Calculating expected value of random walk with one stop value.

Question

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

Answer 1

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.

Answer 2

$E[V] = \displaystyle\sum_{i=0}^{\infty} (2i+1) C_i \, 0.4^i \, 0.6^{i+1}$ with an extra $(2i+1)$ term compared with your first expression.

Since $C_i= {2i \choose i}/(i+1) ={2i+1 \choose i}/(2i+1)$ you get your second correct expression when the two $(2i+1)$ terms cancel.

Your third expression is missing a $\frac{(2i+1)}{(i+1)}$ term so intuitively it is not a surprise that it is just over half the correct answer.

For a possible general approach, first check that you do in fact stop with probability $1$. Then see how many ways there are of being one step away from stopping without having previously stopped and what the probability of each of them are multiplied by the probability of stopping on the next step.