11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I can't answer the question of why it turns out to be $mn$, but just an observation in case you didn't know already: your problem is equivalent to, and better known as, an unbiased random walk with two boundaries. This is covered in a lot of textbooks and websites. So maybe if you search using those terms you can find a better answer. $\endgroup$ – antkam Sep 26 at 2:21
  • $\begingroup$ Related math.stackexchange.com/questions/288298/… $\endgroup$ – leonbloy Sep 26 at 18:17
  • $\begingroup$ @AndrewJay: Not only is the general case more complicated than the special case $p=\frac12$, but plugging $p=\frac12$ into the general case, at least as I give it, leads to $\frac00$. $\endgroup$ – robjohn Sep 28 at 17:16
  • $\begingroup$ @robjohn Yes I got that my general answer had division by 0 in it for 1/2 as well (my answer took a different form and I didn't bother simplifying), that's why I mentioned it had to be handled in a special case. $\endgroup$ – Andrew Jay Sep 30 at 2:40
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah, I like this a lot, makes it very clear why p=1/2 takes a special form (otherwise don't get these martingale's, which seems a nicer explanation than having a single eigenvalue for the linear recurrence). It's not particularly any simpler a solution, but I accept there may not be a very simple argument for why it holds. I had also worked out those probabilities previously (by just noting that the recurrence gave a constant rate of increase as m goes down 1 and n goes up 1 from g(m+n,0)=0 to g(0,m+n)=1, with g prob of stopping on m heads), but using fact that gambling is fair seems nicer. $\endgroup$ – Andrew Jay Sep 26 at 3:26
  • 1
    $\begingroup$ +1 This is a great answer. Can you confirm my understanding: It seems $p=1/2$ is used twice. (1) It makes $M_t$ a martingale, allowing a quick solution for $p$. Then (2) it makes $M'_t$ a martingale, and this is actually more subtle: Because $E[M_t] = 0$, we have $Var(M_t) = E[M^2_t]$. But we also have $Var(M_t) = t$ since you're adding an i.i.d. r.v. with $Var=1$ per step, and together they contribute to making $M^2_t - t$ a martingale. (At least, that's how I understood it, or rather, that's how I "reverse-engineered" how you could come up with the amazing definition $M'_t = M^2_t - t$!) $\endgroup$ – antkam Sep 26 at 18:26
  • 1
    $\begingroup$ Further, in the biased case, $M_t - \mu t$ would be a martingale, and from that alone, you have a linear equation $\mu E[T] = m p - (1-p) n$. This means you can solve $E[T]$ at once if you have another way to solve $p$ (for the biased case), and that IIRC I have seen in some websites / web textbooks. Sadly, I'm not sure the Variance-based martingale (the equiv of $M'_t$) works for biased coin. (I'm both not sure it's still a martingale, and not sure that the resulting equation is useful even if it is a martingale). $\endgroup$ – antkam Sep 26 at 18:32
  • $\begingroup$ @antkam I think your understanding is correct. To be clear, I didn't come up with that clever martingale; I was shown it several years ago, and it was so elegant I've refused to forget it since. Here's one of my all-time favorite MSE answers that sheds some light on how one might find it: math.stackexchange.com/a/1715693/485314 $\endgroup$ – Aaron Montgomery Sep 26 at 19:17
  • $\begingroup$ As for the biased walk, there are some great answers along the direction you're thinking here: math.stackexchange.com/questions/76486/… $\endgroup$ – Aaron Montgomery Sep 26 at 19:17
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not that familiar with difference equations, so I'd appreciate if you can help with this question: How can you tell from (2) that the $h^2$ coefficient is $-1$? $\endgroup$ – antkam Sep 27 at 19:59
  • $\begingroup$ The second difference of a polynomial of degree less than $2$ vanishes. For the first difference: $\Delta h^2=(h+1)^2-h^2=2h+1$. For the second difference: $\Delta^2h^2=(2(h+1)+1)-(2h+1)=2$. $\endgroup$ – robjohn Sep 27 at 23:11
  • $\begingroup$ I understand (sort of) why $f$ is second degree, but lets say $f = A h^2 + B h + C$, then for any $A$ it remains true that $f(h+1) - 2 f(h) + f(h-1) = A(h+1)^2 ... - 2A h^2 ... + A(h-1)^2...$ has no $h^2$ term, which of course matches the RHS, but how can one conclude that therefore $A = -1$? $\endgroup$ – antkam Sep 28 at 2:21
  • $\begingroup$ $\begin{align} &\color{#C00}{f(h+1)}-\color{#090}{2f(h)}+\color{#00F}{f(h-1)}\\ &=\color{#C00}{\left(A\left(h^2+2h\,\underline{+\,1}\right)+B(h+1)+C\right)}-\color{#090}{2\left(Ah^2+Bh+C\right)}+\color{#00F}{\left(A\left(h^2-2h\,\underline{+\,1}\right)+B(h-1)+C\right)}\\ &=2A\end{align}$ $\endgroup$ – robjohn Sep 28 at 5:07
  • $\begingroup$ ah! of course, thanks very much. :) $\endgroup$ – antkam Sep 28 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.