  We consider the problem of testing whether pairs of univariate random
variables are associated. Few tests of independence exist that are consistent
against all dependent alternatives and are distribution free. We propose novel
tests that are consistent, distribution free, and have excellent power
properties. The tests have simple form, and are surprisingly computationally
efficient thanks to accompanying innovative algorithms we develop. Moreover, we
show that one of the test statistics is a consistent estimator of the mutual
information. We demonstrate the good power properties in simulations, and apply
the tests to a microarray study where many pairs of genes are examined
simultaneously for co-dependence.
