Drawn without putting back

An urn holds 100 balls, 30 of them red. Draw 40 and count the red ones. Put each ball back before the next draw and the count is binomial: forty independent trials, each red with probability $0.3$. Keep each ball out once it is drawn, as every real sampling procedure does, and the draws are no longer independent — the chance that the second ball is red depends on whether the first one was.

Every bound in how far from the average a thing can be and its successors was proved for independent draws, or, in no single input can move it far, for functions of independent inputs. A sample without replacement satisfies neither hypothesis. It is a sequence of forty dependent draws, and the red count is not a function of forty independent choices in any obvious way. The question is what survives.

The answer is everything, and more. The dependence between draws is of one particular kind — each red ball drawn makes the next draw a little less likely to be red — and that kind pulls the count towards its average rather than away. The distribution without replacement is narrower than the binomial, every bound proved for the binomial holds for it unchanged, and the size of the improvement is an exact factor that depends only on how much of the urn was taken.

Each ball drawn leaves the urn a little less red #

Both counts average 12, which is forty times three-tenths. That part needs no calculation: whether or not balls go back, each individual draw is red with probability exactly $0.3$ when nothing is known about the others, so the expected count is $40 \times 0.3$ either way.

The spread differs. With replacement the standard deviation is $\sqrt{40 \cdot 0.3 \cdot 0.7} = 2.90$. Without, it is 2.26 — the solid bars are visibly taller in the middle and thinner in the tails. Forty balls from a hundred is a large share of the urn, so the effect is large; it is present at every sample size.

The mechanism is a correlation. Let $X_i$ be 1 if the $i$th ball is red. Any two draws $X_i$ and $X_j$ are negatively correlated: given that the first was red, the urn holds 29 red among 99, and the second is red with probability $29/99 < 30/100$. The covariance of any pair works out to $-p(1-p)/(N-1)$, with $p = 0.3$ and $N = 100$. The variance of a sum is the sum of the variances plus twice the sum of the covariances, and with $n$ draws there are $n(n-1)/2$ pairs, all with the same negative covariance. Collected together, the variance is

$$\operatorname{Var} = np(1-p)\,\frac{N - n}{N - 1}.$$

The factor $(N-n)/(N-1)$ is called the finite-population correction.

The smallest urn shows it by counting. Take four balls, two red, and draw two. With replacement there are sixteen equally likely ordered pairs: both red in 4, one red in 8, none in 4, so the count is 0, 1 or 2 with probabilities $frac14, frac12, frac14$ and variance $frac12$. Without replacement there are twelve ordered pairs of distinct balls: both red in 2, one red in 8, none in 2, so the probabilities are $frac16, frac23, frac16$ and the variance is $frac13$. The ratio is $frac23$, which is $(4-2)/(4-1)$. The pairs that went missing are the four in which a ball was drawn twice, and every one of them was an extreme — both red or both white — because a ball drawn twice matches itself. For 40 balls from 100 it is $60/99 = 0.606$, which is the ratio of $2.26^2$ to $2.90^2$.

One draw is the same either way, the whole urn has no spread #

The figure computes the ratio of the two variances from the exact distributions — no formula assumed — for every sample size from one ball to the whole urn, and every point lands on the straight line $(N - n)/(N - 1)$.

The two ends of the line are worth reading. At $n = 1$ the factor is 1: a single draw cannot be affected by draws that have not happened, so with and without replacement agree. At $n = N$ the factor is 0: drawing the whole urn yields all 30 red balls every time, so the count has no spread at all. With replacement, drawing a hundred times from an urn of a hundred still leaves a standard deviation of 4.6 — some balls are drawn twice and some never — and without replacement it leaves none. The number never drawn is large: on average $100 \times (1 - 1/100)^{100} \approx 36.6$ balls are missed entirely, which is the question how long until every one turns up answers from the other side — with replacement, seeing every ball takes on average $N(1 + \tfrac12 + \cdots + \tfrac1N)$ draws, about 519 here, where without replacement it takes exactly $N$. In between the variance falls linearly, so half the urn halves it.

This is also why the correction is usually ignored, and rightly. When the sample is a small share of the population the factor is near 1: a sample of 1,000 from a population of a million has a factor of 0.999. The dependence is real at every size, but it matters in proportion to the share of the population taken.

Hoeffding’s theorem: every convex measure of spread shrinks #

A variance is one measure of spread. A tail bound needs others, and the whole method behind the bounds of the tail is not a bell and no single input can move it far runs through the moment generating function, $\mathbb{E}\,e^{\lambda(X - \mu)}$, for every $\lambda$. If the variance shrinks but the generating function does not, nothing follows.

Hoeffding settled it in the same 1963 paper that proved his inequality. For any continuous convex function $f$, the expected value of $f$ of the sum is no larger without replacement than with. The variance is the case $f(x) = (x - \mu)^2$; the generating function is the case $f(x) = e^{\lambda(x - \mu)}$, for each $\lambda$. So every quantity that the Chernoff method reads is at least as small for the sample without replacement.

The figure checks the statement for $\lambda$ from $-1$ to $1$ on the urn: the curve without replacement never rises above the one with. At $\lambda = 1$ the gap is large — 2.57 against 4.63, a factor of about eight in the generating function itself. The dashed ceiling is Hoeffding’s lemma, $\lambda^2 n/8$, which bounds any sum of $n$ independent terms confined to $[0, 1]$, and it is what his inequality is built from. Since the binomial curve sits under the ceiling and the hypergeometric curve under the binomial, the inequality $\Pr(|X/n - p| \ge t) \le 2e^{-2nt^2}$ holds for the sample without replacement exactly as stated.

The proof has an idea that can be stated without its details. Hoeffding showed that the sum with replacement can be built as the sum without replacement plus extra noise whose average is zero, whatever value the first sum took. Adding noise of that kind can only raise the average of a convex function — that is Jensen’s inequality, applied one value of the first sum at a time — so the sum with replacement is the more spread-out of the two, in every convex sense at once. The noise is the repetition: a sample with replacement uses some balls twice and misses others, and those duplications and omissions scatter the sum around the value an honest census of distinct balls would give.

The tails, and a bound that knows the urn is finite #

The two exact tails separate quickly. A share of red off by at least $0.15$ — six balls from the average — has probability 0.056 with replacement and 0.013 without. At $0.3$, twelve balls off, the probabilities are $8.1 \times 10^{-5}$ and $1.2 \times 10^{-7}$, a factor of nearly seven hundred. Hoeffding’s bound, which is the same for both, promises $1.5 \times 10^{-3}$ there. It holds, and it is loose for both, but it is looser still for the sample that actually gets drawn.

Robert Serfling showed in 1974 that the finite urn can be written into the bound. His version divides the exponent by $1 - (n - 1)/N$, the dashed line of the earlier figure: $\Pr(X/n - p \ge t) \le \exp\!\left(-2nt^2 / (1 - (n-1)/N)\right)$. For 40 balls from 100 the exponent grows by a factor of about 1.64. The figure shows the result crossing the exact binomial tail near $t = 0.21$ and staying below it. Beyond that point the bound proved for sampling without replacement is smaller than the true probability of the same event with replacement, which no bound that ignores the urn’s size could ever be.

Serfling’s factor is slightly weaker than the exact variance factor — $1 - (n-1)/N$ against $(N-n)/(N-1)$ — and sharper versions exist. What matters for the reader of a bound is the shape of the dependence: when the sample is a large share of the population, the correct bound is much stronger than the independent one, and the independent one is still correct.

A poll of a thousand, in a town and in a nation #

The most familiar sample without replacement is an opinion poll. Nobody is asked twice, the population is finite, and the published margin of error is a statement about the tail of exactly this distribution.

The margin for a thousand people, with the usual 1.96 standard deviations, is $\pm 3.10$ percentage points when the population is unlimited. In a nation of a hundred million it is the same to two decimal places. In a city of a hundred thousand it is $\pm 3.08$, in a town of twenty thousand $\pm 3.02$, and only when the sample becomes a large share of the population does it move much: $\pm 2.19$ in a town of two thousand, and zero when all thousand residents of a town of a thousand are asked.

That is the arithmetic behind a fact that surprises almost everyone who meets it. The accuracy of a random sample depends on the sample’s size and almost not at all on the population’s. A poll of a thousand is as good in a country of three hundred million as in a city of one million. Intuition says a bigger population needs a bigger sample, and the finite-population correction says the opposite — a smaller population needs a slightly smaller sample for the same accuracy, because what the sample leaves out is a smaller share of the whole.

The correction earns its keep where samples are a large share of what they describe. An auditor who checks 200 of a firm’s 500 invoices for errors is sampling 40% of the population, and the variance factor is $300/499 = 0.60$; the margin of error is multiplied by its square root, $0.78$, so the honest interval is 22% narrower than the textbook formula for independent draws gives. The same holds for a quality inspector testing a fifth of a batch, or an ecologist surveying half the ponds in a valley. In each case the formula that ignores the correction is safe and wasteful at once: it never understates the error, and it asks for more sampling than the question needs.

None of this addresses the errors that dominate real polls: who answers the phone, who lies, who changes their mind. The margin of error is a statement about random sampling alone, and it is honest only about that. What the finite-population correction adds is that the sampling error of a well-drawn poll is, if anything, overstated by the formula everybody uses.

Where the argument reaches further #

Hoeffding’s comparison is not about urns specifically. It holds for any finite list of numbers sampled without replacement, not just zeros and ones — the list of household incomes in a town, the running times of a program on a fixed set of inputs, the weights of the parts in a batch. Whatever the list, the sample sum without replacement is dominated in the convex order by the sum with replacement, so every exponential bound for independent sampling applies.

The same shape of argument covers a random permutation. Shuffle a list and take the first $n$ entries, and the result is exactly a sample without replacement, so the sum of the first $n$ entries of a random shuffle concentrates at least as well as $n$ independent draws. The median of many small averages cut a sample into blocks; if the blocks are formed by shuffling a fixed dataset rather than drawing fresh samples, this is what licenses treating them as if they were independent.

It also covers the most common use of random sampling in computation. Estimating a number by sampling needs an error bound, and a program that estimates an average over a fixed, finite set of cases — every input in a test suite, every record in a table — usually samples those cases without repeating one. The bound for independent sampling is the one quoted, and Hoeffding’s theorem is what makes quoting it honest; the true error is smaller, by a margin that becomes large once the sample is a sizeable share of the table.

What does not carry over is the independence itself. Two blocks formed by splitting one shuffle are negatively correlated with each other — a block that happens to be high leaves the other lower — so a statement about their joint behaviour needs its own argument. Hoeffding’s theorem compares one sum with one sum; it does not turn a dependent family into an independent one.

Still open: which dependence is safe #

The urn worked because its draws are dependent in one particular direction. Kumar Joag-Dev and Frank Proschan named the property in 1983: the indicators of a sample without replacement are negatively associated, meaning that any increasing function of some of them and any increasing function of the others are negatively correlated. Devdatt Dubhashi and Desh Ranjan showed in 1998 that negative association alone is enough for the Chernoff–Hoeffding bounds — the urn’s proof is one instance of a general rule that the helpful kind of dependence never costs a bound anything.

That raises the question of which random structures have it, and the answer runs into an open problem quickly. Choose a spanning tree of a graph uniformly at random and let each edge’s indicator record whether it is in the tree. Those indicators are negatively associated — Tomás Feder and Milena Mihail proved it in 1992 — and in 2014 Robin Pemantle and Yuval Peres proved that every Lipschitz function of them concentrates as a sum of independent terms would. A uniform spanning tree is, in this sense, an urn.

Now choose a spanning forest uniformly at random — any subset of edges containing no cycle. It is conjectured that the edges are negatively correlated here too: that knowing one edge is present makes any other edge less likely. Geoffrey Grimmett and Stephan Winkler checked it by computer on every graph with up to eight vertices in 2004. Whether it holds in general is open, and so is the stronger negative association that would bring the concentration bounds with it. The forest is not an exotic object — it is the tree with one constraint removed — and the difference between the two is the difference between a theorem and a conjecture.

What the figures do not settle #

Every number here is computed exactly from binomial and hypergeometric probabilities for a single urn, 100 balls with 30 red, and a single poll size. The variance factor is proved above for every urn; the figures confirm it for one. Hoeffding’s convex-order theorem and Serfling’s inequality are quoted with their authors and dates, and the figures check that they hold on this urn for every $\lambda$ and every $t$ drawn — a check that could have failed and did not, not a proof.

The poll figure assumes simple random sampling, an evenly split question and the normal approximation that the 1.96 comes from. For a thousand respondents that approximation is accurate to well under a tenth of a point; for small samples, or proportions near 0 or 1, the exact hypergeometric tail should be used instead, and the variance-based bounds of how far from the average a thing can be are the ones that hold without any approximation at all.