# Probability Problem with $n$ keys

A woman has $n$ keys, one of which will open a door. a)If she tries the keys at random, discarding those that do not work, what is the probability that she will open the door on her $k^{\mathrm{th}}$ try?

Attempt: On her first try, she will have the correct key with probability $\frac1n$. If this does not work, she will throw it away and on her second attempt, she will have the correct key with probability $\frac1{(n-1)}$. So on her $k^{\mathrm{th}}$ try, the probability is $\frac1{(n-(k-1))}$ This does not agree with my solutions.

b)The same as above but this time she does not discard the keys if they do not work.

Attempt: We want the probability on her $k^{\mathrm{th}}$ try. So we want to consider the probability that she must fail on her $k-1$ attempts. Since she keeps all her keys, the correct one is chosen with probability $\frac1n$ for each trial. So the desired probability is $(1-\frac{1}{n})^{k-1} (\frac1n)^k$. Again, does not agree with solutions.

I can't really see any mistake in my logic. Can anyone offer any advice? Many thanks

• Presumably the $(1/n)^k$ part at the end is a typo, you mean $1/n$. – André Nicolas Nov 28 '12 at 23:21
• Basis of a kvpy problem 2009 sa! – Pole_Star Oct 21 '17 at 14:36

For $(a)$, probability that she will open on the first try is $\dfrac1n$. You have this right.

However, the probability that she will open on the second try is when she has failed in her first attempt and succeeded in her second attempt. Hence, the probability is $$\underbrace{\dfrac{n-1}n}_{\text{Prob of failure in her 1^{st} attempt.}} \times \underbrace{\dfrac1{n-1}}_{\text{Prob of success in 2^{nd} attempt given failure in 1^{st} attempt.}} = \dfrac1n$$

Probability that she will open on the third try is when she has failed in her first and second attempt and succeeded in her third attempt. Hence, the probability is $$\underbrace{\dfrac{n-1}n}_{\text{Prob failure in her 1^{st} attempt.}} \times \underbrace{\dfrac{n-2}{n-1}}_{\text{Prob of success in 2^{nd} attempt given failure in 1^{st} attempt.}} \times \underbrace{\dfrac1{n-2}}_{\text{Prob of success in 3^{nd} attempt given failure in first two attempts.}} = \dfrac1n$$ Hence, the probability she opens in her $k^{th}$ attempt is $\dfrac1n$. (Also note that the probabilities must add up-to one i.e. $$\sum_{k=1}^{n} \dfrac1n = 1$$ which is not the case in your answer).

For $(b)$, the probability that she will open on her $k^{th}$ attempt is the probability she fails in her first $(k-1)$ attempts and succeed in her $k^{th}$ attempt. The probability for this is $$\underbrace{\dfrac{n-1}{n}}_{\text{Fails in 1^{st} attempt}} \times \underbrace{\dfrac{n-1}{n}}_{\text{Fails in 2^{nd} attempt}} \times \cdots \underbrace{\dfrac{n-1}{n}}_{\text{Fails in (k-1)^{th} attempt}} \times \underbrace{\dfrac1{n}}_{\text{Succeeds in k^{th} attempt}} = \left(1-\dfrac1n \right)^{k-1} \dfrac1n$$ Again a quick check here is the sum $$\sum_{k=1}^{\infty} \left(1-\dfrac1n \right)^{k-1} \dfrac1n$$ should be $1$. Note that here her number of tries could be arbitrarily large since she doesn't discard the keys from her previous tries.

• These ought to say "probability of failure in 2nd attempt GIVEN failure in 1st attempt" etc. They're conditional probabilities. – Michael Hardy Nov 28 '12 at 22:47
• Thank you for the reply. Could you elaborate on how you arrived at ''the probability of failure in her second attempt'' – CAF Nov 28 '12 at 22:47
• @CAF For part $a$, on her second attempt, since has discarded the key she chose from her first attempt she only has $n-1$ keys to choose from. Hence, the probability she picks the right key is $\dfrac1{n-1}$. – user17762 Nov 28 '12 at 22:50
• @MichaelHardy I define success and failure as success and failure for each turn and not for the overall event. – user17762 Nov 28 '12 at 22:51
• @Marvis: But you have $\frac{n-2}{n-1}$ for the prob of failure in second attempt? – CAF Nov 28 '12 at 22:57

In (a) you’re calculating the probability that she will open the door on the $k$-th try given that she did not open it earlier; this is not the same as the probability that she will open it on the $k$-th try. Perhaps the easiest way to look at it is to notice that there are $n!$ equally likely orders in which she can try the keys. She opens the door on the $k$-th try if and only if the right key is in position $k$ in the order that she actually uses. The other $n-1$ keys can be in any order, so there are $(n-1)!$ orders with the right key in position $k$, and the probability that she will choose one of those orders is $$\frac{(n-1)!}{n!}=\frac1n$$ irrespective of $k$.

• But what if $k=n$? Shouldn't the probability be $1$ because she has discarded all other keys? – Guacho Perez Apr 10 '16 at 17:19
• @Guacho: No: she will open the door on the last try if and only if the correct key is the last one that she tries. Since the correct key is equally likely to be in any position in the order in which she tries keys, the probability that it is the last one tried is $\frac1n$. – Brian M. Scott Apr 10 '16 at 19:02
Every key in the sequence is equally likely to be the one that opens the door, so the probability is $1/n$.
The first key works with probability $1/n$.
The conditional probability that the second key works, given that the first failed, is $1/(n-1)$.
Next we have $1/(n-2)$, and so on.
So for example, the probability that the fourth one works is $$\Pr(\text{1st fails})\cdot\Pr(\text{2nd fails}\mid\text{1st fails})\cdot\Pr(\text{3rd fails}\mid\text{first 2 fail})\cdot\Pr(\text{4th works}\mid\text{first 3 fail})$$ $$= \frac{n-1}{n}\cdot\frac{n-2}{n-1}\cdot\frac{n-3}{n-2}\cdot\frac{1}{n-3}.$$ Do the obvious cancelations and get $1/n$.