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$.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment