pith. sign in

arxiv: 2504.11978 · v3 · submitted 2025-04-16 · 💻 cs.IT · math.IT· math.ST· stat.TH

On the Intersection and Composition properties of conditional independence

Tobias Boege This is my paper

Pith reviewed 2026-05-22 20:36 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.STstat.TH
keywords conditional independenceintersection propertycomposition propertycompositional graphoidssemigraphoidsinformation theorydiscrete random variablesgraphical models
0
0 comments X

The pith

Sufficient conditions using information-theoretic quantities are derived for the Intersection and Composition properties of conditional independence in discrete random variables.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on compositional graphoids, which are semigraphoids that also satisfy the Intersection and Composition properties and arise in probabilistic reasoning and graphical models. These two properties fail to hold for many probability distributions, so the structures are not universal. The work surveys existing results, supplies systematic examples and counterexamples, and states necessary and sufficient conditions. It then supplies new sufficient conditions obtained from information-theoretic functionals for the discrete case. A reader cares because these conditions give a concrete route to confirming when a distribution will behave as a compositional graphoid.

Core claim

Compositional graphoids are fundamental discrete structures in probabilistic reasoning that require the Intersection and Composition properties in addition to the semigraphoid axioms, yet general distributions do not satisfy them. The paper surveys what is known, constructs examples and counterexamples, and states necessary and sufficient conditions. Novel sufficient conditions for both properties are obtained for discrete random variables by means of information-theoretic tools.

What carries the argument

Information-theoretic functionals such as entropy and mutual information that characterize the Intersection and Composition properties.

Load-bearing premise

The derivations of the novel sufficient conditions assume that entropy and mutual information functionals can be applied to characterize the properties without further restrictions on the support or positivity of the discrete distributions.

What would settle it

A discrete joint distribution that satisfies one of the new information-theoretic sufficient conditions yet violates the Intersection property on some triple of variables would show the claimed sufficiency does not hold.

Figures

Figures reproduced from arXiv: 2504.11978 by Tobias Boege.

Figure 1
Figure 1. Figure 1: The generic information diagram of three jointly distributed random variables A, X, Y . All of Shannon’s information measures can be expressed as linear combinations of these seven quantities. The proof of this fact merely combines Decomposition and Weak union (with Symmetry) in one direction and Contraction in the other. Since the semigraphoid axioms hold for any system of discrete random variables, we ma… view at source ↗
Figure 2
Figure 2. Figure 2: The premises of Intersection and Composition with non-negative parameters g = I(X : Y | A) and h = ±I(A : X : Y ) [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Information diagram of the G´acs–K¨orner extension. 3.2. The G´acs–K¨orner criterion The positivity of the entire distribution guarantees Intersection but is unnecessarily restrictive. A more refined support condition has been developed independently by groups of statisticians, information theorists and algebraists. It is based on the following concept. Definition 3.6. Let X and Y be jointly distributed di… view at source ↗
Figure 4
Figure 4. Figure 4: Information diagram of Alice, Bob and the next message in an interactive protocol, conditional the transcript of their communication. This implies that H(Mk+1 | X, Ak) = 0 and it follows that h = I(X : Y : Mk+1 | Ak) = I(Mk+1 : Y | Ak) is non-negative and hence I(X : Y | Ak) ≥ I(X : Y | Ak+1); see [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An almost-tight distribution with a large violation of (7). The third implication. The proper (unsymmetrized) form of the third converse implication has been considered in the work of [13] which features a sufficient condition derived from a generalization of Basu’s theorem. For discrete random variables, our approach of using conditional information inequalities also applies. Theorem 5.2. Let A, X, Y be j… view at source ↗
Figure 6
Figure 6. Figure 6: When A = X + Y for X and Y independent and uniformly distributed in an abelian group then x = y = h. becomes constant and the entropy profile in the limit satisfies the conditions of (7). For each fixed λ > 0 there exists a distribution in this family which satisfies H(X | A, Y ) = H(Y | A, X) = I(A : X) = I(A : Y ) = 0 and H(X) = H(Y ) = α but also α + λH(A | X, Y ) = α + λε ≪ log(2) ≤ log ⌈exp ε⌉ = log ⌈… view at source ↗
read the original abstract

Compositional graphoids are fundamental discrete structures which appear in probabilistic reasoning, particularly in the area of graphical models. They are semigraphoids which satisfy the Intersection and Composition properties. These important properties, however, are not enjoyed by general probability distributions. This paper surveys what is known about them, providing systematic constructions of examples and counterexamples as well as necessary and sufficient conditions. Novel sufficient conditions for both properties are derived in the context of discrete random variables via information-theoretic tools.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript surveys compositional graphoids (semigraphoids satisfying both Intersection and Composition), supplies systematic constructions of examples and counterexamples, states necessary and sufficient conditions, and derives novel sufficient conditions for these properties on discrete random variables by means of information-theoretic functionals such as conditional mutual information and entropy equalities.

Significance. If the novel sufficient conditions hold as stated, the work consolidates known results on when general distributions obey these graphoid axioms and supplies a fresh information-theoretic route to sufficient conditions. The explicit constructions of examples and counterexamples constitute a concrete strength that makes the survey useful for researchers in graphical models and probabilistic reasoning.

major comments (1)
  1. [Sections presenting the novel sufficient conditions via information-theoretic tools] The derivations of the novel sufficient conditions (the central new contribution) equate vanishing conditional mutual information or entropy identities to the Intersection and Composition axioms. These algebraic steps presuppose that all relevant probabilities are strictly positive so that logarithms and divisions remain defined; the manuscript does not state this restriction or supply a separate argument for the boundary of the probability simplex. Because known counterexamples to Intersection and Composition occur precisely when some joint probabilities are zero, the claimed sufficiency is load-bearing only if the domain is clarified.
minor comments (2)
  1. [Preliminaries] Notation for conditional independence statements and the precise definition of the information-theoretic quantities used in the new conditions should be collected in a single preliminary section for easier reference.
  2. [Abstract] The abstract states that 'systematic constructions' are provided; cross-references from the abstract to the specific sections or theorems containing those constructions would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on the manuscript. We address the single major comment below and will incorporate the suggested clarification in the revised version.

read point-by-point responses

  1. Referee: [Sections presenting the novel sufficient conditions via information-theoretic tools] The derivations of the novel sufficient conditions (the central new contribution) equate vanishing conditional mutual information or entropy identities to the Intersection and Composition axioms. These algebraic steps presuppose that all relevant probabilities are strictly positive so that logarithms and divisions remain defined; the manuscript does not state this restriction or supply a separate argument for the boundary of the probability simplex. Because known counterexamples to Intersection and Composition occur precisely when some joint probabilities are zero, the claimed sufficiency is load-bearing only if the domain is clarified.

    Authors: We agree that the information-theoretic derivations in the sections on novel sufficient conditions rely on the assumption of strictly positive joint probabilities, which ensures that the logarithms appearing in the definitions of conditional mutual information and entropy are well-defined. The current manuscript does not explicitly flag this restriction. We will revise those sections to state clearly that the sufficient conditions are derived under the standing assumption of strictly positive probability mass functions. We will also add a brief remark noting that this domain excludes the zero-probability cases in which Intersection and Composition are known to fail, thereby delineating the scope of the new results. revision: yes

Circularity Check

0 steps flagged

No circularity: derivations of novel sufficient conditions are independent

full rationale

The paper surveys known results on semigraphoids and derives new sufficient conditions for Intersection and Composition using information-theoretic characterizations (entropy and mutual information equalities) for discrete random variables. These steps rely on standard definitions and algebraic manipulations of information quantities rather than fitting parameters to data, self-defining the target properties, or depending on load-bearing self-citations. The central claims remain self-contained with independent content from the input axioms and external literature.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard axioms of conditional independence and semigraphoid properties from probability theory, with no free parameters, invented entities, or ad-hoc assumptions introduced beyond the discrete random variable setting.

axioms (1)
  • domain assumption Standard semigraphoid axioms for conditional independence
    The paper defines compositional graphoids as semigraphoids satisfying additional properties, invoking the background axioms of conditional independence.

pith-pipeline@v0.9.0 · 5592 in / 1206 out tokens · 49899 ms · 2026-05-22T20:36:21.445399+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages · 1 internal anchor

  1. [1]

    On the Intersection and Composition properties of conditional independence

    INTRODUCTION One of the most fundamental aspects one could aim to understand about a complex system is its dependence structure: Which observables depend on others? How many degrees of freedom does the vector of observations have as the system evolves? Insights about the dependence structure are not strictly required to tackle more advanced questions abou...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  2. [2]

    PRELIMINARY REDUCTIONS It is well-known that any CI statement[I ⊥ ⊥J | K] with pairwise disjoint sets I, J, K ⊆ N is equivalent modulo the semigraphoid axioms to a conjunction of elementary CI state- ments: [I ⊥ ⊥J | K] ⇐ ⇒ ^ i∈I ^ j∈J ^ K⊆L⊆IJK \ij [i ⊥ ⊥j | L]. (2) 4 T. BOEGE H(A| X,Y) H(X | A,Y) H(Y | A,X) I(A: X: Y) I(X: Y | A) I(A: X | Y) I(A: Y | X)...

    work page

  3. [3]

    The most widely known and the simplest general condition on a distribution which ensures the full Intersection property is that the probability density be strictly positive

    THE INTERSECTION PROPERTY The problem of finding sufficient conditions for the Intersection property has received considerable attention from a variety of research communities. The most widely known and the simplest general condition on a distribution which ensures the full Intersection property is that the probability density be strictly positive. This i...

    work page

  4. [4]

    GraphicalModels

    as well as ∗- and C ∗-separation [1,5]. Example 3.1. A gassoid is a semigraphoid satisfying Intersection, Composition and a further property called Weak transitivity; cf. [31]. Chen [9, Section 2.2] records that gaussoids appear as the CI structures of regular Gaussian random vectors, as the vanishing almost-principal quasi-minors of a polarity in a Desar...

    work page

  5. [5]

    In algebraic statistics, a similar result is known as the Cartwright–Engstr¨ om conjecture which was recorded in [15] and resolved by Fink in [17]

    provide an overview of the history of this idea on the statistics side. In algebraic statistics, a similar result is known as the Cartwright–Engstr¨ om conjecture which was recorded in [15] and resolved by Fink in [17]. It asserts that the binomial ideal corresponding to the premises of Intersection has one associated prime for each possible shape of G(X,...

    work page

  6. [6]

    richness of support

    THE COMPOSITION PROPERTY The previous section showed that the Intersection property is well-studied. By comparison, not much is known about the failure modes of Composition. We again begin by examining examples and show how some approaches that were successful for Intersection cannot succeed for Composition. 4.1. Examples and non-examples To start, Gaussi...

    work page

  7. [7]

    special position

    REMARKS Duality. Intersection and Composition are not only converses modulo the semigraphoid axioms but also dual. For an elementary CI statement [i ⊥ ⊥j | L] over ground set N, the dual statement is [i ⊥ ⊥j | L]∗ := [i ⊥ ⊥j | N \ ijL]. Applying duality statement-wise transforms Intersection [i ⊥ ⊥j | kL] ∧ [i ⊥ ⊥k | jL] = ⇒ [i ⊥ ⊥j | L] ∧ [i ⊥ ⊥k | L] in...

    work page 2020

  8. [8]

    Carlos Am´ endola, Claudia Kl¨ uppelberg, Steffen Lauritzen, and Ngoc M. Tran. Conditional independence in max-linear Bayesian networks. Ann. Appl. Probab., 32(1):1–45, 2022

    work page 2022

  9. [9]

    Amini, Bryon Aragam, and Qing Zhou

    Arash A. Amini, Bryon Aragam, and Qing Zhou. A non-graphical representation of conditional independence via the neighbourhood lattice, 2022

    work page 2022

  10. [10]

    Geometric algebra, volume 3 of Intersci

    Emil Artin. Geometric algebra, volume 3 of Intersci. Tracts Pure Appl. Math. Interscience Publishers, 1957

    work page 1957

  11. [11]

    Bolt, and Milan Studen´ y

    Tobias Boege, Janneke H. Bolt, and Milan Studen´ y. Self-adhesivity in lattices of abstract conditional independence models. Discrete Applied Mathematics, 361:196–225, 2025

    work page 2025

  12. [12]

    Polyhedral aspects of maxoids, 2025

    Tobias Boege, Kamillo Ferry, Benjamin Hollering, and Francesco Nowell. Polyhedral aspects of maxoids, 2025

    work page 2025

  13. [13]

    Construction Methods for Gaussoids

    Tobias Boege and Thomas Kahle. Construction Methods for Gaussoids. Kybernetika, 56(6):1045–1062, 2020

    work page 2020

  14. [14]

    Marginal independence models

    Tobias Boege, Sonja Petrovi´ c, and Bernd Sturmfels. Marginal independence models. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation , ISSAC ’22, pages 263–271. Association for Computing Machinery (ACM), 2022

    work page 2022

  15. [15]

    Springer, 1989

    J¨ urgen Bokowski and Bernd Sturmfels.Computational synthetic geometry , volume 1355 of Lecture Notes in Mathematics . Springer, 1989

    work page 1989

  16. [16]

    Conditional Erlangen Program

    Xiangying Chen. Conditional Erlangen Program. PhD thesis, OvGU Magdeburg, 2024

    work page 2024

  17. [17]

    Cox, John Little, and Donal O’Shea

    David A. Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms . Under- graduate Texts in Mathematics. Springer, 4th edition, 2015

    work page 2015

  18. [18]

    A short proof of the G´ acs–K¨ orner theorem, 2023

    Laszlo Csirmaz. A short proof of the G´ acs–K¨ orner theorem, 2023

    work page 2023

  19. [19]

    Coding theorems for discrete memoryless systems

    Imre Csisz´ ar and J´ anos K¨ orner.Information theory. Coding theorems for discrete memoryless systems. Cambridge University Press, 2nd ed. edition, 2011

    work page 2011

  20. [20]

    Philip Dawid

    A. Philip Dawid. Conditional independence for statistical operations. Ann. Stat., 8:598–617, 1980

    work page 1980

  21. [21]

    Alexander P. Dawid. Conditional independence in statistical theory. J. Roy. Statist. Soc. Ser. B, 41(1):1–31, 1979

    work page 1979

  22. [22]

    Lectures on algebraic statistics , volume 39 of Oberwolfach Semin

    Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on algebraic statistics , volume 39 of Oberwolfach Semin. Birkh¨ auser, 2009. 18 T. BOEGE

    work page 2009

  23. [23]

    Total positivity in Markov structures

    Shaun Fallat, Steffen Lauritzen, Kayvan Sadeghi, Caroline Uhler, Nanny Wermuth, and Piotr Zwiernik. Total positivity in Markov structures. Ann. Stat., 45(3):1152–1184, 2017

    work page 2017

  24. [24]

    The binomial ideal of the intersection axiom for conditional probabilities

    Alex Fink. The binomial ideal of the intersection axiom for conditional probabilities. J. Algebr. Comb., 33(3):455–463, 2011

    work page 2011

  25. [25]

    Common information is far less than mutual information

    Peter G´ acs and J´ anos K¨ orner. Common information is far less than mutual information. Probl. Control Inf. Theory , 2:149–162, 1973

    work page 1973

  26. [26]

    Grayson and Michael E

    Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www2.macaulay2.com. Version 1.22

    work page

  27. [27]

    Uncovering meanings of embeddings via partial orthogonality

    Yibo Jiang, Bryon Aragam, and Victor Veitch. Uncovering meanings of embeddings via partial orthogonality. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurIPS ’23. Curran Associates Inc., 2023

    work page 2023

  28. [28]

    Conditional information inequalities for entropic and almost entropic points

    Tarik Kaced and Andrei Romashchenko. Conditional information inequalities for entropic and almost entropic points. IEEE Trans. Inf. Theory , 59(11):7149–7167, 2013

    work page 2013

  29. [29]

    A conditional information inequality and its combinatorial applications

    Tarik Kaced, Andrei Romashchenko, and Nikolai Vereshchagin. A conditional information inequality and its combinatorial applications. IEEE Trans. Inf. Theory, 64(5):3610–3615, 2018

    work page 2018

  30. [30]

    Algebraic aspects of conditional independence and graphical models

    Thomas Kahle, Johannes Rauh, and Seth Sullivant. Algebraic aspects of conditional independence and graphical models. In Marloes Maathuis, Mathias Drton, Steffen Lauritzen, and Martin Wainwright, editors, Handbook of graphical models, Chapman & Hall/CRC Handbooks of Modern Statistical Methods, pages 61–80. CRC Press, 2019

    work page 2019

  31. [31]

    George A. Kirkup. Random variables with completely independent subcollections. J. Algebra, 309(2):427–454, 2007

    work page 2007

  32. [32]

    Uniqueness of nonnegative matrix factorizations by rigidity theory

    Robert Krone and Kaie Kubjas. Uniqueness of nonnegative matrix factorizations by rigidity theory. SIAM J. Matrix Anal. Appl. , 42(1):134–164, 2021

    work page 2021

  33. [33]

    On entropic and almost multilinear representability of matroids

    Lukas K¨ uhne and Geva Yashfe. On entropic and almost multilinear representability of matroids. 2025

    work page 2025

  34. [34]

    Kumar, Cheuk T

    Gowtham R. Kumar, Cheuk T. Li, and Abbas El Gamal. Exact common information. In 2014 IEEE International Symposium on Information Theory , pages 161–165, 2014

    work page 2014

  35. [35]

    Graphical models, volume 17 of Oxford Statistical Science Series

    Steffen Lauritzen. Graphical models, volume 17 of Oxford Statistical Science Series . Oxford University Press, 1996

    work page 1996

  36. [36]

    Unifying Markov properties for graphical models

    Steffen Lauritzen and Kayvan Sadeghi. Unifying Markov properties for graphical models. Ann. Statist., 46(5):2251–2278, 2018

    work page 2018

  37. [37]

    Undecidability of network coding, conditional information inequalities, and conditional independence implication

    Cheuk Ting Li. Undecidability of network coding, conditional information inequalities, and conditional independence implication. IEEE Trans. Inf. Theory , 69(6):3493–3510, 2023

    work page 2023

  38. [38]

    On Gaussian conditional independence structures

    Radim Lnˇ eniˇ cka and Frantiˇ sek Mat´ uˇ s. On Gaussian conditional independence structures. Kybernetika, 43(3):327–342, 2007

    work page 2007

  39. [39]

    The theory of relational databases

    David Maier. The theory of relational databases . Computer Software Engineering Series. Pitman Publishing Ltd., 1983

    work page 1983

  40. [40]

    Ascending and descending conditional independence relations

    Frantiˇ sek Mat´ uˇ s. Ascending and descending conditional independence relations. InTransac- tions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, volume B, pages 189–200, 1992

    work page 1992

  41. [41]

    Piecewise linear conditional information inequality.IEEE Trans

    Frantiˇ sek Mat´ uˇ s. Piecewise linear conditional information inequality.IEEE Trans. Inf. Theory, 52(1):236–238, 2006. On Intersection and Composition 19

    work page 2006

  42. [42]

    Entropy region and convolution.IEEE Trans

    Frantiˇ sek Mat´ uˇ s and L´ aszlo Csirmaz. Entropy region and convolution.IEEE Trans. Inf. Theory, 62(11):6007–6018, 2016

    work page 2016

  43. [43]

    Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics

    James Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics . Oxford University Press, 2nd edition, 2011

    work page 2011

  44. [44]

    An introduction to stability theory

    Daniel Palac´ ın. An introduction to stability theory. In Lectures in model theory, pages 1–27. European Mathematical Society (EMS), 2018

    work page 2018

  45. [45]

    GRAPHOIDS: A graph-based logic for reasoning about relevance relations, or When would x tell you more about y if you already know z

    Judea Pearl and Azaria Paz. GRAPHOIDS: A graph-based logic for reasoning about relevance relations, or When would x tell you more about y if you already know z. Technical Report CSD-850038, UCLA Computer Science Department, 1985

    work page 1985

  46. [46]

    Pe˜ na, Roland Nilsson, Johan Bj¨ orkegren, and Jesper Tegn´ er

    Jose M. Pe˜ na, Roland Nilsson, Johan Bj¨ orkegren, and Jesper Tegn´ er. Towards scalable and data efficient learning of Markov boundaries. Int. J. Approx. Reasoning , 45(2):211–232, 2007

    work page 2007

  47. [47]

    On the intersection property of conditional independence and its application to causal discovery

    Jonas Peters. On the intersection property of conditional independence and its application to causal discovery. J. Causal Inference, 3(1):97–108, 2015

    work page 2015

  48. [48]

    The direction of time

    Hans Reichenbach. The direction of time . University of California Press, 1971. Edited by Maria Reichenbach

    work page 1971

  49. [49]

    Ignorable common informa- tion, null sets and Basu’s first theorem

    Ernesto San Mart´ ın, Michel Mouchart, and Jean-Marie Rolin. Ignorable common informa- tion, null sets and Basu’s first theorem. Sankhy¯ a, 67(4):674–698, 2005

    work page 2005

  50. [50]

    Information Science and Statistics

    Milan Studen´ y.Probabilistic Conditional Independence Structures. Information Science and Statistics. Springer, 2005

    work page 2005

  51. [51]

    Conditional independence structures over four discrete random variables revisited: conditional Ingleton inequalities

    Milan Studen´ y. Conditional independence structures over four discrete random variables revisited: conditional Ingleton inequalities. IEEE Trans. Inf. Theory, 67(11):7030–7049, 2021

    work page 2021

  52. [52]

    Information-theoretic cryptography

    Himanshu Tyagi and Shun Watanabe. Information-theoretic cryptography. Cambridge University Press, 2023

    work page 2023

  53. [53]

    On the recognition problem for limits of entropy functions, 2025

    Geva Yashfe. On the recognition problem for limits of entropy functions, 2025

    work page 2025

  54. [54]

    Raymond W. Yeung. A first course in information theory . Information Technology: Transmission, Processing and Storage. Springer, 2005. Tobias Boege, Department of Mathematics and Statistics, UiT – The Arctic University of Norway, N-9037 Tromsø e-mail: post@taboege.de

    work page 2005