# Probability of Picking the Same Password from a $k$ letter alphabet

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$

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