A popular approach for developing distribution-free tests of independence considers partitioning the sample space, and evaluating a test statistic on the binned data. A detailed review of distribution-free partition-based tests is provided in Section 1.1 for the independence problem, and in Section 1.2 for the K -sample problem. In 1.3 we describe our goals and the outline of the present paper. For detecting any type of dependence between X and Y , the null hypothesis states that X and Y are independent, H$_{0}$ : F$_{XY}$ = F$_{X}$F$_{Y}$ , where the joint distribution of ( X,Y ) is denoted by F$_{XY}$ , and the marginal distributions of X and Y , respectively, are denoted by F$_{X}$ and F$_{Y}$ . The alternative is that X and Y are dependent, H$_{1}$ : F$_{XY}$ = F$_{X}$F$_{Y}$ . Figure 1 shows example partitions of the sample space based on the ranked observa- tions, rank ( Y ) versus rank ( X ), where a m × m partition is based on m − 1 observa- tions. We refer to such partitions as data derived partitions (DDP). The dependence in the data can be captured by many partitions, and some partitions are better than others. Hoeffding (1948) suggested a test based on summation of a score over all N 2 × 2 DDP of the sample space, which is consistent against any form of dependence if the bivariate density is continuous. Hoeffding’s test statistic is where ˆ F denotes the empirical cumulative distribution function. Blum et al. (1961) ∫ ∫ N $^{{}$ˆ F$_{XY}$ ( x,y ) − ˆ F$_{X}$ ( x ) ˆ F$_{Y}$ ( y ) } 2 d ˆ F$_{XY}$ ( x,y ) , 1.1 Review of distribution-free tests of independence based on sample space partitions 4