A Problem with Infinite Hotel Keys - Numberphile

Key Concepts

• Hilbert's Hotel: A hypothetical hotel with infinitely many rooms, all of which are occupied.
• Probability: The measure of the likelihood that an event will occur.
• Inclusion-Exclusion Principle: A counting technique that systematically adds and subtracts the probabilities of overlapping events to find the probability of their union.
• Union (of events): The event that at least one of a set of events occurs.
• Intersection (of events): The event that all of a set of events occur simultaneously.
• Factorial: The product of all positive integers less than or equal to a given positive integer (denoted by n!).
• Euler's Number (e): An irrational number approximately equal to 2.71828, which is the base of the natural logarithm.
• Exponential Function: A function of the form e^x, where e is Euler's number.

Problem Setup: The Infinite Key Problem

The video explores a probability problem related to Hilbert's Hotel. Imagine an infinite hotel with infinitely many rooms and an infinite number of keys, one for each room. All the keys are mixed up in a bucket. The question is: if you randomly assign keys to rooms, what is the probability that at least one key ends up on the correct room hook?

Defining Events and Notation

• A_i: The event that key i is placed on the correct hook i.
• The goal is to find the probability of A₁ or A₂ or A₃ or... (the union of all A_i).
• To handle infinity, the problem is first approached with a finite number of rooms, n, and then the limit as n approaches infinity is considered.

Inclusion-Exclusion Principle

The video explains and applies the inclusion-exclusion principle to solve the problem.

Explanation:

1. Include: Sum the probabilities of each individual event (P(A_i)).
2. Exclude: Subtract the probabilities of all pairs of events occurring together (P(A_i and A_j)).
3. Include: Add back the probabilities of all triplets of events occurring together (P(A_i and A_j and A_k)).
4. Continue: Alternate between including and excluding probabilities of increasing combinations of events.

Formula:

P(A₁ ∪ A₂ ∪ ... ∪ A_n) = Σ P(A_i) - Σ P(A_i ∩ A_j) + Σ P(A_i ∩ A_j ∩ A_k) - ... + (-1)ⁿ⁺¹ P(A₁ ∩ A₂ ∩ ... ∩ A_n)

where:

• The first summation is over all individual events.
• The second summation is over all pairs of events where i < j to avoid double-counting.
• The third summation is over all triplets of events where i < j < k to avoid double-counting.
• The last term's sign depends on whether n is odd or even.

Calculating Probabilities of Individual and Combined Events

• P(A_i): The probability of a single key being correct is 1/n, where n is the total number of keys (and rooms).
• P(A_i ∩ A_j): The probability of two specific keys being correct is (1/n) * (1/(n-1)).
• P(A_i ∩ A_j ∩ A_k): The probability of three specific keys being correct is (1/n) * (1/(n-1)) * (1/(n-2)).
• In general, the probability of k specific keys being correct is 1 / (n * (n-1) * (n-2) * ... * (n-k+1)).

Counting the Number of Terms in Each Summation

• The number of terms in the first summation (individual events) is n.
• The number of terms in the second summation (pairs of events) is n * (n-1) / 2. This is because there are n choices for the first key and n-1 choices for the second key, but the order doesn't matter, so we divide by 2.
• The number of terms in the third summation (triplets of events) is n * (n-1) * (n-2) / (3 * 2).
• These are combinations, and can be expressed using the "choose" function from combinatorics.

Substituting into the Inclusion-Exclusion Formula

Substituting the probabilities and the number of terms into the inclusion-exclusion formula, the expression simplifies significantly:

P(at least one correct key) = n * (1/n) - [n * (n-1) / 2] * [1 / (n * (n-1))] + [n * (n-1) * (n-2) / (3 * 2)] * [1 / (n * (n-1) * (n-2))] - ...

This simplifies to:

P(at least one correct key) = 1 - 1/2 + 1/(3 * 2) - 1/(4 * 3 * 2) + ... = 1 - 1/2! + 1/3! - 1/4! + ...

Connecting to Euler's Number (e)

The resulting series is related to the Taylor series expansion of e^x:

e^x = Σ (x^k / k!) from k=0 to infinity

Setting x = -1, we get:

e^-1 = Σ ((-1)^k / k!) from k=0 to infinity = 1 - 1/1! + 1/2! - 1/3! + 1/4! - ...

Therefore, the probability of at least one key being correct is:

P(at least one correct key) = 1 - e^-1 = 1 - (1/e) ≈ 0.6321

Conclusion

The probability that at least one key ends up on the correct hook in Hilbert's infinite hotel is approximately 63.21%. This result is derived using the inclusion-exclusion principle, combinatorial arguments, and the Taylor series expansion of the exponential function. The video highlights the surprising result that even with an infinite number of rooms and keys, there's a significant chance that at least one key will be correctly placed.