Searching for keys in a desk

Here’s a representative example of a situation I think about all the time.

I was at the lab and noticed my keys were missing. I was fairly sure I had left them in one of the ten drawers of my desk, but I didn’t know which one.

I opened the first drawer and the keys weren’t there. I opened the second drawer and they weren’t there either.

As I opened each additional drawer, I started to feel more and more certain that the keys would be in the next one, since I was fairly confident they were in the desk (prior probability of perhaps 90%), and there were fewer and fewer unsearched drawers remaining.

On the other hand, each time I open an empty drawer, it’s additional evidence that the keys aren’t in the desk at all, so I should become somewhat less confident to find them in the remaining drawers.

What is the rational way to feel here? As I open more drawers, should I be getting more or less confident that I’ll find my keys? Specifically, after I’ve searched k drawers out of N total,

  1. What is the probability that I will find the keys in the next drawer?
  2. What is the probability that I’ll find the keys in the desk at all?

After we’ve opened k empty drawers, the probability of finding the keys in the next drawer is

P(\textrm{keys in next}|k \textrm{ empty}) = P(\textrm{keys in next}|\textrm{keys in any})P(\textrm{keys in any}|k \textrm{ empty})

Since the keys could be in any of the remaining drawers with equal probability,

P(\textrm{keys in next}|\textrm{keys in any}) =1/(N-k)

What about the other term, P(\textrm{keys in any}|k \textrm{ empty})? We can use Bayes’ theorem to update our belief that the keys are in the desk (starting from prior \theta_0 = 0.9) after observing k empty drawers in a row. The posterior is:

P(\textrm{keys in any}|k \textrm{ empty}) = \frac{P(k \textrm{ empty}|\textrm{keys in any})P(\textrm{keys in any})}{ P(k \textrm{ empty}|\textrm{keys in any})P(\textrm{keys in any}) + P(k \textrm{ empty}|\sim\textrm{keys in any})P(\sim\textrm{keys in any})}

Now to evaluate each of these terms. The likelihood of opening k empty drawers given that the keys are in the desk, i.e., P(k \textrm{ empty}|{\textrm{keys in any}), is easy to calculate manually:

P(k \textrm{ empty}|{\textrm{keys in any})=\left(\frac{N-1}{N}\right) \left(\frac{N-2}{N-1}\right) ... \left(\frac{N-k}{N-k+1}\right)=\frac{N-k}{N}

The next term, P(\textrm{keys in any}), is just the prior: \theta_0 = 0.9.

In the denominator, P(k \textrm{ empty}|\sim \textrm{keys in any}) is clearly 1 — if the keys aren’t in the desk, it’s not surprising that we haven’t found them in the first k drawers.

Finally, P(\sim \textrm{keys in any}) is just 1-\theta_0.

The resulting expression gives the probability that the keys are in the desk at all after we’ve opened k empty drawers:

 P(\textrm{keys in any}|k \textrm{ empty}) =\frac{(N-k)\theta_0}{N-k\theta_0}

And using the expression above, the probability that we’ll find the keys in the next drawer is:

 P(\textrm{keys in next}|k \textrm{ empty}) =\frac{\theta_0}{N-k\theta_0}

Plotting the results for N=10, \theta_0=0.9, we find that counterintuitively, with each additional drawer that’s opened, the probability of finding the keys in the next drawer increases, while the probability of finding the keys in the desk at all decreases:

As we open more drawers without finding the keys, it becomes more likely that we’ll find them in the next drawer, but less likely that we’ll find them in the desk at all.

The two probabilities become equal at k=9, since obviously at that point there’s only one drawer left to open — if the keys are still in the desk, they’re in the last drawer.

I wondered whether it was always the case that P(\textrm{keys in next}|k \textrm{ empty}) increased with k, i.e., whether there are values of N and \theta_0 for which it would become less likely to find the keys in the next drawer after opening a few empty ones (which I might imagine if e.g. we had low confidence that the keys were in the desk in the first place, and \theta_0 were small). However, you can work out that \frac{\partial}{\partial k} P(\textrm{keys in next}|k \textrm{ empty}) =\left(\frac{\theta_0}{N-k\theta_0}\right)^2, which is strictly positive (but, as expected, it’s small if \theta_0 is small).

The ups and downs of the hope function in a hopeless search – a thorough discussion of this type of problem, where you are searching for an object where failure is possible. From chapter 15 of Subjective Probability