Milan Studený

# Abstract:

An overview is given of results achieved by F. Matúš on probabilistic conditional independence (CI). First, his axiomatic characterizations of stochastic functional dependence and unconditional independence are recalled. Then his elegant proof of discrete probabilistic representability of a matroid based on its linear representability over a finite field is recalled. It is explained that this result was a basis of his methodology for constructing a probabilistic representation of a given abstract CI structure. His embedding of matroids into (augmented) abstract CI structures is recalled and his contribution to the theory of semigraphoids is mentioned as well. Finally, his results on the characterization of probabilistic CI structures induced by four discrete random variables and by four regular Gaussian random variables are recalled. Partial probabilistic representability by binary random variables is also mentioned.

# Keywords:

conditional independence, matroid, polymatroid, entropy function, semimatroid, semigraphoid

# Classification:

62H05, 05B35, 68T30

# References:

1. G. Birkhoff: Lattice Theory. Third edition. American Mathematical Society, Colloquium Publications 25, Providence 1995.   CrossRef
2. V. Chvátal and B. Wu: On Reichenbach's causal betweenness. Erkenntnis 76 (2012), 41-48.   DOI:10.1007/s10670-011-9321-z
3. V. Chvátal, F. Matúš and Y. Zwólš: Patterns of conjuctive forks. A 2016 manuscript {\tt arXiv/1608.03949}.   CrossRef
4. D. Cox, J. Little and D. O'Shea: Ideals, Varieties, and Algorithms. Springer, New York 1997.   CrossRef
5. A. P. Dawid: Conditional independence in statistical theory. J. Royal Statist. Soc. B 41 (1979), 1, 1-31.   DOI:10.1111/j.2517-6161.1979.tb01052.x
6. A. P. Dawid: Separoids: a mathematical framework for conditional independence and irrelevance. Ann. Math. Artif. Intell. 32 (2001), 1/4, 335-372.   DOI:10.1023/a:1016734104787
7. S. Fujishige: Submodular Functions and Optimization. Second edition. Elsevier, Amsterdam 2005.   CrossRef
8. D. Geiger, A. Paz and J. Pearl: Axioms and algorithms for inferences involving probabilistic independences. Inform. Comput. 91 (1991), 1, 128-141.   DOI:10.1016/0890-5401(91)90077-f
9. D. Geiger and J. Pearl: Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 (1993), 4, 2001-2021.   DOI:10.1214/aos/1176349407
10. A. W. Ingleton: Conditions for representability and transversality of matroids. In: Lecture Notes in Computer Science 211, Springer, 1971, pp. 62-67.   DOI:10.1007/bfb0061075
11. S. L. Lauritzen: Graphical Models. Clarendon Press, Oxford 1996.   CrossRef
12. M. Loéve: Probability Theory, Foundations, Random Sequences. Van Nostrand, Toronto 1955.   CrossRef
13. R. Lněnička and F. Matúš: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342.   CORPUS:16748330
14. F. M. Malvestuto: A unique formal system for binary decompositions of database relations, probability distributions and graphs. Inform. Sci. 59 (1992), 21-52.   DOI:10.1016/0020-0255(92)90042-7
15. F. Matúš: Independence and Radon Projections on Compact Groups (in Slovak). Thesis for CSc. Degree in Theoretical Computer Science, Institute of Information Theory and Automation, Czechoslovak Academy of Sciences, Prague 1988.   CrossRef
16. F. Matúš: Abstract functional dependency structures. Theor. Computer Sci. 81 (1991), 117-126.   DOI:10.1016/0304-3975(91)90319-w
17. F. Matúš: On equivalence of Markov properties over undirected graphs. J. Appl. Probab. 29 (1992), 745-749.   DOI:10.1017/s0021900200043552
18. F. Matúš: Ascending and descending conditional independence relations. In: Trans. 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, volume B, Academia, Prague 1992, pp. 189-200.   CrossRef
19. F. Matúš: Stochastic independence, algebraic independence and abstract connectedness. Theor. Computer Sci. 134 (1994), 455-471.   DOI:10.1016/0304-3975(94)90248-8
20. F. Matúš: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Systems 22 (1994), 185-196.   DOI:10.1080/03081079308935205
21. F. Matúš: Extreme convex set functions with many non-negative differences. Discrete Math. 135 (1994), 177-191.   DOI:10.1016/0012-365x(93)e0100-i
22. F. Matúš and M. Studený: Conditional independences among four random variables I. Combinatorics, Probability and Computing 4 (1995), 269-278.   DOI:10.1017/s0963548300001644
23. F. Matúš: Conditional independences among four random variables II. Combinator. Probab. Comput. 4 (1995), 407-417.   DOI:10.1017/s0963548300001747
24. F. Matúš: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 99-128.   DOI:10.1023/a:1018957117081
25. F. Matúš: Conditional independences among four random variables III: final conclusion. Combinator. Probab. Comput. 8 (1999), 269-276.   DOI:10.1017/s0963548399003740
26. F. Matúš: Lengths of semigraphoid inferences. Ann. Math. Artif. Intell. 35 (2002), 287-294.   DOI:10.1023/a:1014525817725
27. F. Matúš: Towards classification of semigraphoids. Discr. Math. 277 (2004), 115-145.   DOI:10.1016/s0012-365x(03)00155-9
28. F. Matúš: Conditional independences in Gaussian vectors and rings of polynomials. In: Proc. WCII 2002, Lecture Notes in Artificial Intelligence 3301, Springer, Berlin 2005, pp. 152-161.   CORPUS:1893239
29. F. Matúš: On conditional independence and log-convexity. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 48 (2012), 4, 1137-1147.   DOI:10.1214/11-aihp431
30. F. Matúš: On patterns of conditional independences and covariance signs among binary variables. Acta Math. Hungar. 154 (2018), 2, 511-524.   DOI:10.1007/s10474-018-0799-6
31. M. Mouchart and J. M. Rolin: A note on conditional independences with statistical applications. Statistica 44 (1984), 557-584.   ECON:630
32. H. Q. Nguyen: Semimodular functions and combinatorial geometries. Trans. Amer. Math. Soc. 238 (1978), 355-383.   DOI:10.1090/S0002-9947-1978-0491269-9
33. J. G. Oxley: Matroid Theory. Oxford University Press, Oxford 1992.   CrossRef
34. J. Pearl: Probabilistic Reasoning in Intelligent Systems - Networks of Plausible Inference. Morgan Kaufmann, San Francisco 1988.   CrossRef
35. H. Reichenbach: The Direction of Time. University of California Press, Los Angeles 1956.   CrossRef
36. W. Spohn: Stochastic independence, causal independence and shieldability. J. Philosoph. Logic 9 (1980), 1, 73-99.   DOI:10.1007/bf00258078
37. M. Studený: Conditional independence relations have no finite complete characterization. In: Trans. 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, volume B, Academia, Prague 1992, pp. 377-396.   CrossRef
38. M. Studený: Structural semigraphoids. Int. J. General Syst. 22 (1994), 207-217.   DOI:10.1080/03081079308935207
39. M. Studený: Semigraphoids and structures of probabilistic conditional independence. Ann. Math. Artif. Intell. 21 (1997), 71-98.   DOI:10.1023/a:1018905100242
40. M. Studený: Probabilistic Conditional Independence Structures. Springer, London 2005.   CrossRef
41. H. Whitney: On the abstract properties of linear dependence. Amer. J. Math. 57 (1935), 3, 509-533.   DOI:10.2307/2371182
42. J. Whittaker: Graphical Models in Applied Multivariate Statistics. John Wiley and Sons, Chichester 1990.   CrossRef
43. R. W. Yeung: Information Theory and Network Coding. Springer, New York 2008.   CrossRef
44. Z. Zhang and R. W. Yeung: A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986.   DOI:10.1109/18.641561
45. G. M. Ziegler: Lectures on Polytopes. Springer, New York 1995.   CrossRef