Probability of Recurring Pairings in Random Groupings

[courtrigrad]

Lets say you have 16 people. You want to make 8 groups. You choose the groups randomly. There are 2 people per group. What is the probability that 1 of the 8 groups is the same for a certain number of trials? For example, if person A is with person B this trial, what is the probability that person A will be with person B in the next trial (or many more trials after that)? I know the probability of all the groups being the same is $$\frac{1}{120}$$.

ThanksPS: I posted this question on the Calculus forums, but thought it more suitable to be here

 

[Joffe]

'A' could be with any of the other 15 letters, so the chances of it being with B are 1/15, for that to happen n times is (1/15)^n

EDIT: And for all the groups being the same it is not 1/120, it is $$\frac{2^8.8!}{16!} = 1/2027025$$

 

[D H]

Suppose the groupings in one trial are labeled (AB, CD, EF, GH, IJ, KL, MN, OP). I gather you are asking what the probability is of getting anyone (or more) of the groups the same on another trial, not just one particular group (say AB). As Joffe answered, the probability of getting AB paired again in some other trial is 1/15. The probability of getting any group paired once again is much higher: 836353/2027025.

 

[courtrigrad]

how did you get that DH? That is the correct answer.

Thanks

 

[courtrigrad]

any ideas?

 

[D H]

how did you get that DH? That is the correct answer.
Thanks

Embarrasingly, I obtained the solution by brute force using Matlab.

 

[uart]

Just reviving this slightly oldish thread to ask if anyone knows if this problem can be done by means other than brute force.

I was also wondering if perhaps this problem was given in a computer science type context rather than a theoretical probability context. Courtrigrad (if you're still around) can you shed any light on the origins of this problem.

It certainly is an interesting little computer programming problem to try and enumerate all the possible grouping combinations and count those that contain a common pairing. I can't even see an easy way to do it (in general) without resorting to recusion, which is generally considered a bit nasty unless absolutely necessary. DH (if you're still around) can you give any more details on the code for your brute force attack.

BTW. The thing that makes this problem hard (for other than brute force enumeration) is that the event that a given pairing is common is obviously not independent of the events of other pairings occurring. Neither are those event multually exclusive, so simple addition of probabilies or multiplication of complementary probabilites is out.

One "theoretical probability" approach that I did find to give an interesting result to this problem was to try approximating the solution by considering the event that a particular pairing does NOT re-occur to be approximately independent of other pairings in that group not recurring. This should be approx true for large groups.

Using the above gives the result that the probability that at least one pairing recurrs when you regroup is $$P \simeq 1 - ( (2n-2)/(2n-1) )^n$$, where "n" is the number of pairs in the group.

So for example in the given case of 8 pairs then $$P \simeq 1 - (14/15)^8$$ which gives an approx answer of about 42% (which compares reasonably well with the exact answer given earlier by DH).

The thing that is particularly interesting about this method however is that it's easy to show that it converges to a limiting value of $$1 - 1/\sqrt{e}$$ (about 39.4%) for large n. I thought that was kind of neat.