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

60C05 Combinatorial probability
05C62 Graph representations (geometric and intersection representations, etc.)
05C80 Random graphs (graph-theoretic aspects)
pcalg; TETRAD; MIM
Full Text: DOI arXiv
[1] Castelo, R. and Roverato, A. (2006). A robust procedure for Gaussian graphical models search for microarray data with p larger than n. J. Mach. Learn. Res. 57 2621-2650. · Zbl 1222.68158
[2] Chaudhuri, S., Drton, M. and Richardson, R.T. (2007). Estimation a covariance matrix with zeros. Biometrika 94 199-216. · Zbl 1143.62032
[3] Cox, D.R. and Wermuth, N. (1996). Multivariate Depencies: Models, Analysis & Interpretations . London: Chapman & Hall. · Zbl 0880.62124
[4] Dempster, A. (1972). Covariance selection. Biometrics 28 157-175.
[5] Drton, M. and Richardson, T. (2008). Graphical methods for efficient likelihood inference in Gaussian covariance models. J. Mach. Learn. 9 893-914. · Zbl 1225.62031
[6] Edwards, D. (2000). Introduction to Graphical Modelling . New York: Springer. · Zbl 0952.62003
[7] Friedman, N., Linial, M., Nachman, I. and Pe’er, D. (2000). Using Bayesian networks to analyse expression data. J. Comput. Biol. 7 (3-4) 601-620.
[8] Geiger, D. and Pearl, J. (1993). Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 2001-2021. · Zbl 0814.62006
[9] Kalisch, M. and Bühlmann, P. (2007). Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J. Mach. Learn. Res. 8 613-636. · Zbl 1222.68229
[10] Kjærulff, U.B. and Madsen, A.L. (2007). Bayesian Networks and Influence Diagrams . New York: Springer. · Zbl 1117.90031
[11] Lauritzen, S.L. (1996). Graphical Models . New York: Oxford Univ. Press. · Zbl 0907.62001
[12] Letac, G. and Massam, H. (2007). Wishart distributions on decomposable graphs. Ann. Statist. 35 1278-1323. · Zbl 1194.62078
[13] Rajaratnam, B., Massam, H. and Carvalho, C. (2008). Flexible covariance estimation in graphical models. Ann. Statist. 36 2818-2849. · Zbl 1168.62054
[14] Spirtes, P., Glymour, C. and Scheines, R. (2000). Causation, Prediction and Search , 2nd ed. Cambridge, MA: MIT Press. · Zbl 0806.62001
[15] Whittaker, J. (1990). Graphical Models in Applied Multivariate Statistics . Cambridge, MA: Wiley. · Zbl 0732.62056
[16] Wille, A. and Bühlman, P. (2006). Low-order conditional independence graphs for inferring genetic network. Stat. Appl. Genet. Mol. Biol. 5 1-32. · Zbl 1166.62374
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.