Testing that distributions are close

Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n/sup 2/3//spl epsiv//sup -4/ log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than max(/spl epsiv//sup 2//32/sup 3//spl radic/n, /spl epsiv//4/spl radic/n=)) or large (more than /spl epsiv/) in L/sub 1/-distance. We also give an /spl Omega/(n/sup 2/3//spl epsiv//sup -2/3/) lower bound. Our algorithm has applications to the problem of checking whether a given Markov process is rapidly mixing. We develop sublinear algorithms for this problem as well.

Authors

• Tugkan Batu
• Lance Fortnow
• Ronitt Rubinfeld
• Warren D. Smith
• Patrick White

Keywords

• Testing
• National electric code
• Computer science
• Sampling methods
• Markov processes
• Engineering profession
• Filtering
• Markov Chain
• Rapid Mixing
• Uniform Distribution
• Heavy Metals
• Running Time
• Time Complexity
• Random Walk
• Class Distribution
• Matrix M
• Matrix Representation
• Testing Algorithm
• Symmetric Encryption
• Nonzero Entries
• Input Distribution
• Collision Probability
• Ith Sample
• Regular Graphs
• Entry In Row
• Kullback-Leibler Distance
• Chebyshev’s Inequality