A few years ago Canadian lottery officials learned the importance of careful counting the hard way when they decided to give back some unclaimed prize money that had accumulated. They purchased 500 automobiles as bonus prizes and programmed a computer to determine the winners by randomly selecting 500 numbers from their list of 2.4 million subscriber numbers. The officials published the unsorted list of 500 winning numbers, promising an automobile for each number listed. To their embarrassment, one individual claimed (rightly) that he had won two cars. The officials were flabbergasted—with over 2 million numbers to choose from, how could the computer have randomly chosen the same number twice? Was there a fault in their program?

The counting problem the lottery officials ran into is equivalent to a problem called the birthday problem: how many people must a group contain in order for there to be a better than even chance that two members of the group will share the same birthday (assuming all birth dates are equally probable)? Most people think the answer is half the number of days in a year, or about 183. But that is the correct answer to a different question: how many people do you need to have at a party for there to be a better than even chance that one of them will share your birthday? If there is no restriction on which two people will share a birthday, the fact that there are many possible pairs of individuals who might have shared birthdays changes the answer drastically. In fact, the answer is astonishingly low: just 23. When pulling from a pool of 2.4 million, as in the case of the Canadian lottery, it takes many more than 500 numbers to have an even chance of a repeat. But still that possibility should not have been ignored. The chances of a match come out, in fact, to about 5 percent. Not huge, but it could have been accounted for by having the computer cross each number off the list as it was chosen.Excerpted from ‘The Drunkard’s Walk – How Randomness Rules our Lives’ by Leonard Mlodinow