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$

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Effectively I want to pick a pair of passwords from $n$ and figure out what's the probability that they're the same. There are $n^2$ possible pairs of passwords, and $n$ ways to choose a pair of identical passwords, so I get $\frac{n}{n^2}=\frac{1}{n}$. That reasoning makes sense? $\endgroup$ – Robert S. Barnes Dec 24 '12 at 11:17
  • 1
    $\begingroup$ @Robert: If all choices are independent and equally likely then yes. $\endgroup$ – Henry Dec 24 '12 at 11:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.