content_image/320175.jpg content_image/320174.jpg content_image/320173.jpg content_image/320172.jpg
1 − d , the fraction of “bad” partitions is upper-bounded by 

Since m → ∞ the fraction of bad partitions goes to zero. 

<img src='content_image/320175.jpg'>

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, 

<img src='content_image/320174.jpg'>

Since the second term of the RHS goes to zero as N → ∞ ,m → ∞ , m √ N → 0, the proof is complete. 

## C Proof of Theorem 2.6 

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, 

<img src='content_image/320173.jpg'>

To prove item 1, we note that from equation (A.7) it follows that under the alternative, 

<img src='content_image/320172.jpg'>

