MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
up vote 1 down vote accepted

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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