4
$\begingroup$

John and Mary both pick passwords at random from a $k$ letter alphabet. There are up to $n$ letters allowed in the password. Repetitions are allowed. What is the probability that they pick the same password?

There are $\sum _{i=1}^{n}k^i$ possible passwords, and $\frac{1}{\sum _{i=1}^{n}k^i}$ probability of picking any particular password.

I'm not sure how to set the problem up from here. I know that the answer is either John or Mary picks a password and then the probability of the other picking the same password is $\frac{1}{\sum _{i=1}^{n}k^i}$, but I'm not sure why. I initially thought it would be $(\frac{1}{\sum _{i=1}^{n}k^i})^2$

2 Answers 2

4

The probability they both choose the first possible password is $\left(\frac{1}{\sum _{i=1}^{n}k^i}\right)^2$, the probability they both choose the second possible password is $\left(\frac{1}{\sum _{i=1}^{n}k^i}\right)^2$, etc.

Since these are mutually exclusive, you can add up the probabilities to find the overall probability they choose the same password. There are $\sum _{i=1}^{n}k^i$ cases with equal probability so this gives $\left(\sum _{i=1}^{n}k^i\right)\left(\frac{1}{\sum _{i=1}^{n}k^i}\right)^2= \frac{1}{\sum _{i=1}^{n}k^i}.$

  • 1
    @Robert: If all choices are independent and equally likely then yes.2012-12-24
0

Assume John picks his password first. You have computed the probability that Mary picks a specific password as $\frac1{\sum k^j}$. This is also the probability that Mary picks the specific password John happens to have picked.