Recently, a problem was brought to my attention by one of our MTGK staff. The problem is this:
Twenty-five chips, each marked with a different integer from 1 through 25, are placed in a jar. A student draws a chip from the jar and tells everyone the number. The chip is then returned to the jar. Nine more students do the same thing. What is the probability that at least two of the ten students draw the same chip? Express your answer as a decimal to the nearest hundredth.
Alright, did you get it? It’s quite a tricky problem, especially if you haven’t seen this kind of thing before. In general, probability is quite a difficult subject for anyone uninitiated to wrap their head around. To understand this solution, you will need some familiarity with calculating probabilities, probability spaces, and permutations. Let’s give it a shot.
EXPERIMENTATION
When tackling a difficult probability problem, one of the first questions I ask myself is, “What are some possible results that would happen if we were to conduct an experiment similar to the one in stated in the problem?” Often, a great way to grab a foothold on understanding complex probability problems is to conduct the tasks described. For our problem, I decided to have random.org generate 100 numbers between 1 and 25. This gives us 10 sets of 10 numbers each. We can then compare each set so see how many contain two or more repeats. For readability, I used 10 columns, and had each column represent one execution of the experiment laid out in the problem. Here are the results (with repeats boxed):
Surprisingly, 9 out of 10 of the sets/columns of numbers contain repeats. The seventh set even went over and beyond our requirements, containing three 15s, three 16s, and two 13s. There were only five distinct numbers in that set! Overall, we recorded an experimental probability of 0.9, or 90% for sets containing more than one repeat! Although this is a rather low sample experiment, it’s still rather eye opening. The chance of getting repeats seems to be rather high. But how is that possible, you might be thinking. We are only selecting 10 numbers each time, less than half of the total numbers available to pick from. Surely, our data set was just a fluke, an lucky accident? Well, there’s only one thing to do now to see if our results were accurate, or out of the norm–the math!
THE SOLUTION
Mathematically, the probability of an event is defined as the total number of anticipated outcomes divided by the number of total possible outcomes. This yields a number between 0 and 1.
For our problem, calculating the total number of outcomes is easy, although it admittedly requires some computational might. Because each number has 25 possibilities, we have to multiply 25 by itself ten times (25 to the power of 10). Doing this (in a calculator) gives us a whopping 95 trillion (95,367,431,640,625 to be exact) possible ways to select 10 numbers, each from 1 to 25 inclusive, with repeats. And that’s just our denominator–half the problem. Keep in mind this number counts separately different orders of the same ten numbers. For example, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} is a different outcome from {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}. This is because our calculation, by default, takes into consideration different orders. In this sense, we are working with permutations, not combinations.
Calculating the anticipated, or wanted outcomes, is a bit trickier. How do we possibly count all the ways in which we could have at least two numbers repeat? Do we list out each case? But there’d be too many. Even finding the total number of outcomes with only two numbers repeating is no walk in the park.
THE INSIGHT
The key to answering this question lies in an observation of our problem. The problem asks “What is the probability that at least two of the ten students draw the same chip?” In our set of ten, at least two numbers repeating is the exact complement of no numbers repeating. The sum of the probabilities of these two events would be equal to 1! If you can calculate one of these probabilities, you can find the other. And calculating the probability that no numbers are repeating is much easier. To do that, we need a simple permutation. We want to count the number of orderings of 10 numbers out of 25 possible numbers. Using the formula, we get another staggering 11 trillion permutations (that is, 25! / (25-10)! = 11,861,676,288,000).
THE ANSWER
This means that the probability that no numbers are repeating is 11,861,676,288,000 / 95,367,431,640,625 ≈ 0.1243. Our last step, we take the complement: 1 – 0.1243 = 0.8757. Thus, our answer, when rounded to the nearest hundredth, is 0.88. Looking back, our experimental probability of 0.9 was right on the mark!
THE BIRTHDAY PROBLEM
Even after studying probability for years, the numbers and solutions can still be quite surprising. I’d like to provide some context to the problem we tackled today. In probability theory, there is a famous and counter-intuitive problem (these often go hand-in-hand with probability problems) known as the Birthday Problem. In fact, it feels so counter-intuitive that some call this problem the Birthday Paradox (though it is not a true paradox). The problem itself is a simple one:
In a set of n people, selected randomly, what is the probability that at least two of them have the same birthday?
Sound familiar? This problem is conceptually identical to our original problem. What makes this problem counter-intuitive are some of the resulting solutions.
When n is 23, the chance of some pair having the same birthday is a just over 50%. Only 23 people! With 70 people, the chance of two sharing a birthday increases to 99.9%! (Keep in mind, this is the chance that any two could have the same birthday. If you wanted to calculate the probability that you share a birthday with someone else in the room, you would use a different calculation.) Even so, these probabilities are shocking and unexpected. If you picked 70 days out of the year, that is less than 20% of the total number of days. Yet, picking randomly, you have only a 0.01% chance of picking 70 unique days. These matter-of-fact statements show the power of mathematics, and expose how our brains play tricks on us through making assumptions and expectations about things that we really have little true understanding of.