bag of marbles
You have 100 marbles numbered 0 to 99 in a bag. You repeatedly draw a marble from the bag (all marbles being equiprobable), note its number, and replace it in the bag. On average, how many of the marbles numbered 1 through 99 will have been drawn from the bag (one or more times) before drawing marble #0?
Solution by Michael A. Gottlieb
The probability of drawing a given marble m (other than 0) before drawing marble 0 must be the same as the probability of drawing marble m for the first time before drawing marble 0 for the first time if you were to continue to draw (and replace) marbles until every marble (0-99) had been drawn at least once. However, there is nothing special about marbles m and 0 in this regard - the probability must be the same for any two given marbles. In particular, it must equal the probability that marble 0 occurs for the first time before marble m occurs for the first time, and therefore it must equal 1/2. The expected number of marbles that will be drawn before 0 is drawn is just the number of non-0 marbles (99) times the probability that each will be drawn before 0 is drawn (1/2), which is 99/2.