Expected Number of Bernoulli trials before you get N more heads than tails 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)?
 A: 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. 
A: 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.
A: 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 http://www.springerlink.com/content/h76486w3330275q7/ . 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.
