# Ergodic Grasshopper

This week’s Riddler poses a question about a grasshopper on a balance beam:

You are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position.

If the grasshopper is within 20 centimeters of one of the edges, it will not jump off the edge. For example, if it is 10 centimeters from the left edge of the beam, then it will randomly jump to anywhere within 30 centimeters of that edge with equal probability (meaning it will be twice as likely to jump right as it is to jump left).

After many, many failed attempts to catch the grasshopper, where is it most likely to be on the beam? Where is it least likely? And what is the ratio between these respective probabilities?

We observe that the probability of the grasshopper being at any specific position on the beam like the exact middle or the exact end is zero with a continuous distribution. So, we proceed by coarse graining the problem a bit and limit the valid locations on the balance beam to n points, calculate transition probabilities from point to point, raise the the transition matrix to a suitably high power, look at the results, and then let the distance between points go to zero. We will see that the distance between points actually doesn’t really matter within reason in this problem!

We will start by locating 21 points on the beam and calculate a transition probability matrix T (see Python code below):

The system essentially has a “soft reflection” when the boundaries of the probability interval move past the end of the beam, which is kind of interesting.

To find the longer term behavior of this system, we follow Markov chain theory and raise the T matrix to the arbitrary power of 100, at which point it should settle to a steady state if there is one:

We see a good result – all the rows are identical. This means that the intial location of the grasshopper, or probability distribution of the initial location, does not matter at all, and that each row describes the long term probability of the grasshopper’s location. Note: these row values can also be found by solving the linear equation x*T =x with constraint that sum(x) = 1, which is the equivalent of calculating the left eigenvector of the transition matrix with eigenvalue = 1 and normalizing it so that total probability = 1.

The probability distribution of the location of the grasshopper after many jumps (>=100) looks like:

And the ratio of the probability of the middle points to the end points is exactly 2.0.

If we change the code parameters to reduce the point spacing to 1 or .1 or .01, it does not change the probability ratio of 2. Also, the width of the hop distribution (20 in the problem) does not affect the ratio either for plausible values.

Code:

## 2 thoughts on “Ergodic Grasshopper”

1. […] of discrete points on the beam went to infinity. By having a beam with 21 discrete locations, one solver used a Markov chain to map out the grasshopper’s location after 100 jumps. Again, the same […]

Like

2. […] of discrete points on the beam went to infinity. By having a beam with 21 discrete locations, one solver used a Markov chain to map out the grasshopper’s location after 100 jumps. Again, the same […]

Like