Testing random variables for independence and identity

Given access to independent samples of a distributionA over [n] [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is -close in the L1 norm to the product distribution A1 A2 for some distributions A1 over [n] and A2 over [m]. The sample complexity of our test is ~O(n2=3m1=3poly(1)), assuming without loss of generality that m n. We also give a matching lower bound, up to poly(log n; 1) factors. Furthermore, given access to samples of a distributionX over [n], we show how to test ifX is -close in L1 norm to an explicitly specified distribution Y. Our test uses ~O(n1=2poly(1)) samples, which nearly matches the known tight bounds for the case when Y is uniform