# Basic probability… probability that two users share a key out of a keypool of 20?

Let's say I am distributing a bunch of encryption keys, where if two users have the same key, they can communicate. I have 20 different keys, and I am giving each user 2. Since encryption keys don't disappear when I hand them out, it can be considered 'with replacement', but I'm not giving the same user the same key twice.

I want to know what the probability that two users can communicate under these circumstances. Doing a bit of the math from what I know, each user has 20 * 19 = 380 permutations of keys. The order that they get the keys in doesn't matter, though, so it's actually 190 different combinations of keys. So, two users have 190 possible combinations of four keys, and what is the probability that one of their two keys is in common.

That reasoning is about as far as I get. How does one move forward from there? Thanks!

-
 I'm a bit confused about the question. Do you have a specific two users that you've given keys, and want to know what the probability they can communicate with each other is? Or are you asking about the probability that within a pool of N users who all have keys, some pair can communicate? Also, you say you're giving each user 4 keys in the first paragraph, but the second paragraph suggests they're getting 2. – Paul VanKoughnett Oct 9 '10 at 17:43 Wow, you're right. My apologies, I was talking with my brother while typing. I have fixed it. Two keys each among twenty keys. Probability that both people can communicate (they got at least one key in common from the 20 handed out). – socks_are_great Oct 9 '10 at 17:47

In this case, the probability is just $1$ minus the probability that they can't communicate, i. e. that they've been given $4$ different keys. The number of possible arrangements of keys among the two users is $190^2=36100$, since, as you noted, they each have $190$ possible pairs. The number of ways they can be given four different keys in total is $\frac{20\times 19\times 18\times 17}{4}=29070$. The numerator should be obvious, and we are dividing by $4$ to account for swaps in either Alice's or Bob's keys. So the probability is $1-(29070/36100)=37/190$.
without loss of generality, say Alice gets keys 1 and 2. (Renumber the keys to make this the case.) Then there are ${20 \choose 2} = (20\times 19)/2 = 190$ possible pairs of keys that Bob can get. Of these, ${18 \choose 2} = (18 \times 17)/2 = 153$ include just keys chosen from ${ 3, \ldots, 20 }$. So the probability that Alice and Bob can't communicate is $153/190$, and the probability that they can is one minus this, or $37/190$.