This week the question is: Can You Hop to the Lily Pad?

You are a frog in a pond with four lily pads, marked “1” through “4.” 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:

• Once on pad 1, you will happily stay there forever.
• From pad 2, there’s a 1-in-2 chance you’ll hop to pad 1, and a 1-in-2 chance you’ll hop to pad 3.
• From pad 3, there’s a 1-in-3 chance you’ll hop to pad 2, and a 2-in-3 chance you’ll hop to pad 4.
• Once on pad 4, you will unhappily stay there forever.

Given that you are starting on pad 2, what is the probability that you will ultimately make it to pad 1 (as opposed to pad 4)?

And for extra credit:

Once again, you are a frog in a pond. But this time, the pond has infinitely many lily pads, which are numbered “1,” “2,” “3,” etc. As before, you are currently on pad 2, and your goal is to make it to pad 1, which you would happily stay on forever.

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.

Now, what is the probability that you will ultimately make it to pad 1?

Highlight to reveal (possibly incorrect) solution:

Program.

This problem can also be expressed as:

The initial state is a = (0 1 0 0). We are on the 2nd pad with probability 100%.

Then a matrix describes each state change:

    ⌈  1   0   0   0  ⌉
M = | 1/2  0  1/2  0  |
    |  0  1/3  0  2/3 |
    ⌊  0   0   0   1  ⌋

After 1 jump, the state is a * M = (1/2 0 1/2 0). What we’re looking for is the state after infinitely many jumps. It’s actually okay to simulate 200 jumps, this converges nicely. The value of a * M²⁰⁰ = (0.6 0 0 0.4). The value we’re looking for is 0.6. This is reflected in the first line of output from my program.

And for extra credit:

Repeat the above with ever bigger ponds. I stopped at 20 pads. My program output shows, that the value we’re looking for converges. The last line says 0.63212055882856. I’m not sure what that signifies. e/pi²?