# Keys without replacement probability

A drunk reaches home and wants to open his front door. He has 5 keys on his key chain and tries them one at a time. He is alert enough to eliminate unsuccessful keys from the subsequent selections. Let X denote the number of keys he tries in order to find the one that opens the door. Set up a sample space and find the distribution of X. Find E(X). Give an interpretation of E(X).

## 2 Answers

Let the sample space be $\{i:\ 1,2,3,4,5\}$ where $i$ means that the drunk uses $i$ keys. The corresponding probabilities are

$P(\{1\})=\frac15$ because she finds the good key at once.

$P(\{2\})=\left(1-\frac15\right)\frac14$ because her first try is a failure but then she finds the right key.

$P(\{3\})=\left(1-\frac15\right)\left(1-\frac14\right)\frac13$ because ...

$P(\{4\})=\left(1-\frac15\right)\left(1-\frac14\right)\left(1-\frac13\right)\frac12$ because ...

$P(\{5\})=\left(1-\frac15\right)\left(1-\frac14\right)\left(1-\frac13\right)\left(1-\frac12\right)$ because ...

Then the expectation of the number of keys used

$$E[X]=\frac15+2\frac45\frac14+3\frac45\frac34\frac13+4\frac45\frac34\frac23\frac12+5\frac45\frac34\frac23\frac12=3.$$

An alternative approach: Since the drunk eliminates incorrect keys from further attempts, the algorithm effectively produces a permutation of the five keys. The actual number of keys tried equals the position of the correct key. By symmetry, the average position is the third key, so the average number of keys tried is also $3$.