Central limits without replacement in a finite population.

Question

"Everybody knows" that there are lots of variations on the theme of the central limit theorem. The most frequently seen form seems to be this: Suppose $X_1,X_2,X_3,\ldots$ are i.i.d. random variables and $\sigma^2=\operatorname{var}(X_1)<\infty$ and $\mu=\mathbb E(X_1)$. Then for all real $x$, $$ \lim_{n\to\infty} \Pr\left( \frac{\frac{X_1+\cdots+X_n}n -\mu}{\sigma/\sqrt n} \le x \right) = \frac 1{\sqrt{2\pi}} \int_{-\infty}^x e^{-u^2/2}\,du. $$

Now suppose $X_1,X_2,X_3,\ldots$ are sampled without replacement from a finite population. In that case the assumption of independence does not hold, but it holds approximately when $n$ is small by comparison to the size of the population. One may imagine the probability above seeming to approach the integral above, but when $n$ reaches the size of the whole population, then the sample average above is with probability $1$ equal to the population average, and the behavior of its probability distribution when $n$ is, for example $1/2$ or $3/4$ or $99/100$ of the population is unclear to me.

There must be published results about this. (?) What are they?

For which value of $n$ is the probability whose limit is taken above closest to the integral?

Answer 1

First, I think you need to fix your theorem: $\bar X = \frac{\sum X_i}{n}\sim \mathcal{N}(\mu,\frac{\sigma}{\sqrt{n}})$. You need to subtract the mean and divide by the standard deviation, so that $\sqrt{n}\frac{\bar X-\mu}{\sigma} \sim \mathcal{N}(0,1)$

That aside, the answer will depend on the underlying distribution of the population. Lets say all $X_i=1\;\forall i$ then it will never converge to the integral. Barring such degenerate distributions, you have the issue of defining your metric for "closest". The probability measure of your sample mean is a function which you are comparing to another function. Do you want to minimize the Kullback–Liebler Divergence? I think this seems like a good choice, at least theoretically.

You will need to know the underlying sampling distribution as a function of $n$ and $N$ (sample and population size, respectively), then do a nonlinear optimization where you minimize the Kullback–Liebler Divergence as a function of $n$.

Answer 2

This is 6 years late, but I came across a few versions of the central limit theorem for sampling without replacement from a finite population in context of the statistical and probabilistic study of card counting in Blackjack. Having come across this theorem in this specific context, I remember trying to find this result in more conventional mathematics references, but the references were either above my level, or did not appear easily when Googling (as comments have shown).

In the "Theory of Blackjack: The Complete Card Counter's Guide to the Casino (1990)", Peter Griffin uses an asymptotic result of the type you are looking for, and he references an arcane, hard-to-find paper, "Erdos, P. and Renyi, A. (1959). On the central limit theorem for samples from a finite population. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 4 (1) 49–57."

When I looked at this in my spare time, I found the Erdos-Renyi paper arcane and tricky to read. Furthermore, I found Peter Griffin's book, whilst comprehensive and excellent, to combine a strange mix of very informal reasoning aimed at Blackjack players, with informal mathematical notation; hence difficult for different reasons.

The version of the finite sample central limit theorem I am more familiar and comfortable with is that given in Stewart Ethier's book "The Doctrine of Chances: Probabilistic Aspects of Gambling (2010)". Here is an extract from the Appendix, p750:

Theorem A.2.13 For each $N \geq 2$, let $(X_{N,1}, X_{N,2}, \ldots , X_{N,N})$ have the discrete uniform distribution over all $N!$ permutations of the $N$ (not necessarily distinct but not all equal) numbers $x_{N,1}, x_{N,2}, \ldots, x_{N,N}$ and define $$\mu_N := \mathbb{E}[X_{N,1}] = \frac{1}{N} \sum^N_{j=1} x_{N, j} \tag{A.21}$$ and $$\sigma^2_N := \text{Var}(X_{N,1}) = \frac{1}{N} \sum^N_{j=1} (x_{N, j} - \mu_N)^2 \tag{A.22}$$ Assume that $$\max_{1 \leq j \leq N} \frac{\lvert x_{N, j} - \mu_N \rvert}{\sqrt{N \sigma^2_N}} \rightarrow 0 \tag{A.23}$$ as $N \rightarrow \infty$. Then with $S_{N, n} := X_{N,1} + \cdots + X_{N, n}$ we have $$\frac{S_{N, n} - n\mu_N}{\sqrt{n \sigma^2_N(N-n) / (N-1)}} \overset{d}\rightarrow N(0,1), \tag{A.24}$$ provided that $n/N \to \alpha \in (0,1)$. Notice that this generalises Theorem 1.5.14. One of the first results of this type was proved by Erdos and Renyi (1959); see Billingsley (1968, pp. 208-212) for a generalization.

Is this at least partially related to what you might have in mind? This is all written with the reservation that the theorems were adapted for usage to derive a modicum of formal results in Blackjack, so might make assumptions that are inappropriate for your purposes.

---

As an aside, most of my digging in this general area came from the fact that I could not understand Edward Thorp's proof for what he termed the "fundamental theorem of card counting", which he proves using a convex contraction of measure argument. I am guessing it is esoteric, because I searched for it in this Q&A and nothing came up. Because I do not know measure theory, I went to look for an easier proof, and it turned out Ethier provides a simpler proof using martingales and Jensen's inequality in his book.

There are asymptotic/CLT results which may be relevant to your query and go somewhat further than what is stated in Ethier's book for the analysis of Blackjack, which I haven't time to go through, and for which I wanted to post a question on here when I managed to get back to it. However I've been hesitant to post on this Q&A in general, so I've left it on the back-burner. The paper is "Ethier, S. N., & Levin, D. A. (2002). On the fundamental theorem of card counting, with application to the game of trente et quarante. Advances in Applied Probability, 37(01), 90–107," which uses a central limit theorem for U-statistics based on samples from a finite population from "Lee, A. J. (1990) U-Statistics: Theory and Practice. Marcel Dekker, New York". This latter book now has a 2019 copy.