MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello, I'd like to find the expected number of Bernoulli trials that I'll need before I will get exactly n more heads than tails, given a coin which gets a heads with probability p.

My approach for this problem has been as follows: a) The probability of getting n more heads is equal to getting any permutation of N+r-1 heads and r tails, followed by a single head, thus $\sum_{r=0}^{\infty} p^{n+r}(1-p)^{r}$ ${n+2r-1}\choose{r}$

b) To find the expected number, I'll just have consider $\sum_{r=0}^{\infty} (n+2r) p^{n+r}(1-p)^{r}$ ${n+2r-1}\choose{r}$

c) I need to find the expectation over the trial lengths of $\gamma^{l}$ ($\gamma$ is a constant $<1$), i.e. $\sum_{r=0}^{\infty} \gamma^{n+2r} p^{n+r}(1-p)^{r}$ ${n+2r-1}\choose{r}$

Another way of phrasing the problem (which is the context in which I would like to solve it) is: Suppose you are at a distance n from a goal, and with probability p you move towards it, and 1-p away from it. What is the expected number of steps you will need to reach the goal?

I don't know how to evaluate any of those summations. I only need an approximate answer - as a function of $p$ and $n$. Is there any other way than by using Stirling's formula for the binomial coefficients (which gets quite messy)?

share|cite|improve this question
This is an easy exercise in probability, so I voted to close. The value $H-T-(2p-1)t$ is a martingale and when $p>1/2$, the optional stopping theorem applies. The martingale starts at $0$ so the expected value at the stopping time is $0$, and the expected stopping time is therefore $n/(2p-1)$. – Douglas Zare Aug 22 '11 at 16:42
up vote 4 down vote accepted

The expected number of trials is infinite if $p\le1/2$ and $n/(2p-1)$ if $p>1/2$.

To see this, a one-step analysis is enough. First, to reach level $n$ one needs to first reach level $1$ starting from level $0$, then to reach level $2$ starting from level $1$ and so on. Each of these durations has the same distribution hence the expected time $t_n$ needed to reach level $n$ starting from level $0$ is $t_n=nt_1$. Second, starting from level $0$, the first step puts us at level $1$, and then we hit level $1$ after $1$ step, or the first step puts us at level $-1$ and then we must climb two steps to reach $1$. The former happens with probability $p$ and the latter happens with probability $1-p$ hence $t_1=p\cdot1+(1-p)\cdot(1+t_2)$. Plugging $t_2=2t_1$ in this yields $t_1=1+2(1-p)t_1$. To complete the proof, note that this relation holds in $[0,+\infty]$ and that its solution is $t_1=+\infty$ if $2(1-p)\ge1$ and $t_1=1/(2p-1)$ otherwise.

share|cite|improve this answer
Yes, this agrees with Feller, An Introduction to Probability Theory and Its Applications, around page 349. He also considers the case of boundaries both above and below the starting point. Note that in the case $p=1/2$, the boundary will be reached with probability 1 even though the expected time is infinite. – Brendan McKay Aug 22 '11 at 5:46
@Brendan: This is standard stuff explained in numerous textbooks. If one wants to go back to Feller's treatises, this would be volume I (with the page you mention, at least in the third edition). – Did Aug 22 '11 at 20:02

This is a "gambler's ruin" problem. Our gambler has n dollars, the house has an infinite supply of money, the gambler repeatedly bets 1 dollar at even money. How long before he is broke? You should be able to find the analysis in probability texts.

share|cite|improve this answer

Aside from the basic question about the expected number of trials for the question, I had two other questions - the probability distribution of the length of trials, and $E[\gamma^l]$.

There is a very nice generating function approach to answer both these questions that I found in this paper . I would never have known what to search for had I not known this was really the Gambler's Ruin problem, so many thanks to Gerald and Didier.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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