# Is there a complete and finite axiom scheme for conditional independence? (Graphoids)

Note: This is a better-written version of an unanswered question asked before on MathOverflow.

Question: Is there a complete and finite axiom scheme for conditional probability?

If so, is there a reference stating the axiom scheme in a manner understandable to someone with knowledge of only probability theory, and without knowledge of mathematical logic?

A complete axiomatization or axiom scheme means that every result of the theory can be shown to be a result of the axioms involved. A finite axiomatization involves only finitely many axioms. I understand a finite axiom scheme to mean possibly infinitely many axioms expressable with finitely many symbols (e.g. the axiom scheme in Tarski's axiomatization of Euclidean geometry). $$\newcommand\independent{\perp\,\!\,\!\,\!\,\!\,\!\,\!\,\!\!\!\!\perp}$$

Background: Judea Pearl at the Computer Science department at UCLA and co-workers found a complete and finite axiomatization of (unconditional) probabilistic independence in the 1990's and then began to look for a complete and finite axiomatization of conditional independence. However, Studeny showed in 1992 [1][2] that no such complete and finite axiomatization exists.

An aspect of Studeny's 1992 paper which is less often emphasized is that it also claims to give a complete axiom scheme for conditional probability. Since the paper is written using very abstract mathematical logic, I don't understand what the axiom scheme is supposed to be. Wolfgang Spohn wrote [1][2] about the result and gives what is a somewhat more transparent description of the axiom scheme, but the organization of his paper is unclear to me, as is the notation at times. Seth Sullivant appears to have written about a similar issue, which may have allowed me to understand at least one part of the axiom scheme. Attempting to interpolate between those three papers, this may be what a complete and finite axiom scheme for conditional probability looks like (please note that the the $$U$$'s, $$V$$'s, $$W$$'s, $$X$$'s, $$\tilde{X}$$'s, $$Y$$'s, and $$\tilde{Y}$$'s are all supposed to denote random variables):

1. $$\{X_1, \dots, X_k \} \independent \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$ $$\iff \{Y_1, \dots, Y_l\} \independent \{X_1, \dots, X_k\} | \{W_1 \dots W_m\}$$
2. $$\{V_1, \dots, V_j\} \independent \emptyset | \{W_1, \dots, W_m \}$$
3. $$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$ $$\implies \{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} | \{W_1, \dots, W_m\}$$
4. $$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1 ,\dots, W_m \}$$ $$\implies \{ V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$
5. $$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$ $$\text{and }\{V_1, \dots, V_j\} \independent \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$ $$\implies \{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$
6. For a strictly positive probability measure, i.e. $$\mathbb{P}(A) = 0 \iff A = \emptyset$$, we have: $$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$ $$\text{and }\{V_1, \dots, V_j\} \independent \{Y_1, \dots, Y_l \} | \{X_1, \dots, X_k\} \cup \{W_1, \dots, W_m\}$$ $$\implies \{V_1,\dots,V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$
7. If $$U$$ is an RV taking only two values, e.g. Bernoulli or Rademacher, then $$\{X_1, \dots,X_k\} \independent \{Y_1, \dots, Y_l\} \text{ and } \{X_1,\dots, X_k\} \independent \{Y_1, \dots, Y_l\} | U$$ $$\implies \{X_1, \dots, X_k \} \cup U \independent \{Y_1, \dots, Y_l\} \text{ or }\{X_1, \dots, X_k\} \independent \{Y_1, \dots, Y_l\} \cup U$$
8. $$\{X_1, \dots, X_k\} \independent \{\tilde{X}_1,\dots, \tilde{X}_{\tilde{k}} \} \,, \{Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} | \{X_1, \dots, X_k\} \,,$$ $$\{Y_1, \dots, Y_l \} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} | \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\}\,, \text{ and }$$ $$\{X_1, \dots, X_k\} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l\} \cup \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \}$$ $$\iff \{Y_1, \dots, Y_l \} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \,, \{X_1, \dots, X_k\} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{Y_1, \dots, Y_l\} \,,$$ $$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \,, \text{ and }$$ $$\{ Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_l \} | \{X_1, \dots, X_k\} \cup \{ \tilde{X}_1, \dots, \tilde{X}_k \}$$
9. For a strictly positive probability measure, i.e. $$\mathbb{P}(A) = 0 \iff A = \emptyset$$, we have: $$\text{If }\{Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} | \{X_1, \dots, X_k \} \cup \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} \cup \{W_1, \dots, W_m\} \,,$$ then any three of the following implies the fourth: $$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{W_1, \dots, W_m\}\,,$$ $$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \} \,,$$ $$\{ X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \cup \{W_1, \dots, W_m \} \,,$$ $$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l \} \cup \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} \cup \{W_1, \dots, W_m\} \,.$$
10. For every $$n \ge 4$$ (this is technically an axiom scheme and not an axiom because as Studeny showed in 1992 these are all logically independent of one another for each $$n$$) one has that: $$X_1 \independent X_2 | X_3\,, X_2 \independent X_3 | X_4\,, \dots, X_{n-1} \independent X_n | X_1\,, X_n \independent X_1 | X_2$$ $$\iff X_1 \independent X_3 | X_2\,, X_2 \independent X_4 | X_3 \,, \dots , X_{n-1} \independent X_1 | X_n \,, X_n \independent X_2 | X_1 \,.$$
• What are the V, X, Y, W variables? Events? Atomic events? Something else? – Joshua Grochow Feb 17 '18 at 15:08
• @JoshuaGrochow They are random variables (I think) -- you are right, I should clarify that. – Chill2Macht Feb 17 '18 at 15:10
• Is the work of @AlexSimpson relevant? – Andrej Bauer Feb 18 '18 at 8:03