Note: A pointer to a reference, or a yes/no answer with a 1-2 sentence incomplete/non-rigorous justification would suffice for answers. I am just curious about whether the result is true; it is fairly unambiguous that I presently lack the means to understand it adequately. /Note

In 1992, Studeny gave a proof that there exists no complete finite axiomatization of countable independence (Conditional Independence Relations have no Finite Complete Characterization - alternative link). (Apparently Sullivant has shown in 2007 that this is true even for Gaussians.)

The proof involves giving a countable sequence of true conditional independence statements, indexed by $n$, such that the statements for $m< n$ do not imply that for $n$. (At least according to Wolfgang Spohn -- more on this later.) Sullivant uses a similar approach for his proof.

Studeny says in the abstract of his 1992 paper that:

However, under the assumption that CIRs [conditional-independence relations] are grasped the existence of a countable characterization of CIRs is shown.

Since Studeny seems to be calling a "complete finite axiomatization" a "finite characterization", this seems to suggest that Studeny is even claiming/asserting that he has shown a complete countable axiomatization of conditional independence.

Question: Is this correct? Has Studeny or anyone else shown the existence of a complete countable axiomatization of conditional independence? (Soundness is not in dispute.)

Later in the introduction, Studeny seems to possibly demur, saying only:

The main result is proved in the fourth section. It is supplied by the construction of a countable characterization of CIRs by $\square$ properties (however applicable only in the case that all CIRs are grasped). The fifth description is devoted to a syntactical description of CI [conditional independence]. We show how a formal axiomatization for CI can look and show that no simple complete deductive system for CI exists.

In particular, I don't understand the condition "all conditional independence relations are grasped", nor whether the mentioned formal axiomatization is complete, or just sound, nor what is meant by a "simple complete deductive system" (as opposed to more general complete deductive systems).

I tried to read the fourth and fifth sections of the paper to get answers to these questions. However, due to my almost complete ignorance of mathematical logic, I understood almost nothing. (Maybe some of Example 2 and Definition 3, but the rest is more or less completely lost on me.)

Fortunately, Wolfgang Spohn, in the 1994 paper On the Properties of Conditional Independence (alternative link) effectively did me the favor of interpreting Studeny's paper and explaining some of it in language I can better understand. Specifically, on page 14 he writes:

Studeny (1992), p. 382, presents a further, simpler family of properties applying to all probability measures:

(S4) Let $\{X_0, \dots, X_{n-1}\}$ be $n$ variables $(n \ge 4)$. Then $X_0 \perp X_i | X_{i+1}$ holds for all $i = 1, \dots, n-1$ if and only if $X_0 \perp X_{i+1} | X_i$ holds for all $i=1,\dots, n-1$ (subscripts taken modulo $n$).

Spohn seems to go on to say that he hopes that at least it can be shown that this axiom family can be written recursively. But Spohn does not seem to mention whether the typical conditional independence axioms (see below) become complete when one replaces the fourth axiom (which corresponds, I think, to the case that $n=4$ in the family given by Studeny above) with Studeny's countable family of axioms. (Which is the only thing I am interested in.)

Seemingly, if this did make the conditional independence axioms not only sound, but even complete, most authors discussing the topic would use these completed axioms instead, since e.g. statisticians are not likely to care very much if one has to use second-order logic. Instead, in all of the references discussing the conditional independence axioms I have seen so far, only the typical, sound but not complete, axioms are mentioned. And since both Studeny and Spohn seem to be beating around the bush about whether this countable axiom family is a complete axiomatization or not, rather than saying so explicitly in unequivocal terms, I am not sure what to think.

Background - Axioms for Conditional Independence/Graphoids:
These can be found on Wikipedia, here or here, or for actual legitimate references one can see e.g. p. 29 of Lauritzen, Graphical Models (1996), pp. 24-25 of Koller and Friedman, Probabilistic Graphical Models (2009), or pp. 32-35 of Whittaker, Graphical Models in Applied Mathematical Multivariate Statistics (1990). Anyway, they are as follows:

  • (S1) If $X_0 \perp X_1 | X_2$ then $X_1 \perp X_0 | X_2$.
  • (S2) If $X_0 \perp (X_1, X_3) | X_2$ then $X_0 \perp X_1 | X_2$ and $X_0 \perp X_3 | X_2$.
  • (S3) If $X_0 \perp (X_1, X_3) | X_2$ then $X_0 \perp X_1 | (X_2, X_3)$.
  • (S4) If $X_0 \perp X_1 | X_2$ and $X_0 \perp X_3 | (X_1, X_2)$ then $X_0 \perp (X_1, X_3) | X_2$.

It is well known that these are sound axioms, and Studeny in 1992 disproved the conjecture that they are complete. My question is about whether, according to Studeny or someone else, the fourth axiom (or another one of the axioms) can be replaced with a countable family of axioms indexed by $n$ such that all of the axioms are not just sound but even complete.

(There is also a fifth axiom which holds for positive distributions but I'm not asking about that here for the sake of increased simplicity/brevity.)


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.