Expected value of steps taken to hit +1 on a 1D integer random walk given you start from zero?

Question

I am trying to calculate the expected number of steps taken on a 1-dimensional random walk (starting from zero) to reach +1.

So far my approach has been to use recursive expectation (first step analysis) technique but I end up creating infinite equations because there are infinite states (since boundary is not closed and there is chance, albeit small that we go to negative infinity before coming to +1).

By intuition (and simulation results below) I feel that the answer may be infinite number of steps (for the expected value of steps taken to reach +1, starting from zero) but I am not able to come up with a mathematical solution to it.

Can someone please help me find the solution / answer to this question?

---

Aside: I ran a simulation on my computer for this process 10,000 times (assuming law of large numbers will help me get an answer close to theoretical average). The simulation took roughly 2 hrs to run. Here are some few observations -

1. You reach +1 only in odd # of steps
2. 50.6% of times you reach +1 in 1 step (law of large numbers in action)
3. Average # of steps taken to reach +1: 101,050 steps
4. Max. steps taken (extreme case) to reach +1: 951,391,959 steps
5. Distribution of steps taken is concentrated towards lower # of steps with few extreme outliers heavily skewing the mean.

Answer 1

Your remark on outliers strongly skewing the mean is a very valuable observation. In fact, it can be shown for the symmetric random walk that the expected value of steps to hit any specific level is $\infty$. Let me prove this:

Let $T_k$ be the first hitting time of level $k$ for $k>0$. You are interested in $\mathbb E[T_1]$.

By translation invariance, $T_k$ does not depend on the starting point of the random walk, so $\mathbb E[T_k]$ is simply the expected value of steps necessary to go up $k$ levels from any starting point. For example, $T_2$ can be viewed as the first hitting time of level $+1$ when starting at $-1$.

By using the Markov property of the random walk (all future steps are independent of the past steps), we can break the problem of going up any number of levels $k$ into a sum of smaller problems, namely of reaching the level above $k$ times. Thus, $$ \mathbb E[T_k] = k \mathbb E[T_1]. $$

Now consider your problem. You start at $0$ and take the first step. You go up with probability $p$ and down with probability $q=1-p$. Now you want to to calculate the expected number of steps $\mathbb E[T_1]$. It is given by the sum of:

• your first step ($1$),
• the probabilty of having gone up ($p$) multiplied by the expected value of further necessary steps to reach level $+1$ (which is $0$ because you have already reached it if you went up),
• the probabilty of having gone down ($q$) multiplied by the expected value of further necessary steps to reach level $+1$ (which is $\mathbb E[T_2]$ because you have to go up $2$ levels now).

Thus, $$ \mathbb E[T_1] = 1 + p\cdot 0 + q \cdot \mathbb E[T_2] = 1 + 2q\mathbb E[T_1]. $$

If $p\leq 1/2$, then this equation has no non-negative solution (you can trivially check this for $p=q=1/2$) and $\mathbb E[T_1] = \infty$.

If $p> 1/2$, then this equation is solved by $\mathbb E[T_1] = 1/(p-q)$.

Answer 2

One approach is to look at the case of a random walk where you have a left boundary of $-n$ in the negative direction. (If you are at position $-n$, you always go to position $-n+1$ on the next step). In this finite case you can figure out the (finite) expectation for getting from $0$ to $1$ with a system of linear equations. Then take a limit of this expectation as $n\to\infty$