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 -
- You reach +1 only in odd # of steps
- 50.6% of times you reach +1 in 1 step (law of large numbers in action)
- Average # of steps taken to reach +1: 101,050 steps
- Max. steps taken (extreme case) to reach +1: 951,391,959 steps
- Distribution of steps taken is concentrated towards lower # of steps with few extreme outliers heavily skewing the mean.