Another splinter of mathematics.

I'm jealous of the part IB maths students, who are taking their exams at the moment. Part of the reason for this is that one of them mentioned one of the questions from today's exam to me, and it's such a neat bit of maths that I have to share it.

The question is about a village idiot, who has to paint a fence. The fence is made up of a large number of slats in a circular arrangement. The idiot begins with a particular slat; let us call it his favourite. After painting any slat, he paints one of the two adjacent slats. He decides which of these two slats to paint next at random, for example by tossing a coin. He does not care whether he has painted a slat before: He follows the decision of the coin and, if necessary, adds multiple coats to some slats. Eventually, of course, he will have painted all of the slats; some particular slat will have the distinction of being painted last. Before he starts painting, can we tell which slat this is likely to be? That is, can we work out, for any given slat, the probability that it will be the last one to be painted?

We can, and the answer is striking and counterintuitive. Obviously, the chance that the idiot's favourite slat is the last to be painted is \small \rule[-1.5]{0.1}{0.1} 0. Let's fix our attention on some other slat, which I'll call 'the slat in question'. At some point, as the fool meanders about, he will paint one of the slats adjacent to the slat in question. The first time this happens, he will be painting the slat on one side without having begun work on the slat on the other side. So, at this point, the chance that the slat in question is the last to be painted is the chance that the idiot will, in his meanderings around the circle, reach the slat on the other side before he reaches the slat in question. In order to do so, he must paint all of the other slats.

Let us call this chance \small \rule[-1.5]{0.1}{0.1} p. So when, as he must, the fool eventually paints one of the adjacent slats, we can say with certainty that the chance we are interested in is \small \rule[-1.5]{0.1}{0.1} p. But this number \small \rule[-1.5]{0.1}{0.1} p doesn't depend at all upon how the idiot moves about until the point when he paints a neighbouring slat. So we may as well say, from the start, that the probability of the fool painting the slat in question is \small \rule[-1.5]{0.1}{0.1} p .

Now it is worth noting that nothing in the above argument, not even the value of \small \rule[-1.5]{0.1}{0.1} p, depends on which slat we were considering, except that it cannot be the idiot's favourite slat. So the probability of any of the other slats being painted last is the same: \small \rule[-1.5]{0.1}{0.1} p. Say there are \small \rule[-1.5]{0.1}{0.1} n slats in total. Then there are \small \rule[-1.5]{0.1}{0.1} n-1 slats that we might have considered, each of which the fool paints last with probability \small \rule[-1.5]{0.1}{0.1} p. Only one of the slats is painted last, so the probability that at least one is painted last is \small \rule[-1.5]{0.1}{0.1} (n-1)p. But this certainly happens, so \small \rule[-1.5]{0.1}{0.1} (n-1)p = 1. That is, \small \rule[-1.5]{0.1}{0.1} p = \frac{1}{n-1}.

This rather neat argument illustrates the power of the ideas in the Markov chains course. You may have thought I was doing something a little fishy in the fourth paragraph above. The main point of the course is that what I did was not fishy at all, and can be made completely rigorous. Finally, here's a question for those who know their stuff: What happens if the fool always moves clockwise with some probability \small \rule[-1.5]{0.1}{0.1} q, and anticlock wise with probability \small \rule[-1.5]{0.1}{0.1} (1-q)? I'm afraid you'll need to do a little calculation to get at the answer.