id: 05816137
dt: j
an: 05816137
au: Malouche, Dhafer
ti: Determining full conditional independence by low-order conditioning.
so: Bernoulli 15, No. 4, 1179-1189 (2009).
py: 2009
pu: International Statistical Institute (ISI), Voorburg; Bernoulli Society for
    Mathematical Statistics and Probability, Voorburg
la: EN
cc: 
ut: concentration graph models; conditional independence; graphical models;
    Markov properties; separability in graphs; undirected graphs
ci: 
li: doi:10.3150/09-BEJ193
ab: This paper explores a graphical representation of independence relations
    among a finite set of random variables. Given random variables $X_α$,
    $α\in V$, we can represent independence relations among these
    variables as follows.  $\bold X = (X_α: α\in V)$ is a random vector,
    and for any $A \subseteq V$, let $\bold X_A$ be the subvector of random
    variables $X_{α’}$, $α’\in A$. If $\bold X_A$ and $\bold X_B$ are
    independent given $\bold X_S$, write “$\bold X_A \amalg \bold
    X_B|\bold X_S$.” Meanwhile, if we have a (simple) graph of vertex set
    $V$, given mutually disjoint $A, B, S\subseteq V$, let “$A \perp
    B|S$” mean that every path from a vertex in $A$ to a vertex in $B$
    intersects a vertex in $S$; call $S$ a separator of $A$ and $B$ in the
    graph. Call the probability distribution of these random vectors
    perfectly Markov to a simple graph $G = (V, E)$ if, for any mutually
    disjoint and nonempty $A, B, S \subseteq V$, $A \perp B | S$ iff $\bold
    X_A\amalg\bold X_B | \bold X_S$.  Fixing $\bold X$, for each
    nonnegative integer $k < |V| - 1$, let $G_k = (V, E_k)$ be the graph
    whose edges satisfy, for each $α, β\in V$ with $α\neq β$, $$ (α,
    β) \not\in E_k \iff \exists S \subseteq V \{ α, β\}, \quad |S| = k
    \& X_{\{α\}} \amalg \perp X_{\{β\}} | \bold X_S. $$ On the other
    hand, suppose that $G$ is perfectly Markov with respect to $X_α$,
    $α\in V$, and that $$ m = \max_{(α, β)\not\in E}\min \{|S| : A \perp
    B | S(\text{ in }G)\}. $$ The principal result of this paper is that
    assuming these hypotheses, $E= E_m \subseteq E_{m-1} \subseteq \cdots
    \subseteq E_1$. There are several ancillary and related results, e.g.,
    if $$\max_{ (α, β)\not\in E } \min \{|S| : A \perp B | S(\text{ in
    }G_0) \}< |V|-2, $$ then $E_1 \subseteq E_0$ (where $(αβ) \in E_0$
    iff $X_α$ and $X_β$ are independent).
rv: Gregory Loren McColm (Tampa)