Can you hop to the lily pad?

This week’s Fiddler is about hopping back and forth.

You are a frog in a pond with an infinite number of lily pads in a line, marked “1,” “2,” “3,” etc. You are currently on pad 2, and your goal is to make it to pad 1. From any given pad, there are specific probabilities that you’ll jump to another pad: Whenever you are on pad $k$, you will hop to pad $k−1$ with probability $1/k$, and you will hop to pad $k+1$ with probability $(k−1)/k$.

What is the probability that you will ultimately make it to pad 1?

My solution:
[Show Solution]

One thought on “Can you hop to the lily pad?”

  1. Beautiful analysis! I got as far as the recursion relation, but not to your elegant solution of it.

    I am confused, though, by your comment on the Markov chain. It seems to me that your analysis is completely equivalent to finding the stationary distribution. Your a_k’s are the components of the right-eigenvector with eigenvalue 1 of the Markov transition matrix (there are two of these right-eigenvectors, your two ‘fundamental solutions’). The corresponding left-eigenvectors span the possible stationary distributions, and inner products with the initial state determine the correct one. No matrix inversion is needed. Of course the final result is the same as yours.

Leave a Reply

Your email address will not be published. Required fields are marked *