Testing Conditional Independence of Discrete Distributions

2017/11/30 by Clément L. Canonne, Ilias Diakonikolas, Canonne, Clément L. +5 · 3 citations
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Statistical and Computational Modeling #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1711.11560

openalex publication_date 2017/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X, Y, Z) on domain [ℓ₁]×[ℓ₂] × [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 ℓ₁-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 [ℓ₁]×[ℓ₂] × [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 ℓ₁, ℓ₂ = O(1), we show that the sample complexity of testing conditional independence (upper bound and matching lower bound) is Θ(max(n^1/2/ε²,min(n^7/8/ε,n^6/7/ε^8/7))) .

Citations

• Near-Optimal Closeness Testing of Discrete Histogram Distributions

Cited by

• Optimal structure learning and conditional independence testing
• S-Leak: Leakage-Abuse Attack Against Efficient Conjunctive SSE via s-term Leakage
• Replicable Distribution Testing

Related

• Conditional Independence Testing for Discrete Distributions: Beyond χ²- and G-tests
• Minimax Optimal Conditional Independence Testing
• A New Approach for Testing Properties of Discrete Distributions
• Optimal Testing of Discrete Distributions with High Probability
• Testing Conditional Independence on Discrete Data using Stochastic Complexity