# Testing Conditional Independence on Discrete Data using Stochastic Complexity

arXiv: https://arxiv.org/abs/1903.04829 · HTML: https://mlsanity.com/paper/1903.04829/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2019.

## Built on by (most cited first, 10 of 10)

- [Combining Human Predictions with Model Probabilities via Confusion Matrices and Calibration](https://mlsanity.com/paper/2109.14591/) (2021)
- [Beyond Normal: On the Evaluation of Mutual Information Estimators](https://mlsanity.com/paper/2306.11078/) (2023)
- [A Survey on Causal Discovery Methods for I.I.D. and Time Series Data](https://mlsanity.com/paper/2303.15027/) (2023)
- [On the Sample Complexity of Causal Discovery and the Value of Domain Expertise](https://mlsanity.com/paper/2102.03274/) (2021)
- [Towards Efficient Local Causal Structure Learning](https://mlsanity.com/paper/2103.00378/) (2021)
- [Conditional independence testing under misspecified inductive biases](https://mlsanity.com/paper/2307.02520/) (2023)
- [On the Properties and Estimation of Pointwise Mutual Information Profiles](https://mlsanity.com/paper/2310.10240/) (2023)
- [A Simple Unified Approach to Testing High-Dimensional Conditional Independences for Categorical and Ordinal Data](https://mlsanity.com/paper/2206.04356/) (2022)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption](https://mlsanity.com/paper/2607.26357/) (2026)

## Abstract (arXiv)

Testing for conditional independence is a core aspect of constraint-based causal discovery. Although commonly used tests are perfect in theory, they often fail to reject independence in practice, especially when conditioning on multiple variables. We focus on discrete data and propose a new test based on the notion of algorithmic independence that we instantiate using stochastic complexity. Amongst others, we show that our proposed test, SCI, is an asymptotically unbiased as well as L2 consistent estimator for conditional mutual information (CMI). Further, we show that SCI can be reformulated to find a sensible threshold for CMI that works well on limited samples. Empirical evaluation shows that SCI has a lower type II error than commonly used tests. As a result, we obtain a higher recall when we use SCI in causal discovery algorithms, without compromising the precision.