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



Central Limit Theorem for additive function of permutations of sequences
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)


