Abstract
Inferring the causal structure that links n observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why causal inference is also possible when only single observations are present. We develop a theory how to generate causal graphs explaining similarities between single objects. To this end, we replace the notion of conditional stochastic independence in the causal Markov condition with the vanishing of conditional algorithmic mutual information and describe the corresponding causal inference rules. We explain why a consistent reformulation of causal inference in terms of algorithmic complexity implies a new inference principle that takes into account also the complexity of conditional probability densities, making it possible to select among Markov equivalent causal graphs. This insight provides a theoretical foundation of a heuristic principle proposed in earlier work. We also discuss how to replace Kolmogorov complexity with decidable complexity criteria. This can be seen as an algorithmic analog of replacing the empirically undecidable question of statistical independence with practical independence tests that are based on implicit or explicit assumptions on the underlying distribution.
Introduction
Traditional causal inference, largely pioneered by researchers like Judea Pearl, relies on detecting statistical dependencies within large datasets. By identifying which variables are independent of others, we can construct Directed Acyclic Graphs (DAGs) that represent causal structures. However, this approach faces two fundamental limitations: the problem of Markov Equivalence—where different causal directions are statistically indistinguishable—and the inability to infer causality from single observations.
In their 2008 paper, Dominik Janzing and Bernhard Schölkopf propose a paradigm shift. They argue that causal inference is possible even for single objects by replacing statistical independence with algorithmic independence, grounded in Kolmogorov complexity.
The Algorithmic Markov Condition
The core innovation is the Algorithmic Markov Condition (AMC). In the statistical world, the Markov condition states that a variable is independent of its non-descendants given its parents. Janzing and Schölkopf translate this into the language of information theory: the shortest program required to describe a set of observations is the sum of the shortest programs for each variable given its parents.
Formally, if $X$ causes $Y$, the joint complexity $K(x, y)$ should be approximately $K(x) + K(y|x^*)$. If we find that $K(x, y)$ is significantly less than this sum, it implies an algorithmic dependency that suggests a causal link. This allows for causal judgments about single pairs of objects (e.g., determining if one text was copied from another) where statistical sampling is impossible.
Breaking Markov Equivalence: Independence of Mechanisms
One of the most powerful applications of this theory is its ability to distinguish between $X \to Y$ and $Y \to X$ when both are statistically equivalent. The authors introduce the principle of Independence of Markov Kernels (or Independence of Mechanisms).
In a true causal model $X \to Y$, the mechanism that produces the effect from the cause ($P(Y|X)$) should be algorithmically independent of the cause itself ($P(X)$). If the description of the cause contains information about the mechanism, it suggests the model is "tuned" or artificial, indicating that the causal direction might be reversed. In the wrong direction, the marginal $P(Y)$ typically "inherits" complexity from both $P(X)$ and $P(Y|X)$, making $P(Y)$ and $P(X|Y)$ algorithmically dependent.
Illustrative Example: Mixtures of Gaussians
To visualize this, consider a binary cause $X \in \{-1, 1\}$ that shifts a Gaussian distribution $Y$. In the forward direction $X \to Y$, the description is simple: a choice of $X$ and a fixed shift parameter.
As shown in the figure above, the joint distribution consists of two shifted Gaussians. If we attempt to model this as $Y \to X$, the conditional probability $P(X|Y)$ becomes a complex sigmoid function. Crucially, this sigmoid must be precisely aligned with the peaks of the marginal distribution $P(Y)$. This "tuning" implies a high degree of algorithmic mutual information between the marginal and the conditional, signaling that $Y \to X$ is the incorrect causal direction.
From Theory to Practice
While Kolmogorov complexity is famously uncomputable, the paper provides a theoretical foundation for practical heuristics. The authors demonstrate that for continuous variables, Fisher Information can serve as a decidable proxy for complexity in cases involving translation-covariant maps. This allows researchers to apply these principles to real-world data where exact algorithmic descriptions are unavailable.
Conclusion
Janzing and Schölkopf’s work extends causal inference beyond the realm of frequentist statistics. By framing causality as a matter of information compression and algorithmic simplicity, they provide a robust framework for understanding why the "true" causal direction is often the one with the most parsimonious description. This approach not only helps resolve Markov equivalence but also opens the door to causal reasoning in domains where only single instances are available, treating a statistical sample of $n$ observations as one single, long, compressible string.
Summary updated