May 5, 2023
Inspired by a conversation with Matan Protter, this week’s Express involves a happily hopping grasshopper:
A grasshopper is jumping on a number line and starts at its home at zero (i.e., the “origin”). Its first jump will be length 1/2, its second jump will be length 1/4, its third jump will be length 1/8 and so on. (To make this explicit, its Nth jump will be length \(\frac{1}{2^N}\).)
However, before the jumping begins, it drinks a little too much grasshopper juice and loses all sense of direction. For each jump, it will hop left or right along the number line with equal probability.
After infinitely many jumps, the grasshopper’s head is once again clear and it wants to return home to the origin. On average, what is the expected distance it travels to return to the origin? (Note that no matter which side of the origin the grasshopper is on, “distance” is defined as being zero or positive, but cannot be negative.)
Extra credit: The next day, the grasshopper again jumps randomly from the origin, but this time with a little more enthusiasm, such that the Nth jump has length \(\left(\frac{2}{3}\right)^N\). After infinitely many jumps, what is the average distance the grasshopper must now travel to return to the origin?
For \(r = \frac{1}{2}\), the average distance is exactly \(1/2\).
For \(r = \frac{2}{3}\), the average distance is about 0.743.
Explanation:
Let us define a random variable \(X\) such that it takes on two values {-1, 1} with equal probability. In addition, let us have a sequence of this random variable \(\{X_1, X_2, \dots, X_n, \dots\}\) that are independent and identically-distributed (i.i.d). In the original puzzle, then we can define the following:
\begin{align} Y &= \sum_{n = 1}^{\infty} \frac{X_n}{2^n} \\ \end{align}
Where \(Y\) is another random variable. Whether you use the Strong Law of Large Numbers or just realizing that each coefficient is equally likely to be positive or negative and it cancels out over infinitely many realizations, it is clear that \(E[Y] = 0\).
However, the answer is in the expression \(E[|Y|]\). This expression is not the same as \(E[Y]\). In order to tackle this problem, we must first realize that the first jump will always yield a distance of \(\frac{1}{2}\) whether the grasshopper leaps to the left or to the right, so without loss of generality, let us have our friend leap to the right. We now need to find \(E[Z]\) where:
\begin{align} Z &= \frac{1}{2} + \left|\sum_{n = 2}^{\infty} \frac{X_n}{2^n}\right| \end{align}
Here is where a little visualization comes in. Suppose after jumping to the right, all subsequent jumps are to the left, then after infinitely many jumps, where does the grasshopper end up? The answer is:
\begin{align} d &= \frac{1}{2} - \sum_{n = 2}^{\infty} \frac{1}{2^n} \\ \\ &= \frac{1}{2} - \frac{1/4}{1 - 1/2} \\ \\ &= \frac{1}{2} - \frac{1}{2} \\ \\ &= 0 \\ \end{align}
Of course, if the grasshopper always jumps to the right after the initial leap, then it will end up at \(d = 2\).
Here the key observation is that if the initial leap distance, call it \(r\), is \(\frac{1}{2}\), then the grasshopper will always remain on one side of the number line about the \(x = 0\) vertical in the subsequent jumps. The average distance from origin then becomes \(r + \delta\), where \(\delta\) is the average deviation from \(r\) in the subsequent jumps, which follows the same analysis as that for deriving \(E[Y]\) and is in fact 0. In fact, we can generalize this for values of \(r\). Here, the right most point the grasshopper can jump would be \(\frac{r}{1 - r}\) assuming \(|r| < 1\) by the geometric series formula. That value is clearly greater than 0. The left most point for the grasshopper would be:
\begin{align} d &= r - \sum_{n = 2}^{\infty} \frac{r^n}{2^n} \\ \\ &= r - \frac{r^2}{1 - r} \\ \\ &= \frac{r - 2r^2}{1 - r} \\ \end{align}
Since \(\frac{r}{1 - r}\) is on the right (positive) side of the number line, we need \(\frac{r - 2r^2}{1 - r}\) to be non-negative in order to not "switch sides". That is:
\begin{align} \frac{r - 2r^2}{1 - r} &\geq 0 \\ \\ r - 2r^2 &\geq 0 \\ \\ 1 - 2r &\geq 0 \\ \\ r &\leq \frac{1}{2} \end{align}
Remember that \(|r| < 1\). Therefore, for \(0 < r \leq 1/2\), after the initial jump, the grasshopper will always remain on one side of the number line (say positive), and the average distance will be \(r\) since the subsequent deviations is 0 without switching sides.
By symmetry, we can further conclude that the deviation, \(\delta\), is uniformly-distributed about 0 with variation \(\frac{4r^4}{12(1 - r)^2} = \frac{r^4}{3(1 - r)^2}\) and standard deviation \(\frac{r^2}{\sqrt{3}(1 - r)}\). For \(r = 1/2\), this translates to a variance of \(1/12\) and standard deviation of \(\sqrt{1/12} \approx 0.289\) units.
For the extra credit, we have \(r = 2/3\). This value is greater than \(1/2\), which means that the grasshoper can reach anywhere between \(-1/3\) and 2 after the initial jump to \(2/3\). While the subsequent deviation still averages to 0, we can no longer use it to calculate the average distance to be \(2/3\) because a side switch occurs. If the grasshopper ends up at say \(-1/3\), the distance is still \(1/3\), i.e. the absolute value of the number on the number line. In order to obtain the average distance, we must find the distribution of the deviations and then weigh the absolute values of the deviations against their frequencies in the distribution. Here, it is much easier to simulate the average distance to be about 0.743.