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!)

Infinite coin flipping

Suppose Alice and Bob decide to play the following simple game: they alternate turns flipping a coin, and whoever gets heads first immediately wins. (Alice gets the privilege of going first.) What are Alice’s chances of winning this game?

To make it more general, let’s suppose the coin is heads with probability $$x$$, where $$0 \le x \le 1$$. There are two approaches to solving this problem. Let’s look at the ‘brute force’ way first. Alice only gets to flip the coin on the first, third, fifth, seventh, … turns. Thus, her chances of winning the game must be equal to the infinite sum of her chances of winning on each of those respective turns. On the first turn, her chance of winning is $$x$$. In order to win on turn three, all previous flips must have been tails. Thus, her chances of winning in this case are $$(1-x)^{2} x$$. Similarly, on turn five, her chances of winning are $$(1-x)^{4} x$$, and this suggests that on turn $$2n + 1$$, her chances of winning are $$(1-x)^{2n} x$$. Thus, her chances of winning the game in total are

$$\displaystyle \sum_{n=0}^{\infty} (1-x)^{2n} x.$$

This is a geometric series with first term $$x$$ and ratio $$(1-x)^{2}$$, so it is equal to $$\frac{x}{1 – (1-x)^{2}} = \frac{x}{2x – x^{2}} = \frac{1}{2 – x}.$$ So for instance, if the coin is fair, $$x = \frac{1}{2}$$ and Alice’s chances of winning are $$\frac{1}{2 – \frac{1}{2}} = \frac{2}{3}.$$

While this approach certainly was successful, let’s look at a slicker alternative. Starting over, let’s denote the probability that Alice wins the game by $$P$$. Then of course the probability that Bob wins the game is $$1 – P$$. Instead of putting ourselves in Alice’s shoes, let’s pretend for a minute that we are Bob. Suppose Alice goes first and throws tails. Now, as Bob, we are pretty happy! It’s almost as though we get to go first now …

Well wait a minute, it is exactly as though we get to go first now! This observation actually tells us something: the original probability of Bob winning the game must be equal to the probability of Alice winning the game while first throwing tails. In equations, this means that $$(1 – P) = P(1 – x)$$. Now we can simply solve for $$P$$:

$$1 = P(1-x) + P$$

$$1 = P(2 – x)$$

So $$P = \frac{1}{2-x}$$, just as before. (Notice that our answer makes intuitive sense: as $$x \searrow 0$$, Alice’s probability of winning approaches $$\frac{1}{2}$$ from above, and as $$x \nearrow 1$$, Alice’s probability of winning approaches $$1$$ from below.)

This approach to probability is essentially recursive, and we’ll see more of it in the next post.