3

I've ran into this tricky problem I can't seem to solve:

Suppose there are $n$ passwords, where only one allows you to log into a system. If the system blocks you out after 3 attempts, what is the probability of logging in?

The problem asks for the particular case when $n=10$, but I suppose this doesn't change much.

What I've tried:

Let $A_i=\text{The $i$-th key is the correct one.}$ Then $P(\text{Log in})=P(\bigcup A_i)$, $i=1,2,3$.

This yields (as the $A_i$ should be mutually exclusive) that the probability of logging in is $\frac {1}{n}+\frac {1}{n-1}+\frac {1}{n-2}$ but I know this is incorrect.

Why is my attempt wrong, and how do you solve this?

csTroubled
  • 139
  • Think of it as choosing $3$ passwords out of $n$ at the same time. The probability that the correct one is among them is $\frac3{n}$. There is no essential difference with choosing $3$ one by one. – drhab Sep 24 '16 at 18:44
  • Related: http://math.stackexchange.com/questions/1012075/probability-concerning-a-6-digit-password – ericw31415 Sep 24 '16 at 19:45

3 Answers3

3

You are almost correct:$$\Pr(\text{Login})=\Pr(\bigcup_{i=1}^3 A_i)=\sum_{i=1}^3\Pr(A_i)=\frac1{n}+\frac1{n}+\frac1{n}=\frac3{n}$$

We are dealing with disjoint equiprobable events. The probability that e.g the second key is the correct one is not smaller than the probability that the first key is the correct one.

edit:

In your try you actually calculate something else:$$\Pr(A_1)+\Pr(A_2\mid A_1^c)+\Pr(A_3\mid A_1^c\cup A_2^c)$$ which can be looked at as a senseless expression.

drhab
  • 151,093
  • 5
    But once you try one password, you won't try it again, will you ? So they are not equiprobable events... the more passwords you try, the most likely you are to break into the account... – Evariste Sep 24 '16 at 18:26
  • @Evariste yes, that's what I thought! – csTroubled Sep 24 '16 at 18:31
  • @Evariste If 10 passwords are in front of you (put there randomly) then each of them has the same probability of being the correct one. – drhab Sep 24 '16 at 18:33
  • Try to grasp it by thinking of case $n=3$. – drhab Sep 24 '16 at 18:35
  • But after you try one, you discard it (if it's wrong). – csTroubled Sep 24 '16 at 18:35
  • That fact does not change the original probabilities. – drhab Sep 24 '16 at 18:36
  • 2
    @drhab Nevermind, I think I got it... you pick the three passwords in one go with no repetition, so you don't actually try again... picking $3$ passwords out of $n$ is like cutting a bar of length $n$ and keeping a broken piece of length $3$, so the probability of getting the part of interest is $3/n$... Thank you – Evariste Sep 24 '16 at 18:37
  • @Evariste That is good thinking! – drhab Sep 24 '16 at 18:38
  • Perhaps add that explanation into the answer, 'cause comments aren't supposed to be treated as permanent... – Malady Sep 25 '16 at 01:36
  • @drhab But should the probability not change in a manner analogous to the Monty Hall problem; but instead of doors and a car we have passwords and the correct one? As soon as the host tells us that one of the passwords is incorrect, the probability of the others change? (Obviously it's different than the Monty Hall problem as in this one we didn't choose one password in order to be given a change to switch) – Quelklef Sep 26 '16 at 10:47
  • @drhab Also, in case of 2 passwords, the first has a 1/2 chance and the second has a 1 chance. Should this not act similarly for greater values of n? – Quelklef Sep 26 '16 at 10:49
  • @Quelklef If there are 2 passwords and exactly one of them is correct then the second has a change of $1$ to be correct under the extra condition that the first is not correct. Leaving out that condition gives it a chance of 1/2 to be correct. – drhab Sep 26 '16 at 10:52
  • @Quelklef Also in Monty Hall the original probabilities do not change. Someone who does not switch will win if his original choice was correct (probability $\frac13$). Someone who does switch will win if his original choice was wrong (probability $\frac23$). – drhab Sep 26 '16 at 10:57
2

Calculate $1$ minus the probability of the complementary event.

The complementary event is the event of failing to log in within $3$ attempts.

The total number of ways to choose $3$ different passwords is $\binom{n}{3}$.

The number of ways to choose $3$ different and incorrect passwords is $\binom{n-1}{3}$.

So the probability of failing to log in within $3$ attempts is $\frac{\binom{n-1}{3}}{\binom{n}{3}}=\frac{n-3}{n}$.

Hence the probability to log in within $3$ attempts is $1-\frac{n-3}{n}=\frac{3}{n}$.

barak manos
  • 43,109
1

We can think like the following too (with conditional probabilities):

$Pr(Login) = Pr(A_1) + Pr(A_1^c \cap A_2) + Pr(A_1^c \cap A_2^c \cap A_3)$ $=Pr(A_1) + Pr(A_1^c)Pr(A_2|A_1^c) + Pr(A_1^c)Pr(A_2^c|A_1^c)Pr(A_3|A_1^cA_2^c)$, by chain rule $=\frac{1}{n}+\frac{n-1}{n}.\frac{1}{n-1}+\frac{n-1}{n}.\frac{n-2}{n-1}.\frac{1}{n-2}=\frac{3}{n}$

Sandipan Dey
  • 2,111
  • This is correct and might give the OP some sight on his wrong attempt. But observe that it can be simplified: $A_1^c\cap A_2=A_2$ and $A_1^c\cap A_2^c\cap A_3=A_3$. – drhab Sep 25 '16 at 11:01