# Testing Conditional Independence of Discrete Distributions

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2017.

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

- [Generalizing Goal-Conditioned Reinforcement Learning with Variational Causal Reasoning](https://mlsanity.com/paper/2207.09081/) (2022)
- [Equal Opportunity of Coverage in Fair Regression](https://mlsanity.com/paper/2311.02243/) (2023)
- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [On the Sample Complexity of Causal Discovery and the Value of Domain Expertise](https://mlsanity.com/paper/2102.03274/) (2021)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Active Structure Learning of Bayesian Networks in an Observational Setting](https://mlsanity.com/paper/2103.13796/) (2021)
- [Learning general conditional independence structures via the neighbourhood lattice](https://mlsanity.com/paper/2206.05829/) (2022)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Neuro-Causal Factor Analysis](https://mlsanity.com/paper/2305.19802/) (2023)
- [On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery](https://mlsanity.com/paper/2310.13553/) (2023)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Greedy equivalence search for nonparametric graphical models](https://mlsanity.com/paper/2406.17228/) (2024)
- [Learning with Hidden Factorial Structure](https://mlsanity.com/paper/2411.01375/) (2024)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)
- [Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions](https://mlsanity.com/paper/2603.04635/) (2026)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)
- [Discrete Causal Representations from Heterogeneous Domains: A Bayesian Approach with Social Survey Applications](https://mlsanity.com/paper/2606.06288/) (2026)

## Abstract (arXiv)

We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X, Y, Z) on domain [ℓ1]×[ℓ2] × [n], we want to distinguish, with probability at least 2/3, between the case that X and Y are conditionally independent given Z from the case that (X, Y, Z) is ε-far, in ℓ1-distance, from every distribution that has this property. Conditional independence is a concept of central importance in probability and statistics with a range of applications in various scientific domains. As such, the statistical task of testing conditional independence has been extensively studied in various forms within the statistics and econometrics communities for nearly a century. Perhaps surprisingly, this problem has not been previously considered in the framework of distribution property testing and in particular no tester with sublinear sample complexity is known, even for the important special case that the domains of X and Y are binary. The main algorithmic result of this work is the first conditional independence tester with em sublinear sample complexity for discrete distributions over [ℓ1]×[ℓ2] × [n]. To complement our upper bounds, we prove information-theoretic lower bounds establishing that the sample complexity of our algorithm is optimal, up to constant factors, for a number of settings. Specifically, for the prototypical setting when ℓ1, ℓ2 = O(1), we show that the sample complexity of testing conditional independence (upper bound and matching lower bound) is [ Thetaleft(maxleft(n1/2/ε2,minleft(n7/8/ε,n6/7/ε8/7right)right)right),. ]