Fix the finite sets $\mathcal{X}$ and $\mathcal{Y}$, and probability mass functions $P_X(x)$ and $P_Y(y)$ on these sets. Assume each value of $P_X(x)$ and $P_Y(y)$ is rational.

For each $n$ such that $nP_X(x)$ and $nP_Y(y)$ are integer-valued, let $(X_1,\cdots,X_n)$ be a random sequence with $nP_X(x)$ occurences of each $x \in \mathcal{X}$ (all such sequences being equally likely), and let $(Y_1,\cdots,Y_n)$ be a random sequence with $nP_Y(y)$ occurences of each $y \in \mathcal{Y}$ (all such sequences being equally likely). [NOTE: This distribution can be obtained by applying a random permutation to any such sequence].

Fix a bounded function $f(x,y) : (\mathcal{X} \times \mathcal{Y}) \to \mathbb{R}$, and let $S_n = \sum_{i=1}^n f(X_i,Y_i)$. Does the distribution of $\frac{S_n - \mathbb{E}[S_n]}{\sqrt{\mathrm{Var}[S_n]}}$ tend to $N(0,1)$ as $n \to \infty$? If so, what can be said about the rate of convergence?

It is worth noting that if the $X_i$ and $Y_i$ were i.i.d. on $P_X$ and $P_Y$ then $\frac{S_n - \mathbb{E}[S_n]}{\sqrt{\mathrm{Var}[S_n]}}$ would tend to $N(0,1)$ by the Central Limit Theorem. Furthermore, by the Berry-Esseen Theorem, its distribution function $F_n$ would satisfy $$\Big| F_n(z)-\Phi(z) \Big| = O\big(n^{-\frac{1}{2}}\big)$$ uniformly in $z$, where $\Phi$ is the distribution function of $N(0,1)$.


1 Answer 1


I think I found the answer actually - in the paper "A Combinatorial Central Limit Theorem" (Hoeffding, 1951)

The above setting seems to be recovered by letting $c_n(i,j)$ equal $f(x,y)$ for $P_X(x)P_Y(y)n^2$ values in the $(i,j)$ grid.

Then the function $d_n(i,j)$ in Eq. (8) can be written as a function of $(x,y)$ as $$d_n(x,y) = f(x,y)-\sum_{\overline{x}}P_X(\overline{x})f(\overline{x},y)-\sum_{\overline{y}}P_Y(\overline{y})f(x,\overline{y})+\sum_{\overline{x},\overline{y}}P_X(\overline{x})P_Y(\overline{y})f(\overline{x},\overline{y})$$ which is easily seen to satisfy Eq. (12).

EDIT: See also "An Estimate of the Remainder in a Combinatorial Central Limit Theorem" (Bolthausen, 1984)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.