Prove finite sampling guarantees with pairwise independence

Try

Distinguish a promise from an observed proportion

A synthetic inspection model records a one for a defective item and a zero otherwise. Its unknown defect probability is p. You want a sample proportion within 0.1 of p, with failure probability at most 0.05. How many observations would certify that statement without assuming a normal approximation?

First write what is random. The parameter p is fixed by the model; the average of the observations changes from sample to sample. A claim about that procedure is not a guarantee that every realized sample is close. Nor does repeatedly copying one observation create more independent information.

This lesson uses only finite sums. For a variable Y, its expectation E[Y] is the probability-weighted average of its values. Its variance is the weighted average of (Y−E[Y])². An indicator of an event is one on that event and zero elsewhere. Review the pointwise tail-bound argument if these symbols are unfamiliar.

Predict

Which kind of independence does the proof need?

Suppose every recorded bit has probability p of being one. Predict whether each statement alone is enough to make the variance of their average shrink as p(1−p)/n:

1. Every bit has the same marginal distribution.
2. Every pair of distinct bits is independent.
3. All bits are mutually independent.

The first is insufficient: use the same random bit everywhere. The second is sufficient; the third is stronger than necessary. Before reading the proof, expand the square of the sum of two centered observations. Identify exactly where a joint expectation enters. Linearity of expectation itself does not require independence.

Also predict whether “error less than 0.1” and “error at most 0.1” have the same complement. They need not: observations at the boundary matter in a discrete model.

Experiment

Enumerate dependent bits with independent pairs

Choose two independent fair bits U and V. Form X₁=U, X₂=V and X₃=U⊕V, where ⊕ means addition modulo two. Fill the last column before checking this exact table. These are all four possible inputs, each of probability 1/4; this is complete enumeration, not a simulation.

Input U,V	Output X₁,X₂,X₃	Sum	Average
0,0	0,0,0	0	0
0,1	0,1,1	2	2/3
1,0	1,0,1	2	2/3
1,1	1,1,0	2	2/3

For each selected pair of output columns, all four ordered pairs occur once. Thus every pair is independent. But all three outputs are zero with probability 1/4, not the product 1/8, so mutual independence fails. The average has mean (3/4)(2/3)=1/2 and second moment (3/4)(4/9)=1/3. Its variance is 1/3−1/4=1/12, exactly the pairwise-independent formula (1/4)/3.

Change the third output to U. Recompute the four averages: 0, 1/3, 2/3 and 1. Their variance is 7/18−1/4=5/36, larger than 1/12. The changed pair X₁,X₃ is no longer independent. Explain the difference through the cross term, not through an assertion that every form of dependence must increase variance.

The live experiment below uses seven observations, distinct from the three-output worked table. Predict what changes when one bit is copied seven times, and compare inclusive and strict tails at the same tolerance. The displayed finite enumeration is exact counting under the selected model, not evidence about a real sampling process.

The same seven fair observations can have different guarantees

Every observation is zero or one with equal probability in each design. Predict whether this alone makes the seven observations independent. The average has target mean 1/2; the error is its distance from 1/2.

Sampling designSeven independent fair bitsSeven pairwise-independent bits from three seedsOne fair bit copied seven times Error tolerance ε1/143/145/147/14 = 1/2

Reveal sampling comparisonReset sampling experiment

No results revealed. Predict the effect of dependence and the inequality endpoint first.

Compare the independent and pairwise designs at ε = 1/2, then switch to copied data. Explain which variance argument survives and which fails. This finite enumeration illustrates the proofs; it does not establish assumptions for a real survey or award mastery.

Understand

Derive a finite guarantee

Write X̄ for the average of n pairwise-independent Bernoulli observations with common mean p. A Bernoulli observation satisfies X²=X, so its variance is p−p². Expanding the centered square gives

Var(X̄) = n⁻² [Σᵢ E[(Xᵢ−p)²] + 2Σᵢ<ⱼ E[(Xᵢ−p)(Xⱼ−p)]].

Pairwise independence makes each cross expectation zero. The n remaining terms give Var(X̄)=p(1−p)/n. Completing the square shows p(1−p)=1/4−(p−1/2)²≤1/4. This is a worst-case variance bound over all possible p, not an estimate that p equals 1/2.

For any ε>0, the squared deviation is at least ε² on the event that the absolute deviation is at least ε, and is nonnegative elsewhere. Therefore, pointwise,

(X̄−p)² ≥ ε² · 1(error ≥ ε).

Taking finite expectations proves

P(error ≥ ε) ≤ p(1−p)/(nε²) ≤ 1/(4nε²).

Clip an upper bound at one when necessary. This is Chebyshev’s inequality applied to the sample average. It uses no limiting theorem, fitted standard deviation or binomial shape assumption. At p=0 or p=1 the actual variance is zero. For general p the bound may be loose.

To certify inclusive failure probability at most δ, where 0<δ<1, it suffices that n≥1/(4ε²δ). In the opening example ε=0.1 and δ=0.05, this gives n≥500. At 500 the bound is exactly 0.05, certifying strict error below 0.1 with probability at least 0.95. It does not certify a strict failure inequality by itself. The least integer certified for that stronger risk claim is 501.

Keep three endpoints separate: the inclusive failure event, its strict success complement, and a weak or strict inequality on the probability itself. An exact fair Bernoulli deviation of 1/2 supplies a boundary counterexample. Also distinguish a sufficient sample size from the actual smallest sample size for a particular distribution.

Apply

Audit the design before trusting the bound

Consider 160 recorded bits formed from 40 independent fair observations, each copied four times. Their average equals the average of the 40 original bits. Compute its variance as 1/160, not 1/640. At ε=0.2, the justified inclusive-tail bound is 5/32; pretending the copies are independent would produce 5/128. Neither fraction is asserted to be the exact tail probability. A sound repair changes the independent sampling units or accounts for the clusters; deleting a warning does not change the design.

Now estimate two binary outcomes using the same sampled rows. Within a row the outcomes may be dependent. If each outcome separately satisfies the across-row pairwise-independence assumptions, each failure probability at tolerance 0.1 is at most 25/n. The probability that either estimate fails is at most 50/n by the union bound. Thus n=500 certifies both strict errors below 0.1 with probability at least 0.90. Multiplying the two success probabilities would need an additional independence justification that we do not have.

For your written report, identify the target parameter, sampling units, independence claim, error event, risk budget and integer rounding. Supply the squared-deviation proof and a counterexample to any assumption you remove. The six practice tasks include a seven-output sampler and changed design decisions; use their review rubrics after attempting them.

Continue

Keep finite guarantees separate from approximation

Return to covariance when adding variables for the general variance expansion, or pairwise versus mutual independence for joint-law examples. The normal sample-size planning lesson answers a related question using approximation assumptions; its smaller planning number is not a replacement proof for this finite guarantee.

Finally, unbiased observations from the wrong population estimate the wrong target. Pairwise independence and a large n do not remove selection bias. Finite enumeration verifies a specified small model, while a simulation estimates frequencies under its generator. Neither establishes that a real data-collection process has the assumed joint law.