Expected number of coin flips until either 10 more Hs than Ts or 7 more Ts than Hs

combinatoricsexpected valueprobability

Problem: Find the expected number of flips of a fair coin needed to either have 10 more heads flipped than tails or 7 more tails flipped than heads.

My approach:

Let H be the number of heads flipped and T be the number of tails

$E(H = T + 10) + E(T = H + 7)$

I tried forming a sum of Geometric Progression individually for both cases, but couldn't arrive at the correct answer.

Follow up: The interesting fact is that the answer is 70. Is it by pure coincidence that its a product of 7 and 10, or is there a probabilistic reason as to why the expected value comes out to be so conveniently related to the input data?

Best Answer

Let $H_t$ and $T_t$ be the number of heads and tails, respectively, after $t$ flips; let $D_t := H_t - T_t$ be their difference. You now want to look at the first time $T$ that $D_t$ reaches either $+10$ or $-7$:

$$ T = \inf\bigl\{ t \ge 0 \mid D_t \in \{+10, -7\} \bigr\}. $$

Observe that $D$ steps up by $+1$ with probability $\tfrac12$ and down by $-1$ with probability $\tfrac12$; that is, $D$ is just a simple random walk!

So, we have reduced the question to one of hitting time for SRW. This is a very well-known problem, called Gambler's ruin. You can find the expected value $\mathbb E(T)$ of $T$ by searching for this online.

You can calculate it directly using standard hitting-time techniques. Let $X$ be simple random walk on $[0,n] \cap \mathbb Z$; we will be interested in $n = a+b$ and starting from $a$. Let $T$ be the first hitting time of either $0$ or $n$ and $t_i := \mathbb E_i(T)$, ie the expected hitting time started from $i$. Then,

$$ t_i = 1 + \tfrac12 t_{i-1} + \tfrac12 t_{i+1}, \quad t_0 = 0 \quad\text{and}\quad t_n = 0. $$

Solving this relation gives $t_i = i(n-i)$. You should verify this yourself, too! Now, we care about an interval of length $a+b = n$ and starting $a$ from one side, so the time we're interested in is

$$ \mathbb E_a(T) = a \bigl( (a+b) - a \bigr) = ab. $$

You can also prove this using martingales. An introduction to these is given in Section 4.1 of Norris's book. In particular, your exact question is answered on Page 117, at the very end of Section 4.1. You can also find many more expositions online. In particular, if $+10$ is replaced by $+b$ and $-7$ by $-a$, then, indeed, $\mathbb E_0(T) = ab$, the product, as you noticed.