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

Question

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?

Answer 1

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.

Answer 2

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$.