A Challenge for my Readers!

In this blog post, I present a very interesting math problem that I came up with while pondering random walk problems.

You are walking along the x axis and you start at $x=0$. At each time step you move to $x+1$ with probability $ \frac{1}{1+x} $ and to $ x-1 $ with probability $ \frac{x}{x+1} $.  What is the expected number of steps until you return to $ 0 $ for the first time?
What makes this problem harder than a typical random walk problem is that the probability of moving to $x+1$ vs $x-1$ is not fixed -- it changes based on your position. That being said, the typical counting methods for solving problems of this type do not apply. There is a clever and fascinating solution that doesn't require too much advanced knowledge, but I will leave it to you to think about this problem.


Popular posts from this blog

Optimal Strategy for Farkle Dice

Automatically Finding Recurrence Relations from Integer Sequences

Markov Chains and Expected Value