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 * 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
    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.2010-10-09
  • 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
    Thanks for the solid answer! I'm not sure I totally understand the denominator in the above equation (dividing by 4 to account for swaps in either's keys). What do you mean by swaps?2010-10-09
  • 0
    Also, would it really be 20*19*18*17? Since after Alice gets her two keys (20*19), those keys are replaced into the pool of 20 keys so Bob can pick the same two, so his permutations also entail (20*19). I may be mixing myself up, though.2010-10-09
  • 0
    Gah, I rewrote that sentence a couple times and couldn't think of a concise and clear way to put it. "Swaps" means this: that you're assigning a 4-tuple (A1,A2,B1,B2) of keys, and we're considering that to be equal to (A2,A1,B1,B2) and (A1,A2,B2,B1) but not, say, (A1,B1,A2,B2). You divide by two to account for ordering of Alice's keys and again to account for ordering of Bob's keys.2010-10-09
  • 0
    As for your second comment, I believe you are confused. 20*19*20*19 is the number of possible key assignments, which I used as my denominator. 20*19*18*17 is the number of key assignments where the two can't communicate, and I used it (divided by 4) as my numerator. That fraction is the probability that they can't communicate, and 1 minus it is the probability they can.2010-10-09
  • 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$.