Question

A student uses n passwords, but forgets which one is for his email.
If the student tries the passwords at random (even multiple times in a row, suspecting
a typo), what is the probability that the student will need exactly k tries to login?
What if the student writes down tried passwords and doesn't reuse them?

Answer 1

The probability to choose the correct password = 1/n

The probability to choose the incorrect password = 1-(1/n) = (n-1) / n

The probability that the student will need exactly k tries to login = Probability that incorrect password is chosen (k-1) times and correct password was chosen in kth try

= [(n-1) / n]^k-1 [1/n]

= (n-1)^k-1 / n^k

If the student writes down tried passwords and doesn't reuse them, then,

probability that incorrect password on 1st try = (n-1)/n

probability that incorrect password on 2nd try = (n-2)/(n-1) {There is a mail password in n-1 remaining passwords}

probability that incorrect password on 3rd try = (n-3)/(n-2)   {There is a mail password in n-2 remaining passwords}

....

probability that incorrect password on (k-1)th try = (n-k+1)/(n-k+2)   {There is a mail password in n-k+2 remaining passwords}

probability that correct password on (k)th try = 1/(n-k+1)

= [(n-1)/n] * [(n-2)/(n-1)] * [(n-3)/(n-2)] * ..... * [(n-k+1)/(n-k+2) ] * [1/(n-k+1)]

= 1/n