A Doob Martingale for a Coin-Toss Total

Predicting a Total as Information Arrives

Suppose a finite sequence of independent coin tosses is made, but the outcomes are revealed one at a time. Before any toss is known, the expected total number of heads is the sum of the head probabilities. After some tosses are observed, the conditional expectation adjusts: it counts the heads already seen and adds the expected number among the tosses still hidden. The resulting sequence of predictions is a martingale.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. For a fixed positive integer $n$, let $X_1,\ldots,X_n$ be independent Bernoulli random variables, where $X_i=1$ denotes heads and $X_i=0$ denotes tails. Write $\mathbb{P}(X_i=1)=p_i$, with $0\le p_i\le1$, and define the total $Z=\sum_{i=1}^n X_i$. The common-probability case has $p_i=p$ for every $i$.

Definition: The information after the first $k$ tosses is the sigma-field $\mathcal{F}_k=\sigma(X_1,\ldots,X_k)$, for $1\le k\le n$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. The Doob martingale of the total $Z$ with respect to this filtration is $M_k=\mathbb{E}[Z\mid\mathcal{F}_k]$, for $0\le k\le n$. Conditional-expectation equalities are understood almost surely.

Each $M_k$ is the best conditional-mean prediction of the final total given the tosses observed so far. Independence ensures that the conditional expected number of heads among the unrevealed tosses remains $\sum_{i=k+1}^n p_i$. Thus the prediction has an explicit form.

Theorem (Coin-toss Doob martingale): For independent Bernoulli tosses with probabilities $p_1,\ldots,p_n$, the conditional expectations are $$ M_k=\sum_{i=1}^k X_i+\sum_{i=k+1}^n p_i,\qquad 0\le k\le n, $$ where an empty sum is zero. In particular, $M_0=\sum_{i=1}^n p_i$, $M_n=Z$, and $$ M_k-M_{k-1}=X_k-p_k,\qquad 1\le k\le n. $$ With the filtration $(\mathcal{F}_k)_{k=0}^n$, $(M_k)$ is an integrable martingale.

Proof. Fix $k$. The sum $Z$ separates into the observed part $\sum_{i=1}^k X_i$ and the unrevealed part $\sum_{i=k+1}^n X_i$. The observed part is $\mathcal{F}_k$-measurable, so its conditional expectation given $\mathcal{F}_k$ is itself. Each $X_i$ with $i>k$ is independent of $\mathcal{F}_k$, because the tosses are mutually independent; hence $\mathbb{E}[X_i\mid\mathcal{F}_k]=\mathbb{E}[X_i]=p_i$. Linearity of conditional expectation gives the stated formula, including the cases $k=0$ and $k=n$. Subtracting the formulas at $k$ and $k-1$ cancels all terms except $X_k-p_k$. Every $M_k$ is integrable because it is bounded between $0$ and $n$. Finally, $M_k$ is $\mathcal{F}_k$-measurable, and $$ \mathbb{E}[M_k\mid\mathcal{F}_{k-1}] =\mathbb{E}[\mathbb{E}[Z\mid\mathcal{F}_k]\mid\mathcal{F}_{k-1}] =\mathbb{E}[Z\mid\mathcal{F}_{k-1}] =M_{k-1}, $$ by the tower property, since $\mathcal{F}_{k-1}\subseteq\mathcal{F}_k$. These are the defining conditions for a martingale. $\square$

The update formula makes the mechanism especially transparent. If toss $k$ is heads, the prediction changes by $1-p_k$: one head is now certain, but the expected contribution $p_k$ from that toss is no longer part of the future prediction. If it is tails, the prediction changes by $-p_k$. These statements also cover $p_k=0$ or $p_k=1$; an outcome with probability zero simply does not occur, while the algebraic update formula remains valid.

Worked Updates

Worked Example: Five Fair Tosses

Five independent fair tosses are made. Suppose the observed sequence, in order, is heads, tails, heads, tails, heads. Compute the prediction after each toss and check the updates.

Here $n=5$ and $p_i=\tfrac12$ for every $i$. After $k$ tosses with $h_k$ observed heads, the formula gives $M_k=h_k+\tfrac{5-k}{2}$. The computations are

\begin{aligned} M_0&=0+\tfrac52=\tfrac52,\\ M_1&=1+\tfrac42=3,\\ M_2&=1+\tfrac32=\tfrac52,\\ M_3&=2+\tfrac22=3,\\ M_4&=2+\tfrac12=\tfrac52,\\ M_5&=3+0=3. \end{aligned}

The updates are $M_1-M_0=\tfrac12$, $M_2-M_1=-\tfrac12$, $M_3-M_2=\tfrac12$, $M_4-M_3=-\tfrac12$, and $M_5-M_4=\tfrac12$. These agree toss by toss with $X_k-\tfrac12$: heads gives $1-\tfrac12$, and tails gives $0-\tfrac12$. Check: the final sequence contains three heads, so $Z=3=M_5$. The sum of the five updates is $\tfrac12-\tfrac12+\tfrac12-\tfrac12+\tfrac12=\tfrac12$, which also equals $M_5-M_0=3-\tfrac52=\tfrac12$.

Worked Example: An Attainable Prediction with Biased Tosses

Six independent tosses each have head probability $\tfrac14$. After three tosses, suppose exactly one head has been observed. Find the conditional expectation of the final total, and compute the possible next updates.

With $k=3$ and one observed head, the prediction is the observed head plus the expected number of heads in the three remaining tosses: $$ M_3=1+3\left(\tfrac14\right)=1+\tfrac34=\tfrac74. $$ If the fourth toss is heads, then two heads have been observed and two tosses remain, giving $$ M_4=2+2\left(\tfrac14\right)=2+\tfrac12=\tfrac52. $$ The update is $\tfrac52-\tfrac74=\tfrac{10}4-\tfrac74=\tfrac34=1-\tfrac14$. If the fourth toss is tails, then $$ M_4=1+2\left(\tfrac14\right)=1+\tfrac12=\tfrac32, $$ and the update is $\tfrac32-\tfrac74=\tfrac64-\tfrac74=-\tfrac14=0-\tfrac14$.

Check by conditional averaging: given the first three tosses, the fourth is heads with probability $\tfrac14$ and tails with probability $\tfrac34$. Therefore $$ \mathbb{E}[M_4\mid\mathcal{F}_3] =\tfrac14\left(\tfrac52\right)+\tfrac34\left(\tfrac32\right) =\tfrac58+\tfrac98=\tfrac{14}8=\tfrac74=M_3. $$ The prediction before the fourth toss is exactly the probability-weighted average of the two possible predictions after it.

Worked Example: Different Probabilities for Different Tosses

Let four independent tosses have head probabilities $p_1=\tfrac12$, $p_2=\tfrac13$, $p_3=\tfrac34$, and $p_4=\tfrac14$. Suppose the observed outcomes are tails, heads, tails, heads. Compute the full prediction sequence.

The initial prediction is the sum of all four probabilities: $$ M_0=\tfrac12+\tfrac13+\tfrac34+\tfrac14 =\tfrac12+\tfrac13+1=\tfrac{11}6. $$ After the first toss is tails, the observed total is zero and the remaining probabilities sum to $\tfrac13+\tfrac34+\tfrac14=\tfrac43$, so $M_1=\tfrac43$. After the second toss is heads, the observed total is one and the remaining probabilities sum to $\tfrac34+\tfrac14=1$, so $M_2=2$. After the third toss is tails, $M_3=1+\tfrac14=\tfrac54$. After the last toss is heads, the total is two and there are no tosses left, so $M_4=2$.

Check the updates: their successive values are $$ M_1-M_0=-\tfrac12,\quad M_2-M_1=\tfrac23,\quad M_3-M_2=-\tfrac34,\quad M_4-M_3=\tfrac34. $$ The actual tosses give $X_1-p_1=0-\tfrac12$, $X_2-p_2=1-\tfrac13$, $X_3-p_3=0-\tfrac34$, and $X_4-p_4=1-\tfrac14$, the same four values. Their sum is $-\tfrac12+\tfrac23-\tfrac34+\tfrac34=\tfrac16$, which agrees with $M_4-M_0=2-\tfrac{11}6=\tfrac16$.

Mean and Variance of the Updates

The update $D_k=M_k-M_{k-1}=X_k-p_k$ has conditional mean zero given the previous tosses. Its conditional variance is $p_k(1-p_k)$. For this finite sequence, these facts also give a direct variance calculation for the final total.

Proposition: Under the independent Bernoulli assumptions above, $\mathbb{E}[M_k]=\mathbb{E}[Z]=\sum_{i=1}^n p_i$ for every $k$, and $$ \operatorname{Var}(Z)=\sum_{k=1}^n p_k(1-p_k). $$ Moreover, for $i\ne j$, $\mathbb{E}[(M_i-M_{i-1})(M_j-M_{j-1})]=0$.

Proof. The explicit expression for $M_k$ gives $$ \mathbb{E}[M_k]=\sum_{i=1}^k\mathbb{E}[X_i]+\sum_{i=k+1}^n p_i =\sum_{i=1}^n p_i=\mathbb{E}[Z]. $$ For each increment $D_k=X_k-p_k$, the Bernoulli identity $X_k^2=X_k$ gives $$ \mathbb{E}[D_k^2]=\mathbb{E}[X_k^2]-2p_k\mathbb{E}[X_k]+p_k^2 =p_k-2p_k^2+p_k^2=p_k(1-p_k), $$ and $\mathbb{E}[D_k]=0$. If $i<j$, then $D_i$ is $\mathcal{F}_{j-1}$-measurable, while $\mathbb{E}[D_j\mid\mathcal{F}_{j-1}]=0$. Consequently, $$ \mathbb{E}[D_iD_j] =\mathbb{E}\!\left[D_i\,\mathbb{E}[D_j\mid\mathcal{F}_{j-1}]\right]=0. $$ For $j<i$, the same conclusion follows by exchanging the two factors. Since $Z=M_0+\sum_{k=1}^n D_k$, with $M_0$ deterministic, expanding the square of $Z-\mathbb{E}[Z]=\sum_kD_k$ leaves only the squared-increment terms: every cross-term has expectation zero. Thus $\operatorname{Var}(Z)=\sum_k\mathbb{E}[D_k^2]=\sum_kp_k(1-p_k)$, as claimed. $\square$

This identity gives an additional check on the construction: the uncertainty in the final total is the sum of the variances contributed by the individual independent tosses. The martingale makes those contributions visible one at a time, through its centered increments.

Why the Construction Is Useful—and a Common Mistake

The sequence $(M_k)$ separates what is already known from what remains uncertain. At time $k$, the value is not generally the number of heads seen; it is that number plus the expected number of future heads. At time $n$, no uncertainty remains and the prediction equals the actual total. The martingale property says that, before the next toss is revealed, the average of the possible updated predictions equals the current prediction. It does not say that each realized update is zero, or that a particular path must move steadily toward its final value.

Common mistake: accepting an impossible prediction. In the six-toss example with $p=\tfrac14$, after three tosses the formula is $M_3=h+\tfrac34$, where the observed head count $h$ must be one of $0,1,2,3$. Thus the only possible values are $\tfrac34,\tfrac74,\tfrac{11}4,\tfrac{15}4$. A mistaken calculation might set $M_3=\tfrac32$, subtract $\tfrac34$, and report $h=\tfrac34$ heads. That cannot happen: a count of heads must be an integer. The corrected attainable value $M_3=\tfrac74$ gives $h=\tfrac74-\tfrac34=1$ observed head. Checking attainable values is a useful safeguard whenever interpreting a conditional expectation as a count plus a future mean.

For equal probabilities $p$, the formula simplifies to $M_k=S_k+(n-k)p$, where $S_k=\sum_{i=1}^kX_i$ is the number of heads already observed. The remaining expected contribution is $(n-k)p$, not $p$ and not the number of tosses still to come. Keeping those two parts distinct prevents both arithmetic errors and conceptual confusion.

Check Your Understanding

Use the conditional-expectation formula and verify each update from the newly revealed toss.

For four fair tosses, suppose the first two outcomes are tails and heads. Compute $M_0$, $M_1$, and $M_2$.
For five independent tosses with common head probability $\tfrac13$, what are the possible values of $M_2$? State the number of heads corresponding to each value.
For independent tosses with probabilities $\tfrac12$ and $\tfrac14$, compute the two possible values of $M_1$ after the first toss and check their conditional average before that toss.
Explain why $M_k$ is not generally equal to the number of heads seen by time $k$.
For $n$ independent Bernoulli tosses with probabilities $p_i$, state the increment $M_k-M_{k-1}$ and its conditional mean given $\mathcal{F}_{k-1}$.

A Doob Martingale for a Coin-Toss Total

What You'll Learn