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)