# How good an approximation is sampling with replacement to sampling without replacement?

I'm learning about probability with Feller's book and he states that, when the population size $n$ is big in comparison with the sample size $r$, then $n_r$, which is a shorthand for $\frac{ n!}{(n-r)!}$, is very close to $n^r$. This is very clear.

What I was curious about was to find a heuristic to how big $n/r$ should be in order to have a good approximation. I reached the conclusion that $$|n_r / n^r - 1| < r^2/n$$ , when $r^2 / n$ is small.

The question is if this heuristic is well known and if there is a better simple bound on the above difference.

• Can you please check your statements and definitions; they cannot all be correct. In particular, if $n_r = n!/r!$ then $n_r$ is not close to $n^r$ for $r$ small relative to $n$. e.g. consider $n=100$ and $r=2$. Then $100!/2!$ is not at all close to $100^2$. However, $100!/98!$ is of the same order as $100^2$ (i.e. their ratio is close to 1). Jun 11, 2018 at 4:57
• Sorry, you are right. The right definition is of course $n!/(n-r)!$. I corrected above. Jun 11, 2018 at 16:32

My answer largely relates to the second part but I may come back with a few words on the first part later (once the notation in the question is clarified)

A common rule of thumb when approximating the hypergeometric by the binomial (which is at heart what we're talking about) is that the sample should be smaller than 10% of the population (another common one says the sample fraction should be no more than 5%).

We can work out the degree of approximation that involves for large samples (large enough for a normal approximation to hold in both cases) by comparing standard deviations (we can then get implied ratios of densities or upper tail areas or differences in cdfs or whatever is desired at some given value of the argument from that).

The ratio of the standard deviations is directly incorporated into the finite population correction factor:

$\text{FPC} =\sqrt{\frac{N-n}{N-1}}$, which in your notation is $\sqrt{\frac{n-r}{n-1}}=\sqrt{1-\frac{r-1}{n-1}}\approx \sqrt{1-\frac{r}{n}}=\sqrt{1-f}$ when $n\gg r\gg 1$, where $f$ is the sampling fraction, $r/n$. When $r$ is small compared to $n$ this is approximately $1-\frac{f}{2}$, so requiring $f$ be no more than 10% is the same as tolerating up to a 5% error in the standard deviation; if you want no more than a 1% error in the standard deviation, this suggests that $r$ should be no more than 2% of $n$, and so forth.

Quite a few posts on site discuss the finite population correction.

• Thanks! I think that a name for the correction was exactly what I was looking for. By being such an elementary subject, I figured out that there should be some quite well established results in this regard, and specific terminology is even better, since it allows me to search directly for it. I'm trying to understand and learn more about estimation techniques, since the graduate probability course I'm taking delves deep into technical details, and I'm feeling a lack of intuition for what kind of conclusions I should look for when studying a probability problem (like, say, "random graphs"). Jun 11, 2018 at 19:37
• I have some specific things to add on $n_r/n^r$ (via Stirling's series and related approximations, and the series expansion for $(1+x/n)^n/e^x$) but may not get to it for some hours; it simplifies right down. It should even be possible to get simple bounds for the latter expansion, which would enable us to write bounds on $n_r/n^r$ though I may not get that far. Jun 11, 2018 at 21:22