Determining full conditional independence by low-order conditioning (Q605892)

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).