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)?



Expected Number of Bernoulli trials before you get N more heads than tails
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. 


