Posts Tagged ‘binomial coefficient’

Given n possible keys where they are all equally likely to be chosen. If only 3 keys are correct, then on average how many keys would I have to try to find a correct one?

First lest try to clarify the problem by picturing the following scenario. We have a bucket with n keys and we would like to open a door but only 3 keys will work. We randomly choose a key and try to open the door. If the door opens then we are done; but if it doesn’t open then we randomly choose another key and so on. Now if we were to attempt to open this door then we would expect to do so after trying m_1 keys, where m_1 is some number between 1 and n-2. So if a friend were to attempt to open this door then we would expect some number m_2 between 1 and n-2, and from a kth friend we would get a some number m_k also between between 1 and n-2. Hence, we could argue that on average we would need to try \frac{1}{k} \sum_{i = 1}^k m_i keys to find the correct one, but each m_i is a random variable so if we were to repeat this experiment then we might get a different average! However, if k is a large number then we would expect any experimental averages to be close to each other, and if we let k approach infinity then these averages would converge to the expected value.

So we are interested in calculating the expected value but first we need to derive a probability mass function which would tell us the probability of finding the correct key on the kth try, P(X = k). Then the expected value will be given by

\displaystyle  E[X] = \sum_{k = 1}^{n-2}k P(X = k) .

For P(X = 1), we are interested in

P(finding correct key on 1st try)

which is given by

P(X = 1) = \frac{\begin{array}{c}\#~of~ ways~ in~ which  \\ 1st~ choice~ could ~be~ a~ correct~ key \end{array}}{\begin{array}{c} \#~ of~ ways~ in~ which \\ 1st~ key~ could~ be~ chosen\\ \end{array}}.

Since there are 3 correct keys then there are 3 ways in which the 1st choice could be a correct key. And, since there are n keys then there are n ways in which 1st key could be chosen. So

P(X = 1) =  \displaystyle \frac{3}{n}.

For P(X = 2), we are interested in

P(finding correct key on 2nd try)

which can be thought of as

P(1st key was not correct and 2nd key is correct)

which is given by

P(X = 2) =  \frac{ \begin{array}{c} \#~of~ ways~ in~ which  \\ 1st~ choice~ could ~be~ incorrect\\ and~2nd~correct \end{array}}{\begin{array}{c} \#~ of~ ways~ in~ which \\ 1st~and~2nd~ keys~ could~ be~ chosen\\ \end{array}}.

Since there are n-3 ways in which 1st choice could be incorrect and 3 ways in which 2nd choice could be correct then by the fundamental principle of counting there are (n-3)3 ways in which 1st key could be incorrect and 2nd correct. Similarly, since there are n ways in which the 1st key could be chosen and (n-1) ways in which 2nd key could be chosen then thre are n(n-1) ways in which 1st and 2nd keys could be chosen. So,

P(X = 2) = \displaystyle \frac{(n-3)3}{n(n-1)}.

If follows that

P(X = 3) = \displaystyle \frac{(n-3)(n-3 - 1)3}{n(n-1)(n-2)}

so in general

P(X = k) = \displaystyle \frac{(n-3)(n-3 -1) \cdots (n-3 - (k-2))3}{n(n-1)(n-2) \cdots (n - (k-1))}

which can be simplified to

P(X = k)  = \displaystyle \frac{\displaystyle \binom{n-3}{k-1}3}{\displaystyle k\binom{n}{k}}

where the binomial coefficient \binom{N}{i} is defined to be coefficient of the of x^i in the polynomial expansion of (1 + x)^N.

So the average number of keys we would have to try, to find a correct key would be given by

\displaystyle E[X] = \sum_{k=1}^{n-2} \frac{\displaystyle \binom{n-3}{k-1}3}{\displaystyle \binom{n}{k}}

which results in

\displaystyle E[X] =  \frac{n+1}{4}.

Advertisements