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.

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!

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  socks_are_great Oct 9 '10 at 18:13
    
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. –  socks_are_great Oct 9 '10 at 18:26
    
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. –  Paul VanKoughnett Oct 9 '10 at 18:30
    
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. –  Paul VanKoughnett Oct 9 '10 at 18:32
    
Ah, got it! Thanks again, great explanation! –  socks_are_great Oct 9 '10 at 18:38

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

share|improve this answer

Your Answer

 
discard

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