Let N be a positive integer. I toss a fair coin several times and I want to know the probability that the number of heads becomes larger than the number of tails (by 1) BEFORE the number of tails is ever larger than the number of heads by N. Intuitively, since it seems N times harder to get N times a fixed value of the outcome than it is to get a fixed value just once, my guess is N/(N+1) (I mean, if I was betting a dollar for each head, chances of winning 1 dollar before losing 100 in a fair game should not be 100/101 ?). In fact, I will be happier with an answer that uses this intuition to give a simple proof based on some standard probability arguments about expected values and alike. What about the case of an unfair coin?


Your intuition is good.

Let $p_N$ be the probability you seek. That is, $p_N$ is the probability that $\#T-\#H$ eventually reaches $N$ before it hits $-1$. We fix N and consider a possible path. At any point along this path, the only information you need is $\#T-\#H$. Thus the state of a path can be summarized with an integer $(m)$. For example the state of the path $TTHTHT$ is $(2)$ as there have been $2$ more Tails than Heads. We will denote by $p_N(m)$ the probability of winning assuming the current state is $(m)$. Thus the answer $p_N=p_N(0)$.

We note some recursions: $$p_N=p_N(0)=\frac 12 0+\frac 12 p_N(1)=\frac 12 p_N(1)$$ as the next throw must be $H$ or $T$ with equal probability. Similarly,$$p_N(1)=\frac 12 p_N+\frac 12 p_N(2)\;\Rightarrow\;P_N=\frac 13p_N(2)$$ We are lead to conjecture that $$p_N(m)=(m+1)p_N$$

To prove that note the general recursion: $$p_N(i)=\frac 12 p_N(i-1)+\frac 12 p_N(i+1)$$ which inductively yields $$2(i+1)p_N=(i)p_N+p_N(i+1)\;\Rightarrow\;p_N(i+1)=(i+2)p_N$$

In particular, as $p_N(N)=1$ we see that $$1=p_N(N)=(N+1)p_N\;\Rightarrow\;p_N=\frac 1{N+1}$$

Note: it shouldn't be too terrible to redo all of this with an unfair coin. Just reweight the recursions appropriately.


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.