Problem 71

Problem 71: Choosing keys ( $✓$ ) 2000 Paper II

I have $k$ different keys on my key ring. When I come home at night I try one key after another until I ﬁnd the key that ﬁts my front door. What is the probability that I ﬁnd the correct key, for the ﬁrst time, on the $n$ th attempt in each of the following three cases?

(i): At each attempt, I choose a key that I have not tried before, each choice being equally likely.
(ii): At each attempt, I choose a key from all my keys, each of the $k$ choices being equally likely.
(iii): At the ﬁrst attempt, I choose from all my keys, each of the $k$ choices being equally likely. At each subsequent attempt, I choose from the keys that I did not try at the previous attempt, each of the $k - 1$ choices being equally likely.

Comments

This is very easy, and would really be far too easy if the answers were given.

You should set out your argument clearly and concisely, because if you come up with the wrong answer and an inadequate explanation you will not get many marks. Even if you write down the correct answer you may not get the marks if your explanation is inadequate.

You should of course run the usual checks on your answers. Do they lie in the range $0 \leq p \leq 1$ ? If you sum over all outcomes, do you get 1? (The latter is a good and not difficult exercise; I insist that you try it.)

You will probably be struck by the simplicity of the answer to part (i), after simpliﬁcation. Is there an easy way of thinking about it (or, if you did it the easy way, is there a hard way)?

Solution to problem 71

\begin{array}{l} (i) \\ P(finding correct key, for the ﬁrst time, on n th attempt) \\ = P(fail ﬁrst, fail second, ... , fail (n - 1) th, succeed n th) \\ = \{\begin{matrix} \frac{1}{k} & f o r & n = 1; \\ \frac{k - 1}{k} \times \frac{k - 2}{k - 1} \times \dots \times \frac{k - (n - 1)}{k - (n - 2)} \times \frac{1}{k - (n - 1)} = \frac{1}{k} & f o r & 2 \leq n \leq k; \\ 0 & f o r & n > k . \end{matrix} \\ (ii) \\ P(ﬁnd correct key, for the ﬁrst time, on n th attempt) \\ = P(fail ﬁrst, fail second, ... , succeed n th) = {(\frac{k - 1}{k})}^{n - 1} \frac{1}{k} . \\ (iii) \\ P(ﬁnd correct key, for the ﬁrst time, on n th attempt) \\ = P(fail ﬁrst, fail second, ... , succeed n th) \\ = \{\begin{matrix} \frac{1}{k} & f o r & n = 1; \\ (\frac{k - 1}{k}) {(\frac{k - 2}{k - 1})}^{n - 2} \frac{1}{k - 1} & f o r & n \geq 2 . \end{matrix} \end{array}

Post-mortem

The above solution for part (i) is the ‘hard way’. The easy way is to consider the keys all laid out in a row, instead of being picked sequentially. Exactly one of the keys is the correct one, which is equally likely to be any of the keys in the row, so has a probability of $1 ∕ k$ of being in any given position. Clearly, this corresponds exactly to picking them one by one.

I gave the hard solution above, because I think most people will be drawn into doing it this way by the phrasing of the question: keys are picked one by one and tried before going on to the next.

Did you check that your probabilities sum to 1? It is obvious for part (i), but you have to sum geometric progressions for parts (ii) and (iii).