A Problem with Infinite Hotel Keys - Numberphile
Audio Brief
Show transcript
This episode explores a variation of the classic hat-check problem, set in Hilbert's Hotel with an infinite number of rooms, and asks what the probability is that at least one key ends up on its correct hook if all keys are randomly placed.
There are four key takeaways from this discussion. First, the probability of at least one person getting the right item in a random assignment problem is surprisingly not small, even with an infinite number of items. Second, when solving problems involving "at least one" success, it is often easier to calculate the probability of "zero" successes and subtract that from one. Third, the inclusion-exclusion principle is a powerful method for calculating probabilities of unions of events by alternating between adding and subtracting the probabilities of their intersections. And fourth, many complex probability problems simplify neatly when extended to an infinite case, often converging to values involving fundamental mathematical constants like Euler's number 'e'.
The problem initially seems counterintuitive; with infinite keys and hooks, one might expect the chance of any correct match to be infinitesimally small. However, this finding suggests that even in vast random assignments, some degree of correct matching is highly likely. The infinite setting of Hilbert's Hotel vividly illustrates this principle.
Calculating probabilities directly for "at least one" successful event can be complex. Instead, determining the probability of the complementary event, "zero" successes, provides a more straightforward path to the solution. This complementary probability approach is a powerful tool in statistics, transforming complex direct calculations into manageable inverse problems.
The inclusion-exclusion principle provides a systematic approach to counting elements in the union of multiple sets. It involves summing individual set sizes, subtracting pairwise intersections, adding back three-way intersections, and so on, with alternating signs. This method is crucial for accurately calculating the probability of at least one event occurring among many possibilities.
A remarkable aspect of this problem is how the solution converges to a constant value related to Euler's number 'e' as the number of keys approaches infinity. Specifically, the probability that at least one key is correct is one minus one over 'e', or approximately 63%. This highlights how fundamental constants often govern the behavior of infinite systems, offering elegant solutions to seemingly intractable problems.
These insights reveal the elegant and often counterintuitive nature of probability when applied to infinite systems, demonstrating how complex problems can yield surprisingly simple and profound mathematical truths.
Episode Overview
- The episode explores a variation of the classic "hat-check problem" set in the context of Hilbert's Hotel, which has an infinite number of rooms.
- The core question is: If all the infinite keys are muddled in a bucket and randomly placed on hooks, what is the probability that at least one key ends up on its correct hook?
- The host, Dr. Tom Crawford, uses the inclusion-exclusion principle to break down the problem for a finite number of keys (n).
- The solution surprisingly converges to a constant value related to Euler's number (e) as the number of keys approaches infinity.
Key Concepts
- Hilbert's Hotel Paradox: A thought experiment illustrating the counterintuitive properties of infinite sets, used here as a fun setting for an infinite probability problem.
- Derangement Problem: This is the classical name for the problem being discussed. A derangement is a permutation of the elements of a set, such that no element appears in its original position. The video calculates the probability of the opposite of a derangement (at least one correct placement).
- Inclusion-Exclusion Principle: A counting technique for finding the size of a union of multiple sets. It involves systematically adding the sizes of the individual sets, subtracting the sizes of all pairwise intersections, adding back the sizes of all three-way intersections, and so on, with alternating signs.
- Euler's Number (e): The mathematical constant approximately equal to 2.718. The solution involves the Taylor series expansion for e^x, specifically for e^-1, which is equal to 1/e.
- Factorials: The product of all positive integers up to a given integer (e.g., 5! = 5 × 4 × 3 × 2 × 1). The probability calculations in the inclusion-exclusion principle simplify to terms involving factorials.
Quotes
- At 00:23 - "All of those infinite keys are just in a big old bucket. And we have to figure out... what is the probability we actually end up putting the correct key on the correct room hook?" - The host clearly and concisely states the core problem of the episode.
- At 05:05 - "What we've got here is the n=2 and n=3 version of something called the inclusion-exclusion principle, which is an excellent name because it basically tells you what to do." - Dr. Crawford introduces the key mathematical principle used to solve the problem.
- At 15:43 - "The probability that at least one key is correct is 1 - 1/e, which is about 63% chance." - The host reveals the final, counterintuitive answer for the infinite case.
Takeaways
- The probability of at least one person getting the right item in a random assignment problem is not small, even with an infinite number of items.
- When solving problems involving "at least one" success, it's often easier to calculate the probability of "zero" successes and subtract that from 1.
- The inclusion-exclusion principle is a powerful method for calculating probabilities of unions of events by alternating between adding and subtracting the probabilities of their intersections.
- Many complex probability problems simplify neatly when extended to an infinite case, often converging to values involving fundamental mathematical constants like 'e'.
