Consider N holes arranged in a circle on a wooden board. A marble is placed in one of them. You toss a fair coin to determine if you should move the marble one hole clockwise or one hole counterclockwise. You keep doing this until the marble has been in each hole at least once.

What is the probability that each of the N holes turns out to be the last hole visited by the marble? Number the holes 1 through N, clockwise starting with the hole in which the marble starts. Obviously the probability for hole 1 is zero, since it already has the marble and there are other holes to visit still.

If n is even:

Use p(n) to signify the probability that the last hole to be visited will be hole n.

Consider various p(i) values conditional on whether the marble first moves CW or CCW. Start with p(3).  If the marble's first move is CW, then the conditional probability of 3 being the last hole visited would be p(2), as it would then have the same relative position to hole 2 (where the marble would be) as hole 2 has to hole 1 (where the marble starts).  On the other hand, if the marble initially went CCW, then the conditinal probability of 3 being the last hole would be p(4).  Since it's equally likely that the initial move would be CW or CCW, p(3) = (p(2)+p(4))/2.

Similar considerations make p(4)=(p(3)+p(5))/2, etc., that is, p(i)=(p(i-1)+p(i+1))/2.  Note that this does not work for i=2, as hole 2 is adjacent to the special hole 1.  This works until the route becomes shorter going in the other direction around the circle.  For even i, the last i for which it works is i = n/2+1, where p(n/2+1)=(p(n/2) + p(n/2 + 2))/2.  But p(n/2+2) = p(n/2) by symmetry.  But if that's the case, then p(n/2+1) must equal p(n/2), and tracking all the way back to p(2)=p(n), these must be equal as well.  Thus all the probabilities except p(1) must be equal, at 1/(n-1).

For example, when n=6,

p(2)=p(6)
p(3)=p(5)

p(3)=(p(2)+p(4))/2
p(4)=(p(3)+p(5))/2 = (p(3)+p(3))/2 = p(3)

p(3)=(p(2)+p(3))/2, so p(2)=p(3) and p(6)=p(3)
and we already knew that p(5)=p(3).

For odd n, it works similarly, such as for n=7:

p(2)=p(7)
p(3)=p(6)
p(4)=p(5)

p(3)=(p(2)+p(4))/2
p(4)=(p(3)+p(5))/2

the latter being also
p(4)=(p(3)+p(4))/2, so p(4)=p(3)
then p(3)=(p(2)+p(3))/2, so p(2) = p(3).

So all the probabilities except for the first hole, are equal to 1/(n-1).

Posted by Charlie on 2004-12-28 20:15:47