Exponential Improvements for Testing Independence in Data Streams

Abstract

We study the problem of testing whether a joint distribution given by a stream of m tuples in [k] n is a product distribution. Independence testing has been studied previously in the streaming context by Indyk and McGregor (SODA ‘08) and Braverman et al. (STOC ’10, STACS ’10). They designed algorithms to obtain a (1 ± ε)-approximation of the distance between the input joint distribution on tuples in [k] n and the product distribution of its marginals. We give new algorithms with improved space complexity bounds. In particular, for approximating the `2 distance between the joint and product distributions, our space usage is O(nε−2log(mk)) instead of the previous best O˜(3nε−2log(mk)). For approximating the `1 distance, when m =poly(kn), our space usage is exp(O(n2 + n log(n/ε) + log log k)) instead of the previous best (ε−1log(k))(30+n)n. Additionally, we investigate streaming algorithms for testing goodness-offit with respect to Markov chains and Markov random fields.