2
$\begingroup$

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 \cdot 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!

  • 0
    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).2010-10-09

2 Answers 2

2

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

  • 0
    Ah, got it! Thanks again, great explanation!2010-10-09
4

A solution which doesn't involve quite so large numbers:

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