A Neat Random Walk Problem

As many of the people that read this blog probably know, I enjoy inventing math problems, especially problems that are probabilistic in nature, and then working out the math to solve that problem. In this blog post, I will introduce one problem that I solved that I think is particularly elegant:

You are randomly walking along the x-axis starting at \( x=0 \). When you are at \( x = n \), you move to \( x = n-1 \) with probability \( p = \frac{n}{n+1} \) and to \( x = n+1 \) with probability \( p = \frac{1}{n+1} \). What is the expected number of steps until you return to \( x = 0 \) for the first time?

This problem differs from standard random walk problems because the probability of moving left and right along the x-axis depends on your current location. In this problem, there is a force that is pulling you towards \( x = 0 \), and the further away you get, the more of an effect this force has on you.

So how do we go about solving this problem? When I first attempted the problem I attempted to setup an equation that described the situation. In particular, I defined a function \( f(n) \) to be the expected number of steps to reach \( x = 0 \) from \( x = n \). This was ultimately a dead end, but my key insight was fairly similar. Let's define a function \( f(n) \) to be the expected number of steps to reach \( x = n-1 \) from \( x = n \). Then the answer to the original problem is simply \( 1 + f(1) \). To get some intuition about what this function needs to look like, we need to think about what can happen when you are at \( x = n \). No matter what you have to take 1 step. With probability \( p = \frac{n}{n+1} \) that is the only step you need to take, because that is the probability of moving to \( x = n-1 \) immediately. However, with probability \( p = \frac{1}{n+1} \) you need to take more steps. In this case, you end up at \( x = n+1 \) but you ultimately want to get back to \( x = n-1 \). To do that, we must first get back to \( x = n \) then we have to get to \( x = n-1 \). By definition of \(f\), the expected number of steps needed to complete this sequence of events is exactly \( f(n+1) + f(n) \). This gives rise to the following equation: $$ f(n) = 1 + \frac{1}{n+1} [ f(n+1) + f(n) ] $$ Solving this equation for \( f(n) \) yields; $$ f(n) = \frac{n + 1}{n} + \frac{f(n+1)}{n} $$ We've got an interesting situation here where we have a recurrence relation but no base case. Theoretically, if we knew \( f(n) \) for any \( n \geq 1 \), then we would know the value of \( f(n) \) for all \( n \) by repeatedly applying the formula. After carefully thinking about the problem, you will probability realize that as we get further away from \( x = 0 \), the expected number of steps to move one unit to the left will approach \( 1 \). Formally we have \( \lim_{n \rightarrow \infty} f(n) = 1 \). Let's take a deeper look at \( f(1) \) for a moment, which is ultimately what we are interested in finding: \begin{align*} f(1) &= \frac{2}{1} + \frac{f(2)}{1} \\ &= \frac{2}{1} + \frac{3}{2 \cdot 1} + \frac{f(3)}{2 \cdot 1} \\ &= \frac{2}{1} + \frac{3}{2 \cdot 1} + \frac{4}{3 \cdot 2 \cdot 1} + \frac{f(4)}{3 \cdot 2 \cdot 1} \\ &= \frac{2}{1!} + \frac{3}{2!} + \frac{4}{3!} + \frac{5}{4!} + \frac{f(5)}{5!} \\ &= \frac{2}{1!} + \frac{3}{2!} + \frac{4}{3!} + \dots + \frac{n+1}{n!} + \dots \end{align*} since \( \lim_{n \rightarrow \infty} \frac{f(n)}{n!} = 0 \), we have: $$ f(1) = \sum_{n=1}^\infty \frac{n+1}{n!} $$ $$ 1 + f(1) = \sum_{n=0}^\infty \frac{n+1}{n!} $$

Now you might recognize this infinite series already but don't worry if you don't. The sum evaluates to exactly $ 2 e \approx 5.437 $.  Here's why: let's define \( g(x) = e^x = \sum_{k=0}^\infty \frac{x^k}{k!} \) Then consider \( x g'(x) = x e^x = \sum_{k=1}^\infty \frac{k x^k}{k!} \). Now define \( h(x) = g(x) + x g'(x) = 1 + \sum_{k=1}^\infty \frac{(k+1) x^k}{k!} \). This looks familiar! In fact, \( 1 + f(1) = h(1) = e^1 + 1 e^1 = 2 e \). There you have it! The expected number of steps to return to the origin is \( 2 e \). This was a beautiful problem, and it has one of the most elegant solutions I have ever come up with. When I initially thought of the problem, I had no idea \( e \) was going to pop up in the answer so that was somewhat of a surprise. If you liked this problem, consider a new but very similar problem where the force is reversed:

You are randomly walking along the x-axis, starting at \( x = 1 \). When you are at \( x = n \), you move to \( x = n-1 \) with probability \( p = \frac{1}{n+1} \) and you move to \( x = n+1 \) with probability \( p = \frac{n}{n+1} \). What is the probability that you eventually reach \( x = 0 \).