intuition is true despite the fact that the number of partitions goes to infinity, since we show that the convergence is uniform and that the fraction of “bad” partitions (i.e., partitions with cells that are too big or too small) is small, as long as m goes to infinity at a slow enough rate. 

Theorem 2.3. Suppose X is categorical with K categories and Y is continuous. Let N$_{g}$ be the total number of observations from distribution g ∈ { 1 ,...,K } , and N = ∑ K g $_{=1}$N$_{g}$ . If lim$_{N}$$_{→∞}$ N$_{g}$ N > 0 for g = 1 ,...,K , lim$_{N}$$_{→∞}$ m N = 0 , and lim$_{N}$$_{→∞}$ m = ∞ , then S$_{m}$ N ( N − 1 m − $_{1}$) is a consistent estimator of the MI. 

Theorem 2.4. Suppose the bivariate density of ( X,Y ) is continuous with bounded mutual information. If lim$_{N}$$_{→∞}$ m/ √ N = 0 , and lim$_{N}$$_{→∞}$ m = ∞ , then S ADP m × m N ( N − 1 m − $_{1}$) × ( N − 1 m − $_{1}$) is a consistent estimator of the MI. 

See Appendix B for a proof of Theorem 2.4. The proof of Theorem 2.3 is omitted since it is similar to that of Theorem 2.4. See Appendix D for a simulated example of MI estimation using S DDP m × $_{m}$, S ADP m × $_{m}$, and the histogram estimator. The ADP estimator is the least variable, as is intuitively expected since it is the average over many partitions. 

Remark 2.1. In this work we assume there are no ties among the continuous vari- ables. In our software, tied data are broken randomly, so that our test remains dis- tribution free. An alternative approach, which is no longer distribution free, is a permutation test on the ranks, with average ranks for ties. Then a tied observation, that falls on the border of a contingency table cell, receives equal weight in each of the cells it borders with. 

