Professor X smokes a pipe. He carries two identical matchboxes, originally containing 20 matches each. When he lights his pipe, he chooses a matchbox at random and lights his pipe with one match and discards the used match.

There will eventually arise an occasion when he first selects a matchbox with only one match in it. At this point, what is the expected number of matches in the other box?

(In reply to Corrected Solution after Charlie's comments by Dan Rosen)

Just to take an easy-to-calculate probability in your summation: P20:

A20 is just 2, while summation of AN over N=1 to N=20 is 137846528820.

But P20 is easily shown to be other than 2/137846528820. N=20 comes about when the first 19 are all the same box, and the professor again chooses that box. That has probability (1/2^18)/2, or if you prefer 2*(1/2^19)/2. Either way that's 1/2^19 = 1/524288, which is considerably larger than 2/137846528820.

Your P1 is 70690527600/137846528820 = 0.5128205128205128205

This is presumably the probability that the "other" box already contains just a single match when the professor selects a box that also has just one match. In turn, this means that the first 38 matches were equally divided between the two boxes. What is the probability that the professor's choices will be like that? There are 2^38 ways the professor could choose the sequence, and 2*C(38,19) of these satisfy this condition. That makes this probability 70690527600/274877906944 = 4418157975/17179869184 = 0.2571706412709318101.

The smaller sequences need a smaller denominator; they cover all the possible choices that the professor might have made after that. That's another way of looking at it. You can't use the full sum from 1 to 20. To take a smaller example, the ways of producing 122112222 have to count more than the ways of producing, say 12222111122, when seeking the first to take 6 from one box.

Posted by Charlie on 2010-06-29 17:32:52