Brilli The Ant And His Numberline Wall

Relevant wiki: Expected Value - Problem Solving

Let $E(x)$ be the expected number of wall bumps when starting from point $x$ . We have the following three identities:

• $E(100) = 0$ (if we're at 100, we're done)
• $E(-1000) = 1 + E(-999)$ (if we're at -1000, we're bumping the wall, and our next step is to -999)
• $E(x) = \frac{1}{2} (E(x-1) + E(x+1))$ for $-999 \le x \le 99$ (if we're anywhere else, we have equal chances going left or right, and we won't bump the wall midway)

Now, interestingly, we can induct using the second and the third identities to prove that $E(x) = 1 + E(x+1)$ . (Induct from $x = -1000$ upward.) After obtaining this relation, we can use induction again with the first identity to show that $E(x) = 100 - x$ . (Induct from $x = 100$ downward.) We're seeking for the value of $E(0)$ , which is $100 - 0 = \boxed{100}$ .

---

First, it's surprising that the answer is 100, while it looks like the finish is much closer and thus the answer should be tiny. This is intuitively explained by the fact that in the off-chance that we do go left a lot, we will bump the wall many, many times before we finally manage to go back to the right, to the finish line.

More surprisingly, it doesn't matter where the wall to the left of us is; the wall can be at -1, at -1000, or at negative Graham's number, and the expected value is the same. The intuition is similar: apparently, even though the chance of going close to the wall shrinks as we go farther, in that tiny chance that we do go there, the chance of us exiting also shrinks as well, thus we bump the wall many more times that it offsets the probability completely.

The main idea here is that we can view this as a series of events as well as a compound event, and look at the average of brilli's position before and after each even. Our compound event is brilli reaching the point 100, which has an expected value of 100, while the individual events are (a) brilli flipping the coin at a position other than -1000, which has an expected value of 0, and (b) flipping the coin at position -1000, which has an expected value of 1.

Thus, we have that 100 = (the average number of coin flips on a position other than -1000) * 0 + (the average number of coin flips on position -1000) * 1, and thus it is clear that the average number of coin flip on position -1000 must be 100.

Note that it actually doesn't matter where the wall is, as the only number that really comes into play is how far off Brilli's goal is.