  A popular approach for testing if two univariate random variables are
statistically independent consists of partitioning the sample space into bins,
and evaluating a test statistic on the binned data. The partition size matters,
and the optimal partition size is data dependent. While for detecting simple
relationships coarse partitions may be best, for detecting complex
relationships a great gain in power can be achieved by considering finer
partitions. We suggest novel consistent distribution-free tests that are based
on summation or maximization aggregation of scores over all partitions of a
fixed size. We show that our test statistics based on summation can serve as
good estimators of the mutual information. Moreover, we suggest regularized
tests that aggregate over all partition sizes, and prove those are consistent
too. We provide polynomial-time algorithms, which are critical for computing
the suggested test statistics efficiently. We show that the power of the
regularized tests is excellent compared to existing tests, and almost as
powerful as the tests based on the optimal (yet unknown in practice) partition
size, in simulations as well as on a real data example.
