Sampling With Or Without Replacement

Suppose that there are $a$ blue balls and $b$ red balls in a box and we would like to sample $k$ balls from them. We can sample the balls with replacement such that after picking each ball we put it back into the box, or we can do it without replacement.

For convenience of discussion, denote $n = a + b$ , $p = \frac{a}{n}$ and $q = \frac{b}{n}$ . Define $X_i$ ( $i \in [k]$ ) the indicator random variable of whether the $i$ -th selected ball is blue. Let

X = \sum X_i

Then we claim that

E[X] = \sum_{i \in [k]} E[X_i] = kp

The first equality holds by linearity of expectation. The second equality states that in expectation, $p$ fraction of the selected balls are blue.

The claim is trivial when we sample with replacement, as $\Pr[X_i = 1] = p$ . To prove that the probability applies for the case of sampling without replacement requires a little more effort, as shown by the following

There are in total $\begin{pmatrix} n \\ k\end{pmatrix}$ possible combinations of choosing $k$ balls out of $n$ .
Among them there are $\begin{pmatrix} a \\ 1 \end{pmatrix} \cdot \begin{pmatrix} n - 1 \\ k - 1 \end{pmatrix}$ combinations such that the $i$ -th ball is blue.
Therefore, $\Pr[X_i = 1] = \frac{ \begin{pmatrix} a \\ 1 \end{pmatrix} \cdot \begin{pmatrix} n - 1 \\ k - 1 \end{pmatrix} }{ \begin{pmatrix} n \\ k\end{pmatrix} } = \frac{a}{n} = p$ .

However, the two sampling scheme have different variance.

Variance of Sampling With Replacement

By independence of $X_i$

Var[X] \doteq \sigma^2 = \sum_{i \in [k]} Var[X_i] = k p q

Variance of Sampling Without Replacement

In this case, the $X_i$ 's are not independent.

\begin{aligned} Var[X] &= E \left[ X^2 \right] - \left( E[X] \right)^2 \\ &= \sum_{i \in [k]} E[X_i^2] + \sum_{i, j \in [k]} E[X_i X_j] - (kp)^2 \\ &= kp + k(k - 1) \frac{ \begin{pmatrix} a \\ 2 \end{pmatrix} \cdot \begin{pmatrix} n - 2 \\ k - 2 \end{pmatrix} }{ \begin{pmatrix} n \\ k\end{pmatrix} } - (kp)^2 \\ &= kp + k(k - 1) \frac{ a(a-1) }{ n(n - 1) } - (kp)^2 \\ &= kp + kp \frac{ (k - 1) (a-1) }{ (n - 1) } - (kp)^2 \\ &= kp ( 1 + \frac{ (k - 1) (a-1) }{ (n - 1) } - k \frac{a}{ n } ) \\ &= kp \frac{n^2 - n + ka n - kn - an + n - kan + ka }{ n (n - 1) } \\ &= kp \frac{n^2 - kn - an + ka }{ n(n - 1) } \\ &= kp \frac{(n - a) (n - k)}{ n (n - 1)} \\ &= kpq \frac{n - k}{n - 1} \\ &= \sigma^2 \frac{n - k}{n - 1} \end{aligned}

We have shown that sampling without replacement has smaller variance than sampling with replacement. Moreover, if $n \succ k$ , then $\frac{n - k}{n - 1} \approx 1$ and the two sampling scheme have almost the same variance. We can bound the concentration behavior of $X$ by Chebyshev's inequality: for any $c > 0$ ,

\Pr[ |X - E[X] | \ge c \cdot \sigma] \le \frac{Var[X] }{c^2 \sigma^2} = \frac{1}{c^2}

The $3$ -sigma rule says only $X$ deviates more than $3\sigma$ from its expectation with probability at most $11.11\%$

\Pr[ |X - E[X] | \ge 3 \cdot \sigma] \le \frac{Var[X] }{c^2 \sigma^2} = \frac{1}{9} \approx 0.1111

It is also interesting to observe that the variance most related to the sample size $k$ and probabilities $p$ and $q$ , but not $n$ !