Chance at least one guest gets their own key

Question

A large number $N$ of hotel guests are each handed a room key, with the keys assigned by a uniformly random permutation. What is the probability that one or more guests receive the key to their own room?

Short answer

About $1-1/e\approx0.632$ . By inclusion–exclusion the probability is $1-\tfrac1{2!}+\tfrac1{3!}-\dots\pm\tfrac1{N!}$ , which converges very quickly to $1-e^{-1}$ as $N$ grows (the no-fixed-point, or derangement, probability tends to $1/e$ ).

Adapted from Crack, Heard on the Street, Q1.31, p.15; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Counting and Combinatorics
Sample Spaces, Events, and the Probability Axioms
Conditional Probability, Total Probability, and Bayes' Rule

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free