# zbMATH — the first resource for mathematics

Determining full conditional independence by low-order conditioning. (English) Zbl 1206.60009
This paper explores a graphical representation of independence relations among a finite set of random variables. Given random variables $$X_\alpha$$, $$\alpha\in V$$, we can represent independence relations among these variables as follows.
$$\mathbf X = (X_\alpha: \alpha\in V)$$ is a random vector, and for any $$A \subseteq V$$, let $$\mathbf X_A$$ be the subvector of random variables $$X_{\alpha'}$$, $$\alpha'\in A$$. If $$\mathbf X_A$$ and $$\mathbf X_B$$ are independent given $$\mathbf X_S$$, write “$$\mathbf X_A \amalg \mathbf X_B|\mathbf 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 $$\mathbf X_A\amalg\mathbf X_B | \mathbf X_S$$.
Fixing $$\mathbf X$$, for each nonnegative integer $$k < |V| - 1$$, let $$G_k = (V, E_k)$$ be the graph whose edges satisfy, for each $$\alpha, \beta \in V$$ with $$\alpha \neq \beta$$,
$(\alpha, \beta) \not\in E_k \iff \exists S \subseteq V \{ \alpha, \beta \}, \quad |S| = k\;\&\;X_{\{\alpha\}} \amalg \perp X_{\{\beta\}} | \mathbf X_S.$
On the other hand, suppose that $$G$$ is perfectly Markov with respect to $$X_{\alpha}$$, $$\alpha \in V$$, and that
$m = \max_{(\alpha, \beta)\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_{ (\alpha, \beta)\not\in E } \min \{|S| : A \perp B | S(\text{ in }G_0) \}< |V|-2,$
then $$E_1 \subseteq E_0$$ (where $$(\alpha \beta) \in E_0$$ iff $$X_\alpha$$ and $$X_\beta$$ are independent).

##### MSC:
 60C05 Combinatorial probability 05C62 Graph representations (geometric and intersection representations, etc.) 05C80 Random graphs (graph-theoretic aspects)