I know that for a random walk with two stop values, the expected value of the number of steps needed is $ab$ where the stop values are $-a$ and $b$ and the initial position is at 0.
What about for random walks with probability $1$ of reaching the stop value? For example, I am at position $1$ and I have probability $0.6$ of going left and $0.4$ of going right. I obviously have probability $1$ of reaching $0$, but what is the expected value of number of steps?
Simulations seem to say $E[V] = 5$ which is equal to $\sum_{i=0}^{\infty} C_i * 0.4^i * 0.6^{i+1}$ where $C_i$ is the $i$th Catalan number. However this is equal to of $\sum_{i=0}^{\infty} 0.6^{i+1}*0.4^i*\binom{2i+1}{i}$ which doesn't make intuitive sense. I would have reasoned it to be $\sum_{i=0}^{\infty} 0.6^{i+1}*0.4^i*\binom{2i}{i} = 3$ since the last head is set (the last coin tossed has to be a head). The first equation seems to double count?
Thanks! (Also is there a general formula or approach for random walks with one stopping value?)
Best Answer
Let $N$ denote the expected number of steps before hitting $0$ when starting at position $1$ and having probability $p\gt\frac12$ of going left and $1-p$ of going right.
The (simple) Markov property after one step indicates that $N=p\cdot1+(1-p)\cdot(1+M)$ where $M$ denotes the expected number of steps before hitting $0$ when starting at position $2$. Since this requires to hit $1$ starting from $2$ then to hit $0$ starting from $1$ and since both phases require the same mean number of steps $N$, one has $M=2N$.
Solving this for $N$ yields $N=1/(2p-1)$.
The full distribution of $N$ stems from the same decomposition applied to the generating function $E[s^N]$, for every $s$ in $[0,1]$, which yields the system $E[s^N]=p\cdot s+(1-p)\cdot s\cdot E[s^M]$ and $E[s^M]=E[s^N]^2$, implying that $$ E[s^N]=\frac{1-\sqrt{1-4p(1-p)s^2}}{2(1-p)s}, $$ from which $P[N=2n+1]$ can be deduced for each $n\geqslant0$ by a series expansion of the square root in the numerator.