Central Limit Theorem for additive function of permutations of sequences

Question

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

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)