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