modulomathy.com

#math trivia: Each day there’s a 20% chance that a given class has a quiz. What’s the chance that at least one of the five classes does?

— Burt Kaliski Jr. (@modulomathy) September 25, 2012

To determine the chances that something happens at least once, it’s often easiest to figure out the probability p that it doesn’t happen at all. Either the event doesn’t happen, or it happens at least once, so the latter probability is then 1-p.

In the present example, the probability that a particular class doesn’t have a quiz on a given day is 80%, or 4/5.

The probability that all five classes don’t have a quiz is thus

p = (4/5)*(4/5)*(4/5)*(4/5)*(4/5) = 1024/3125

which is about 33%. It follows that the probability that at least one class has a quiz on a given day is 1-p = 2101/3125, or about 67%.

Note:  The preceding analysis assumes that the chances that one class has a quiz is independent of the chances that any other class does, which is why the probabilities can be multiplied together. A situation where the chances would not be independent is one in which exactly one class has a quiz every day, but the choice of class is made at random. In that situation, any given class, considered in isolation, would have a 20% chance of being selected for a quiz. However, once it was known that one of the other classes had a quiz, it would be clear that the given class wouldn’t have one (relief!); and once it was known that one of the other classes didn’t have a quiz, it would be clear that the given class was more likely to have one.

Independence means that knowing the state of the other classes doesn’t affect the chances of this particular class having a quiz, which is a reasonable assumption in a math trivia problem unless stated otherwise.  Because of independence, it would be incorrect just to add the 20% probabilities across the five classes and assume that the chances that at least one class had a quiz would then be 100%. (What if there were six classes? Would it be 120%?) The chances that the first class has a quiz is 20%, and the chances that the second class has a quiz is also 20%. However, the chances that at least one of them has a quiz is not 40%, but 36%. The reason is that there’s a 4% chance (20% * 20%) that they both have a quiz. This 4% chance is double-counted if we add 20% and 20%. Extending the logic, we’d get the same 67% result as determined above.

A simpler case if you need one more way to check the logic: If you flip two fair coins, and each has a 50% chance of heads, what’s the chance that you get at least one heads? It’s clearly not 100%. You could either look at the chances of getting no heads (50% * 50% = 25%) and subtract that from 100% to get 75%; of look at the chances of getting two heads, again 25%, and subtract that from the 50% + 50% to avoid double-counting, and again get 75%. Assuming, of course, that the two coin flips are independent.

Beyond the trivia: Suppose that instead of five classes, there were n, and instead of a probability of 1/5 that a given class has a quiz, it was 1/n. As n grows large, the probability that at least one of the n classes has a quiz approaches a limit of (1-e^-1), where e is the base of the natural logarithms (2.712…). This is about 63%.

The proof is quite elegant. As n grows large, the value e^-1/n approaches (1-1/n). Now the probability that a given class doesn’t have a quiz is (1-1/n), which is thus approximately e^-1/n. The probability that all n classes don’t have a quiz, assuming independence, is (1-1/n)ⁿ, which is approximately (e^-1/n)ⁿ = e^-1. It follows that the probability that at least one class has a quiz approaches 1-e^-1. The values determined above illustrate this trend: 75% for n = 2, 67% for n = 5, eventually converging to around 63%. This is a good ratio to keep in mind when solving any “balls in bins” problem, e.g., if I thrown n balls such that each one falls randomly into one of n bins, what are the chances that any particular bin gets at least one ball? If n is large enough, it’s about 63%.