content_image/295776.jpg content_image/295774.jpg content_image/295775.jpg
Therefore, by Markov’s inequality, 

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

where ⃗x = ( x$_{1}$, . . . , x$_{N}$ ) and ⃗y = ( y$_{1}$, . . . , y$_{N}$ ). The approximation in (A.8) 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.8) goes to 0 as N → ∞ , as long as lim$_{N}$$_{→∞}$ m √ N = 0. Thus, 

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

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

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

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

To prove item 2, we will use the following inequality for chi-square distributions, which appears in equation (4.3) of Laurent and Massart (2000): for U a χ 2 statistic with D degrees of freedom, for any positive x , Pr ( U − D ≥ 2 √ Dx + 2 x ) ≤ e − $^{x}$. 

Let I be a fixed arbitrary partition of size m . Since for N large enough, under the null hypothesis, T I is approximately a χ 2 statistic with D = ( m − 1) 2 degrees of 

