Testing random variables for independence and identity

Given access to independent samples of a distribution A over [n] x [m], we show how to test whether the distributions formed by projecting A to each coordinate are in dependent, i.e., whether A is epsilon -close in the L-1 norm to the product distribution A(1) x A(2) for some distributions A(1) over [n] and A(2) over [m]. The sample complexity of our test is (O) over tilde (n(2/3)m(1/3)poly(epsilon (-1))), assuming without loss of generality that m less than or equal to n. We also give a matching lower bound, up to poly(log n, epsilon (-1)) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is epsilon -close in L-1 norm to an explicitly specified distribution Y. Our test uses (O) over tilde (n(1/2)poly(epsilon (-1))) samples, which nearly matches the known tight bounds for the case when Y is uniform.