showed that Hoeffding’s test statistic is asymptotically equivalent to ∑ N i $_{=1}$( o i 1 , $_{1}$o i 2 , 2 − o i 1 , $_{2}$o i 2 , $_{1}$)$^{2}$/N$^{4}$, where o i $_{u,v}$, u, v ∈ { 1 , 2 } , is the observed count of cell ( u, v ) in the 2 × 2 contingency table defined by the i th observation. Thas and Ottoy (2004) noted that by appropriately normalizing each term in the sum, the test statistic becomes the average of all Pearson statistics for independence applied to the contingency tables that are induced by 2 × 2 sample space partitions centered about observation i ∈ { 1 , . . . , N } . They proved that the weighted version of Hoeffding’s test statistic is still consistent. Partitioning the sample space into finer partitions than the 2 × 2 quadrants of the classical tests, based on the observations, was also considered in Thas and Ottoy (2004). They suggested that the average of all Pearson statistics on finer partitions of fixed size m × m may improve the power, but did not provide a proof that the resulting tests are consistent. They examined in simulations only 3 × 3 and 4 × 4 partitions. Reshef et al. (2011) suggested the maximal information coefficient, which is a test statistic based on the maximum over dependence scores taken for partitions of various sizes, after normalization by the partition size, where the purpose of the normalization is equitability rather than power. Since computing the statistic exactly is often infeasible, they resort to a heuristic for selecting which partitions to include. Thus, in practice, their algorithm goes over only a small fraction of the partitions they set out to examine. In Section 4 we show that the power of this test is typically low. As in Section 1.1, we focus on consistent partition-based distribution-free tests. For testing equality of distributions, i.e., for a categorical X , one of the earliest and still very popular distribution-free consistent tests is the Kolmogorov–Smirnov test 5 1.2 Review of the K -sample problem