Formally Justifying MDL-based Inference of Cause and Effect

The algorithmic independence of conditionals, which postu- lates that the causal mechanism is algorithmically indepen- dent of the cause, has recently inspired many highly success- ful approaches to distinguish cause from effect given only observational data. Most popular among these is the idea to approximate algorithmic independence via two-part Mini- mum Description Length (MDL). Although intuitively sen- sible, the link between the original postulate and practical two-part MDL encodings has so far been left vague. In this work, we close this gap by deriving a two-part formulation of this postulate, in terms of Kolmogorov complexity, which directly links to practical MDL encodings. To close the cy- cle, we prove that this formulation leads on expectation to the same inference result as the original postulate.