is available for this N , or max { O ( M × N $^{4}$) ,O ( B × N $^{4}$) } if the null table is generated by the user using B Monte-Carlo replicates for the sample size N . If we needed to recompute the null distribution for every one of the M hypotheses (as required for permutation tests that are not distribution-free, such as dCov and HHG), then the computational complexity would have been O ( M × B × N $^{4}$), which may be infeasible in modern studies where the number of hypotheses tests simultaneously examined can be several thousands or hundreds of thousands. Since the null distribution needs to be generated only once in order to compute the significance of all the M test statistics, due to the distribution-free property of our tests, they can be feasible with today’s computing power even for a few thousands samples. However, computing O ( N $^{4}$) test statistics is unfeasible for larger sample sizes. To reduce the computational complexity when N is large, statistics which do not go over all partitions but rather just over a representative sample can be considered. This approach was used for example in Jiang (2014) for the K -sample problem. A simple way of doing this is to divide the data into √ N × √ N bins and only consider partitions that do not break up these bins. We expect such statistics to also be consistent and the algorithms that accompany them to be computable in O ( N $^{2}$). 

If one expects relatively simple dependence structures, for large N , the S DDP 3 × 3 is recommended, since it is both distribution-free and computable in O ( N $^{2}$) (see Remark 3.1). In our simulations it was as powerful as HHG and more powerful than dCov, and it has the advantage over HHG of being distribution-free. 

A thorough investigation of the suggested mutual information estimator in Section 2 was outside the scope of this paper, but is of interest for future research. We suspect the asymptotic distribution of our mutual information estimator has a simple form. The bias of the estimator can be dealt with by modifying our estimator, and our algorithms accordingly, to only include partitions with cells of a minimum size, and 

