Doob Martingales in Sampling Without Replacement

From a Random Sample to a Martingale

Suppose a finite population has known values, but its order is random, and we plan to take a sample of fixed size without replacement. Before any draws, the sample total is uncertain. As values are revealed, its conditional expected total changes. The sequence of these expectations is a Doob martingale: each value is the best prediction of the final sample total given the information revealed so far.

Let the population consist of \(n\) labelled individuals with fixed real values \(a_1,\dots,a_n\), and let \(T=\sum_{i=1}^n a_i\). Labels distinguish individuals even if some have equal values. Take as probability space \((\Omega,\mathcal{F},\mathbb{P})\), where \(\Omega\) is the set of all \(n!\) orderings of the individuals, \(\mathcal{F}\) is the collection of all subsets of \(\Omega\), and \(\mathbb{P}\) assigns probability \(1/n!\) to each ordering. Let \(X_k\) be the value of the individual in position \(k\), and let \(\mathcal{F}_k=\sigma(X_1,\dots,X_k)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Thus \(\mathcal{F}_k\) records the first \(k\) revealed values. Fix a sample size \(r\) with \(1\le r<n\), and let \(Y=\sum_{j=1}^r X_j\) be the final sample total.

The Conditional-Expectation Formula

Write \(S_k=\sum_{j=1}^k X_j\), with \(S_0=0\). After \(k\) draws, there are \(n-k\) individuals left, their total value is \(T-S_k\), and \(r-k\) of them will be included in the sample. By symmetry, each remaining individual has the same conditional probability of being among those \(r-k\) selected. This gives a direct formula for \(M_k\).

Proof. Fix \(k\) and any possible history of the first \(k\) labelled individuals. Conditional on that history, every ordering of the remaining \(n-k\) individuals is equally likely. In particular, the set of the next \(r-k\) individuals is uniformly distributed over all subsets of size \(r-k\) from the remaining population. For any particular remaining individual, the fraction of these subsets that contain it is $$ \frac{\binom{n-k-1}{r-k-1}}{\binom{n-k}{r-k}}=\frac{r-k}{n-k}. $$ Therefore the expected sum of the values in the next \(r-k\) positions is \(\frac{r-k}{n-k}(T-S_k)\). Adding the already observed total \(S_k\) proves the formula for \(M_k\). At \(k=r\), the coefficient is zero, so \(M_r=S_r=Y\).

To obtain the update, put \(N=n-k\), \(a=r-k\), \(R=T-S_k\), and \(x=X_{k+1}\). Since \(k<r<n\), both \(N-1\) and \(a-1\) are defined, and \(N-1>0\). The formula at the two successive stages gives $$ M_k=S_k+\frac{a}{N}R,\qquad M_{k+1}=S_k+x+\frac{a-1}{N-1}(R-x). $$ Subtracting, the coefficient of \(x\) is \(1-\frac{a-1}{N-1}=\frac{N-a}{N-1}\), while the coefficient of \(R\) is \(\frac{a-1}{N-1}-\frac{a}{N}=-\frac{N-a}{N(N-1)}\). Since \(N-a=n-r\), this yields the stated update.

It remains to check the martingale condition. Conditional on \(\mathcal{F}_k\), each of the \(n-k\) remaining individuals is equally likely to be drawn next. Hence $$ \mathbb{E}[X_{k+1}\mid\mathcal{F}_k]=\frac{T-S_k}{n-k}. $$ The update formula therefore gives \(\mathbb{E}[M_{k+1}-M_k\mid\mathcal{F}_k]=0\), or equivalently \(\mathbb{E}[M_{k+1}\mid\mathcal{F}_k]=M_k\). Each \(M_k\) is integrable because the population is finite and its values are finite. Thus the sequence is a martingale. \(\square\)

The update has a useful interpretation. It is proportional to the difference between the draw just observed and the mean of the individuals still available just before that draw. A draw above the remaining-population mean raises the prediction; a draw below it lowers the prediction. The factor \((n-r)/(n-k-1)\) accounts for how much of the final sample remains to be selected.

Worked Updates

Boundary Cases and a Common Error

The formula above assumes \(1\le r<n\), which ensures its denominator \(n-k\) is positive throughout \(0\le k\le r\). If \(r=0\), the sample total is identically zero and all conditional expectations are zero. If \(r=n\), the sample total is the fixed population total \(T\), so every conditional expectation is \(T\); the displayed formula need not be used at \(k=n\), where its denominator would vanish. These cases are deterministic and do not require the update formula.

Common mistake: keeping the original population size in the denominator. In the first example, after observing \(2\), one might incorrectly calculate \(M_1=2+\frac{1}{4}(26-2)=8\), using \(n=4\) rather than the three individuals remaining. This is wrong: one of the remaining three, not one quarter of the original population, supplies the final sample position. The correct conditional expected additional value is \((5+8+11)/3=8\), so the correct prediction is \(M_1=2+8=10\). The denominator must count the individuals still available at the time of the conditional expectation.

This construction is useful whenever a statistic of a random sample is revealed sequentially. The conditional expectation starts at the unconditional mean of the final statistic and ends at the statistic itself. In sampling without replacement, the remaining values are dependent across draws, but the uniform-ordering argument gives the conditional mean directly; independence of the draws is neither assumed nor needed.