2
$\begingroup$

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
|improve this question
$\endgroup$
  • 1
    $\begingroup$ I suggest you rewrite the puzzle to make it more like a puzzle. Right now, it will probably be VTCed as a math problem. $\endgroup$ – Rohcana Oct 1 '15 at 17:26
  • $\begingroup$ The math is just for background to make it more interesting. The puzzle is simply, given input and output find the function (should be an elementary function). The probability background just gives it physical meaning $\endgroup$ – knrumsey Oct 1 '15 at 17:31
  • 1
    $\begingroup$ I understand what the puzzle is. I'm just saying that from the surface it seems that the question has little to do with puzzles. While the puzzle isn't actually (IMO) overly mathy probability mass function, discrete random variable, PMF, generalized Expected Value these type of terms will probably discourage people to view this as a puzzle and makes the problem hard to understand for the average reader. $\endgroup$ – Rohcana Oct 1 '15 at 17:37
  • $\begingroup$ In fact, your puzzle can be summed up as $ $ Given N keys, K of which are correct, what is the expected number of tries to open the lock? $\endgroup$ – Rohcana Oct 1 '15 at 17:43
  • $\begingroup$ I edited the puzzle, to remove some emphasis on the Probability. But your 'summed up' version of my puzzle requires heavy math and knowledge of probability theory. I am simply asking for a function based on some inputs and outputs in an interesting/meaningful setting. $\endgroup$ – knrumsey Oct 1 '15 at 17:45
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Very good! Also note that if K = 1, F(N,K) = (N+1)/2 $\endgroup$ – knrumsey Oct 1 '15 at 17:50
4
$\begingroup$

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}$.

|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.