Is there a simple reason why the expected number of coin flips till getting $m$ more heads than tails or $n$ more tails than heads should be $mn$?

Question

I flip a coin until I get $m$ more heads than tails, or $n$ more tails than heads. Let the expected number of flips of the coin before stopping be $f(m,n)$.

I obtained $f(m,n)=mn$ from the recursion $f(m,n)=1+\frac{f(m-1,n+1)+f(m+1,n-1)}2$ with $f(k,0)=f(0,k)=0$ for all $k$.

Other than going through this recursion (and either solving by inspection or by writing as linear recurrence in single variable and solving brute force), is there an intuitive reason you should expect this process to take $mn$ flips? I was thinking about the more general problem with probability $p$ of getting heads and was struck by how simple the formula became when handling, what turned out to be a special case (general formula broke down) of $p=\frac12$.

Answer 1

I'm not sure if this is a straightforward "intuitive reason" like you're hoping for, but it is a very different solution to this problem that is recursion-free and (I think) quite fun. Let's think of this problem like the Gambler's Ruin.

A bettor walks into the casino with 0 dollars. She makes \$1 wagers on coin flips; she wins \$1 on heads, and she loses \$1 on tails. She intends to make bets until she reaches a bankroll of \$$m$ (at which point she'll have seen $m$ more heads than tails). This is a very generous casino, so she is allowed to assume a very small amount of debt; she can borrow a maximum of \$$n$ from the casino (at which point she'll have seen $n$ more tails than heads). She will play until one of those conditions are met.

Let $M_t$ denote her bankroll after $t$ flips, and let $T$ be the number of flips required before she leaves. Note that $M_T$ is necessarily either $m$ or $-n$, but which one of those it is depends on the outcomes of the coin flips. Call $\mathbb P(M_T = m)$ by the name $p$. Since $M_t$ is the result of fair bets, it is a martingale. One can verify that the conditions of the Optional Stopping Theorem apply to $M_t$ and $T$, whence $\mathbb E[M_T] = \mathbb E[M_0] = 0$; that is, her expected bankroll when she leaves is the same as when she entered, because every bet was fair (and some technical conditions are satisfied). However, $$\mathbb E[M_T] = m \cdot p - n \cdot \mathbb (1-p)$$ so setting this equal to $0$ and solving for $p$ gives $p = \frac{n}{m+n}$. The intuition behind $p$ should somewhat clear; the starting point ($0$) is $n$ steps along the path of length $m+n$ from $-n$ to $m$.

It's worth pausing to point out that it's perhaps not at all clear why this is useful in answering the question you asked. Here's the magic: we'll observe a second martingale, $M'_t = M_t^2 - t$. You can easily see why this is a martingale; if $M_t = x$, then $M_t' = x^2 - t$, and $M_{t+1}'$ will be either $(x+1)^2-(t+1)$ or $(x-1)^2 - (t+1)$ with equal probability; you can verify that their average is $M_t'$.

Since $M_n'$ is a martingale, we can use the Optional Stopping Theorem up above again; note that $M_0' = 0$, whence $\mathbb E[M_T'] = 0$ as well. However, $$\mathbb E[M_T'] = \mathbb E[M_T^2] - \mathbb E[T] = m^2 p + n^2(1-p) - \mathbb E[T] = 0$$ and since we saw above that $p = \frac{n}{m + n}$, solving for $\mathbb E[T]$ gives the advertised $mn$.

I'm not sure if this will scratch your itch for a heuristic argument for the reasonableness of $mn$, but I like this method a lot and thought the algebra in the punch line may be illuminating.

Answer 2

Fair Coin

Let $e(h,t)$ be the expected duration to get $h$ more heads than tails or $t$ more tails than heads. We get the following relation: $$ e(h,t)=\overbrace{\tfrac12e(h-1,t+1)}^{\substack{\text{probability of a head}\\\text{times}\\\text{duration after a head}}}+\overbrace{\tfrac12e(h+1,t-1)}^{\substack{\text{probability of a tail}\\\text{times}\\\text{duration after a tail}}}+\overbrace{\ \quad1\vphantom{\tfrac12}\quad\ }^{\substack{\text{account}\vphantom{y}\\\text{for}\\\text{head/tail}}}\tag1 $$ If we let $f_{h+t}(h)=e(h,t)$. Then $(1)$ becomes a second order difference equation $$ f_n(h-1)-2f_n(h)+f_n(h+1)=-2\tag2 $$ Equation $(2)$ says that $f_n(h)$ is a degree $2$ polynomial in $h$ with with an $h^2$ coefficient of $-1$. Since $f_n(0)=f_n(n)=0$ we get $$ f_n(h)=h(n-h)\tag3 $$ Equation $(3)$ translates to $$ \bbox[5px,border:2px solid #C0A000]{e(h,t)=ht}\tag4 $$

---

Weighted Coin

Suppose the coin comes up heads with probability $p$ and tails with probability $1-p$. Equation $(1)$ becomes $$ e(h,t)=pe(h-1,t+1)+(1-p)e(h+1,t-1)+1\tag5 $$ which becomes the second order difference equation $$ pf_n(h-1)-f_n(h)+(1-p)f_n(h+1)=-1\tag6 $$ which, when written using the shift operator in $h$, $S_h$, is $$ (S_h-1)\left(S_h-\frac{p}{1-p}\right)f_n(h)=-\frac1{1-p}\tag7 $$ whose solution, given that $f_n(0)=f_n(n)=0$, is $$ f_n(h)=\frac{n}{1-2p}\,\frac{1-\left(\frac{p}{1-p}\right)^h}{1-\left(\frac{p}{1-p}\right)^n}+\frac{h}{2p-1}\tag8 $$ which translates to $$ \bbox[5px,border:2px solid #C0A000]{e(h,t)=\frac{t(1-p)^t\left[(1-p)^h-p^h\right]+hp^h\left[p^t-(1-p)^t\right]}{(1-2p)\left[(1-p)^{h+t}-p^{h+t}\right]}}\tag9 $$

---

Weighted Case Limits to the Fair Case

Simply plugging $p=\frac12$ into $(9)$ gives $\frac00$, not $(4)$.

To evaluate the limit of $(9)$ as $p\to\frac12$, set $p=\frac{1+\delta}2$, so $1-p=\frac{1-\delta}2$. Then, $(9)$ becomes $$ \begin{align} \hspace{-12pt}e(h,t) &=\frac{t(1-\delta)^t\left[(1-\delta)^h-(1+\delta)^h\right]+h(1+\delta)^h\left[(1+\delta)^t-(1-\delta)^t\right]}{\delta\left[(1+\delta)^{h+t}-(1-\delta)^{h+t}\right]}\\ &=\small\frac{t\left(1-t\delta+O\!\left(\delta^2\right)\right)\left(-2h\delta+O\!\left(\delta^3\right)\right)+h\left(1+h\delta+O\!\left(\delta^2\right)\right)\left(2t\delta+O\!\left(\delta^3\right)\right)}{2(h+t)\delta^2+O\!\left(\delta^4\right)}\\ &=\frac{2ht^2\delta^2+2h^2t\delta^2+O\!\left(\delta^3\right)}{2(h+t)\delta^2+O\!\left(\delta^4\right)}\\[3pt] &=\frac{2ht(h+t)+O(\delta)}{2(h+t)+O\!\left(\delta^2\right)}\\[6pt] &=ht+O(\delta)\tag{10} \end{align} $$ Thus, as $p\to\frac12$, $(10)$ shows that $(9)\to(4)$.