Finite ant crawling

Here’s another example of recursive probability in action on a different problem.

Suppose you are an ant crawling along the edges of an equilateral triangle \( ABC \). You start at point \( A \). Every minute, you choose uniformly at random one of the other two vertices and move to it. What is the probability that you return to where you started (point \( A \)) after exactly twelve minutes?

Well, okay, at first the question seems hard to grasp, so let’s try to approach it by first tackling simpler questions. What is the probability that you return to where you started after exactly one minute? Zero, since you can only make one move. Well that didn’t work! How about after two minutes? Now we’re getting somewhere, since you can do this via two different paths: one through point \( B \) and one through point \( C. \) There are four total paths you could take, so the probability in this case must be \( \frac{1}{2} \). Just out of curiosity/completeness, we could also ask ourselves what the probability of arriving at point \( B \) or point \( C \) is after two moves. By symmetry, these probabilities must be the same, and their sum, together with the probability of arriving at point \( A \) after two moves, must be \( 1. \) Hence, they must each have probability \( \frac{1}{4} \).

Believe it or not, we’re already in a position to solve the original problem! The key is to think recursively. With this in mind, let \( p_{k} \) denote the probability of returning back to where you started after \( 2k \) minutes. We already know that \( p_1 = \frac{1}{2}. \) For \( k \) greater than \( 1 \), we want to relate \( p_k \) to \( p_{k-1} \). In other words, once you’ve made \( 2k – 2 \) steps, what is the probability that after taking two more steps, you are back to where you started?

This depends on where you are after \( 2k – 2 \) steps. So we can just break it down into all the cases! You’re at point \( A \) with probability \( p_{k-1} \), and from here, the probability of taking two more steps and getting back to point \( A \) is simply \( \frac{1}{2} \) as we computed before. You’re at either of points \( B \) or \( C \) with a sum total of probability \( 1 – p_{k-1} \), and from each of those cases, the probability of taking two more steps and getting back to point \( A \) is \( \frac{1}{4} \), also as calculated before. So we are finally in a position to write down our recursive equation:

\( p_k = \frac{1}{2}p_{k-1} + \frac{1}{4}(1 – p_{k-1}) \)

Simplifying,

\( p_k = \frac{1}{4}(p_{k-1} + 1). \)

Thus, turning the crank a few times, starting with \( p_1 = \frac{1}{2} \), we get \( p_2 = \frac{3}{8}, p_3 = \frac{11}{32}, p_4 = \frac{43}{128}, p_5 = \frac{171}{512}, \) and finally, \( p_6 = \frac{683}{2048}. \) (Note that our final answer is very close to \( \frac{1}{3} \), which makes intuitive sense.)

There are actually many other ways to approach the same problem (one could, for instance, create a transition matrix), but this one is very simple and clean. In fact, it’s not too hard from here to come up with an explicit formula for \( p_k \) and prove that it is correct via induction. (A good exercise!)

Leave a Reply