An unusual setup where sampling without replacement from an infinite sequence might lead to a central limit theorem

Solution 1:

Here it is not too hard to explicitly compute the distribution of $s_{2n}$. By counting the number of $x_k$ that match $a_k$, we see that for all $x\in\{0,\ldots,n\}$, $$ P(\sqrt{2n}s_{2n}=2n-4x)=\frac{\binom{n}{x}\binom{n}{n-x}}{\binom{2n}{n}}. $$ Now it suffices to apply some local limit theorem. What we need to prove is a statement of the form: for all $$ x_n=\frac{n}{2}+\frac{\sqrt{n}t}{4}+o(\sqrt{n}), $$ it holds that $P(s_{2n}=x_n)/\sqrt{n}\to e^{-t^2/2\sigma^2}/\sqrt{2\pi\sigma^2}.$ This should not be too hard, using standard estimates such as $$ \binom{n}{\frac{n}{2}+\sqrt{n}t/4+o(\sqrt{n})}2^{-n}\sim\sqrt{\frac{2}{\pi n}}e^{-t^2/2}. $$