Kybernetika 50 no. 2, 284-295, 2014

Discriminating between causal structures in Bayesian Networks given partial observations

Philipp Moritz, Jörg Reichardt and Nihat AyDOI: 10.14736/kyb-2014-2-0284


Given a fixed dependency graph $G$ that describes a Bayesian network of binary variables $X_1, \dots, X_n$, our main result is a tight bound on the mutual information $I_c(Y_1, \dots, Y_k) = \sum_{j=1}^k H(Y_j)/c - H(Y_1, \dots, Y_k)$ of an observed subset $Y_1, \dots, Y_k$ of the variables $X_1, \dots, X_n$. Our bound depends on certain quantities that can be computed from the connective structure of the nodes in $G$. Thus it allows to discriminate between different dependency graphs for a probability distribution, as we show from numerical experiments.


Bayesian networks, causal Markov condition, information theory, information inequalities, common ancestors, causal inference


60A08, 62B09


  1. E. S. Allman and J. A. Rhodes: Reconstructing Evolution: New Mathematical and Computational Advances, chapter Phylogenetic invariants. Oxford University Press, 2007.   CrossRef
  2. N. Ay: A refinement of the common cause principle. Discrete Appl. Math. 157 (2009), 10, 2439-2457.   CrossRef
  3. B. Bollob{á}s: Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001.   CrossRef
  4. T. M. Cover and J. A. Thomas: Elements of Information Theory. Second edition. Wiley, 2006.   CrossRef
  5. N. Friedman: Inferring cellular networks using probabilistic graphical models. Science 303 (2004), 5659, 799-805.   CrossRef
  6. J. Peters, J. Mooij, D. Janzing and B. Schölkopf: Causal discovery with continuous additive noise models. arXiv 1309.6779 (2013).   CrossRef
  7. S. L. Lauritzen: Graphical Models. Oxford Science Publications, Clarendon Press, 1996.   CrossRef
  8. S. L. Lauritzen and N. A. Sheehan: Graphical models for genetic analyses. Statist. Sci. 18 (2003), 489-514.   CrossRef
  9. J. Pearl: Causality: Models, Reasoning and Inference. Cambridge University Press, 2000.   CrossRef
  10. H. Reichenbach and M. Reichenbach: The Direction of Time. California Library Reprint Series, University of California Press, 1956.   CrossRef
  11. J. E. S. Socolar and S. A. Kauffman: Scaling in ordered and critical random boolean networks. Phys. Rev. Lett. 90 (2003), 068702.   CrossRef
  12. B. Steudel and N. Ay: Information-theoretic inference of common ancestors. CoRR, abs/1010.5720, 2010.   CrossRef
  13. M. Studen{ý}: Probabilistic Conditional Independence Structures. Information Science and Statistics. Springer, 2005.   CrossRef