How many keys will we try before opening the door? [closed]

Question

You have N keys, exactly K of which will open your door. If you tries keys at random and you never try the same key twice, then X is the number of keys you will try before opening the door.

X is a Random Variable, which means it will take on different values due to chance, but some values may be more likely than others.

I have derived the PMF for this distribution, which gives the Probability that X = k, where k can take integer values between 1 and N-K+1.

For example: If we have N=10 keys, and K=3 of them will open the door, the probability that it takes us 4 tries to open the door is given by: Pr(X = 4 | N=10, K=3) = 0.125

The Puzzle

Find the Expected Value of X.

In other words, given the parameters N and K, how many keys should we expect to try before opening the door.

Your answer should be a function of N and K. You can assume N and K are both positive integers. Here are some Expected Values of X given specific values for N and K.

• E(X| N=10, K=3) = 2.75
• E(X| N=12, K=3) = 3.25
• E(X| N=15, K=3) = 4
• E(X| N=25, K=15) = 1.625
• E(X| N=35, K=15) = 2.25
• E(X| N=50, K=2) = 17

Moreover,

• If K = N, your function should return 1
• If K > N, your function should return 0
• Finally, if K = 1, then X is known as a Discrete Uniform Random Variable, and your function should return (N + 1)/2

Answer 1

If $N\ge K$, then $F(N,K)=\frac{N+1}{K+1}$, which can be proved by induction:

If $N=K$, then $F(N,K)=1=\frac{N+1}{K+1}$.

Otherwise, consider what happens if you try a key. It works with probability $\frac{K}{N}$, and fails with probability $1-\frac{K}{N}$. If it fails, you now have $N-1$ keys, of which $K$ work. So $F(N,K)=1+(1-\frac{K}{N})F(N-1,K)=1+(\frac{N-K}{N})\frac{N}{K+1}=1+\frac{N-K}{K+1}=\frac{N+1}{K+1}$, as desired.

Answer 2

Alternate way to derive the formula:

Imagine that someone arranges the $N-K$ non-working keys and $K+1$ markers in a circle in random order. One of the markers is chosen at random as a starting point, and the rest are replaced with working keys. We try each key, starting with the one right after the starting point, until we find one that works. We want to know the expected distance from the starting point to the first working key.

If we consider the situation before the starting position is chosen, and sum the distances from each marker to the next, we get $N+1$, the total number of positions in the circle. Each marker is equally likely to become the starting point, so the average distance is $\frac{N+1}{K+1}$.