Toss a coin until you get $n$ heads in a row. Expected number of tails tossed?

You toss a fair coin until you get $$n$$ heads in a row. What is the expected number of tails you tossed?

It can be well shown that the expected number of tosses required to get $$n$$ heads in a row is $$2^{n+1}-2$$

So naturally half of this is the expected number of tails?

More formally:

Let $$H_n$$ and $$T_n$$ respectively denote the number of heads and tails you have tossed in total up to time $$n$$.

$$X_n : = H_n - T_n$$ is a martinagle. As $$X_{n+1} = X_n + C_{n+1}$$ where $$C_n = \{+1 \text{ if you tossed a head and } -1 \text{ if you tossed a tail on coin } n+1 \}$$

And $$\mathbb{E}[C_n] = 0$$ for all $$n >=1$$

Notice $$X_0$$ is $$0$$ and the stopping time $$\tau$$ to yield $$n$$ consecutive heads is a.s finite (by borell cantelli ) and in $$\mathcal{L}_1$$

Ergo by OST: $$\mathbb{E}[H_{\tau} - T_{\tau}] = \mathbb{E}[X_{\tau}] = \mathbb{E}[X_0] = 0$$

And so

$$\star \mathbb{E}[H_{\tau} ] = \mathbb{E}[T_{\tau} ]$$

We know from before that $$\mathbb{E}[H_{\tau} + T_{\tau}] = 2^{n+1} -2$$

And so using $$\star$$ $$\mathbb{E}[T_{\tau}] = \frac{1}{2} (2^{n+1} -2 ) = 2^n -1$$

Having gone through all this I feel like I used an AK-47 to swat a fly. And that all the martingale theory was not needed. Is there a simply more concise way to prove that once you know the expected number of tosses for something, the expected number of tails will simply be half that?

• In this case, letting $E_i$ be the expected number of $T's$ seen before seeing $H^i$, it is clear that $E_{n+1}=E_n+\frac 12\times 0+\frac 12\times (E_{n+1}+1)$ which quickly establishes the result you want, no need of any heavy lifting. Not clear (to me) what general statement you might hope to prove.
– lulu
Commented Oct 14, 2021 at 13:35
• this was excellent @lulu thank you. The general statement is "you cant trick a coin" that is, for any game you play at any point the expected number of heads = expected number of tails . having just wrote this i realised this exactly the same problem of OST and so we are done, (must include some finitness or bounds) Commented Oct 14, 2021 at 14:22
• That general statement is simply too general. For instance, suppose your game was "toss the coin until the number of Heads you have seen is twice the number of Tails you have seen". Any stopping point for this game breaks the underlying symmetry (obviously).
– lulu
Commented Oct 14, 2021 at 14:25
• @lulu exactly, thats why we need some of the additional requirements from OST Commented Oct 14, 2021 at 14:29
• I confess that I didn't know what OST was and it wasn't easy to look up without knowing. So just in case anybody else needs to know: en.wikipedia.org/wiki/Optional_stopping_theorem Commented Oct 15, 2021 at 8:47

To expand on the suggestion in the comments:

For $$i\in \mathbb N$$ let $$E_i$$ denote the expected number of Tails you see before seeing $$H^i$$.

It is easy to confirm that $$E_1=1$$.

We can now work recursively. In order to see $$H^{n+1}$$ we must first see $$H^n$$. Up to that point, we expect to have seen $$E_n$$ Tails. The next toss is either $$H$$, which ends the game, or $$T$$, which restarts it from the beginning. It follows that $$E_{n+1}=E_n+\frac 12\times 0 +\frac 12\times (E_{n+1}+1)$$ and a simple induction then confirms that $$E_n=2^n-1$$ as desired.

• perfect! thank you Commented Oct 14, 2021 at 14:36

Generating Function Approach

We can develop a generating function of two variables for the probable outcomes. Let $$x$$ represent a head and $$y$$ a tail. An atom of $$1$$ to $$n-1$$ heads followed by $$1$$ or more tails is represented by $$\overbrace{\,\,\frac{x-x^n}{1-x}\,\,}^{x+x^2+x^3+\dots+x^{n-1}}\,\,\overbrace{\,\,\frac{y\vphantom{x^n}}{1-y}\,\,}^{y+y^2+y^3+\dots}\tag1$$ Thus, starting with any number of tails, followed by any number of the atoms from $$(1)$$, and terminated by $$n$$ heads, would give the generating function $$\overbrace{\,\,\frac1{1-y}\,\,}^{\substack{\text{any number}\\\text{of tails}}}\overbrace{\frac1{1-\frac{x-x^n}{1-x}\frac{y}{1-y}}}^{\substack{\text{any number of}\\\text{atoms from (1)}}}\overbrace{\quad\,x^n\vphantom{\frac1y}\,\quad}^{\text{n heads}}=\frac{x^n(1-x)}{1-x-y+x^ny}\tag2$$ In the generating function $$\frac{x^n(1-x)}{1-x-y+x^ny}=\sum_{j,k\ge0}a_{j,k}x^jy^k\tag3$$ each term $$a_{j,k}x^jy^k$$ gives the probability of finishing with $$j$$ heads and $$k$$ tails.

For example, if we set $$y=1-x$$ in $$(3)$$, we get $$\frac{x^n(1-x)}{x^n(1-x)}=1$$, which is the probability of finishing with $$0$$ or more heads (with probability $$x$$) and $$0$$ or more tails (with probability $$1-x$$).

Note that $$x\frac{\partial}{\partial x}\sum_{j,k\ge0}a_{j,k}x^jy^k=\sum_{j,k\ge0}ja_{j,k}x^jy^k\tag4$$ gives the expected number of heads when finished and $$y\frac{\partial}{\partial y}\sum_{j,k\ge0}a_{j,k}x^jy^k=\sum_{j,k\ge0}ka_{j,k}x^jy^k\tag5$$ gives the expected number of tails when finished.

Applying $$(4)$$ to $$(3)$$ and setting $$y=1-x$$, we get the expected number of heads when finished to be \begin{align} x\frac{\partial}{\partial x}\frac{x^n(1-x)}{1-x-y+x^ny} &=\frac{x^{n+1}\left(1-x^n\right)y+nx^n(1-x)(1-x-y)}{\left(1-x-y+x^ny\right)^2}\tag{6a}\\ &=\frac{x^{-n}-1}{x^{-1}-1}\tag{6b} \end{align} Applying $$(5)$$ to $$(3)$$ and setting $$y=1-x$$, we get the expected number of tails when finished to be \begin{align} y\frac{\partial}{\partial y}\frac{x^n(1-x)}{1-x-y+x^ny} &=\frac{(1-x)\left(1-x^n\right)x^ny}{\left(1-x-y+x^ny\right)^2}\tag{7a}\\ &=x^{-n}-1\tag{7b} \end{align} Adding $$(6)$$ and $$(7)$$ gives the expected number of tosses when finished to be $$\frac{x^{-n}-1}{x^{-1}-1}+x^{-n}-1=\frac{x^{-n}-1}{1-x}\tag8$$

Apply to the Question

For a fair coin, $$x=\frac12$$, and we get an expected $$2^n-1$$ heads and $$2^n-1$$ tails by the time we get $$n$$ heads in a row.

If the coin is biased, heads with probability $$x$$ and tails with probability $$1-x$$, the number of heads vs the number of tails is $$x$$ vs $$1-x$$.