8
$\begingroup$

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

  • 0
    Presumably the $(1/n)^k$ part at the end is a typo, you mean $1/n$.2012-11-28
  • 0
    Basis of a kvpy problem 2009 sa!2017-10-21

3 Answers 3

11

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.

  • 0
    These ought to say "probability of failure in 2nd attempt GIVEN failure in 1st attempt" etc. They're _conditional_ probabilities.2012-11-28
  • 0
    Thank you for the reply. Could you elaborate on how you arrived at ''the probability of failure in her second attempt''2012-11-28
  • 0
    @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}$.2012-11-28
  • 0
    @MichaelHardy I define success and failure as success and failure for each turn and not for the overall event.2012-11-28
  • 0
    @Marvis: But you have $\frac{n-2}{n-1}$ for the prob of failure in second attempt?2012-11-28
  • 0
    @CAF Oh I thought you were asking about probability of success in her second attempt in the previous equation. The same argument essentially. In her second attempt, since she has discarded the first key as incorrect, she has $n-1$ keys of which only one is the right key and the remaining $n-2$ keys are the wrong keys. Hence for her to fail in her second attempt she need to choose one of the $n-2$ keys from the total of $n-1$ keys. Hence, her probability of failure in her second attempt is $\dfrac{n-2}{n-1}$.2012-11-28
  • 0
    Nevermind. I see. Thank you to everyone for their replies. I really appreciate the fast and well-explained answers.2012-11-28
  • 0
    @Marvis : I was also defining success and failure for each trial and not for the overall event. I don't know what would make you think I was doing anything else. My point remains: They're _conditional_ probabilities.2012-11-29
  • 0
    @MichaelHardy Oh yes. you are right. I don't know what I was thinking earlier. Will edit it.2012-11-29
  • 0
    Just one last question here: Why is it that the probability of success on some trial,say the third trial, is necessarily given by P(failure on first)P(failure on second|failure on first)P(success on third|failure on first and second trials)? What probability law is this?2012-11-29
  • 0
    @CAF : $\Pr(A)\cdot\Pr(B\mid A)\cdot\Pr(C\mid A\ \&\ B)\cdot\Pr(D\mid A\ \&\ B\ \&\ C)$ $=\Pr(A\ \&\ B\ \&\ C\ \&\ D)$ etc. Success on the third trial is the same as failure on the first and second, followed by success on the third. Of course you don't need to view it that way, since a symmetry argument also shows that all trials are equally likely to be the one on which one succeeds.2012-11-29
2

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

I see nothing wrong with your answer to (b).

  • 0
    But what if $k=n$? Shouldn't the probability be $1$ because she has discarded all other keys?2016-04-10
  • 0
    @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$.2016-04-10
2

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