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.


  1. Wow! this was near impossible, but it is no where near as challenging as trying to solve the Rubik's cube for the very first time! When I first picked up the cube, I had no idea where to start for days (where with this i could figure it out in minutes!). After years of practice, I can finally solve the Rubik's cube in under 45 seconds (with the help of the best speed cube!)


Post a Comment

Popular posts from this blog

Multi-Core Programming with Java

Interpolation Search Explained

Beat the Streak: Day Three