Independence Testing for Bounded Degree Bayesian Network

2022/04/19 by Arnab Bhattacharyya, Clément L. Canonne, Bhattacharyya, Arnab +3 · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference

paper · pdf · doi:10.48550/arxiv.2204.08690

Abstract

We study the following independence testing problem: given access to samples from a distribution P over \0,1\ⁿ, decide whether P is a product distribution or whether it is ε-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires exp(n) samples. We show in this work that if P has a sparse structure, then in fact only linearly many samples are required. Specifically, if P is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by d, then Θ(2^d/2⋅ n/ε²) samples are necessary and sufficient for independence testing.

Cited by

• Entropy Equivalence Testing

Related

• A Bayesian Multiresolution Independence Test for Continuous Variables
• Optimal rates for independence testing via U-statistic permutation tests
• Testing Conditional Independence of Discrete Distributions
• Testing Bayesian Networks
• Optimal Testing for Properties of Distributions