content_image/323953.jpg content_image/323952.jpg content_image/323951.jpg content_image/323950.jpg
from (A.16) that almost surely, 

for some constant c ′′ > 0. 

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

Consider now a random permutation ( πy$_{1}$ ) , . . . , ( πy$_{N}$ ) of the y -values y$_{1}$, . . . , y$_{N}$ . Let S π m × m be the test statistic that is computed from the data ( x$_{1}$, πy$_{1}$ ) , . . . , ( x$_{N}$, πy$_{N}$ ). By Markov’s inequality, 

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

where ⃗ x = ( x$_{1}$, . . . , x$_{N}$ ) and ⃗ y = ( y$_{1}$, . . . , y$_{N}$ ). The approximation in (A.18) becomes more accurate the larger N is, since each of the contingency tables is approximately χ 2 with ( m − 1) 2 degrees of freedom. The right hand side of equation (A.18) goes to zero as N → ∞ , as long as lim$_{N}$$_{→∞}$ m √ N = 0. Thus, 

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

We now have all the necessary results to complete the proof. Specifically, 

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

where the inequality follows from (A.19), since S tab 1 − α is below c ′′ ( N − 1 m − 1 )( N − 1 m − 1 $^{)}$N for N large enough, and the equality follows from (A.17), thus proving item 1 of Theorem 1 for the ADP summation statistic. 

