1 − d , the fraction of “bad” partitions is upper-bounded by Since m → ∞ the fraction of bad partitions goes to zero. Note that | ( − H I UV + H I U + H I V + H$_{UV}$ ) | is at most O (log m $^{2}$) because by Jensen’s in- equality, | H I $_{UV}$|  ≤ log m $^{2}$, | H I $_{U}$|  ≤ log m $^{2}$, | H I $_{V}$|  ≤ log m $^{2}$, and | H$_{UV}$ | = I$_{XY}$ is assumed to be bounded. Therefore, Since the second term of the RHS goes to zero as N → ∞ ,m → ∞ , m √ N → 0, the proof is complete. We shall prove items 1 and 2 for the DDP statistic only, since the proof for the ADP statistic is very similar. We shall use the notation of Section A.1. Let ˆ m be the value of m with minimum p -value, To prove item 1, we note that from equation (A.7) it follows that under the alternative, 59 lim N →∞ S$_{ˆ}$ m × ˆ m ( N ˆ m − 1 $^{)}$( N − ˆ m + 1) ≥ c $^{′′}$. ˆ m = arg min m ∈{ 2 ,...,m$_{max}$ $_{}}$p$_{2}$ ,...,p$_{m}$. | $^{∑}$$_{I}$( − H I UV + H I U + H I V + H$_{UV}$ ) | | Π | ≤ ϵ/ 3 + O $^{(}$log m $^{2}$m (1 − d ) m − 1 $^{)}$. 2 m ( N (1 − d ) m − 1 )( N m − 1 ) (( N − 1 m − 1 )) 2 ≤ 2 m (1 − d ) m − $^{1}$. C Proof of Theorem 2.6