Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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? –  Robert S. Barnes Dec 24 '12 at 11:17
1  
@Robert: If all choices are independent and equally likely then yes. –  Henry Dec 24 '12 at 11:20
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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