December 16, 2022
Every Christmas, Gary’s family has a gift exchange. And every year, there is a big fight over how much folks should spend on the gifts. This year, they decided to pair up. So if Virginia gives Justin a gift, then Justin gives Virginia a gift. This way, while there will still be arguments, only two people will be involved in each argument.
There are 20 people in the gift exchange. In the first round, everyone writes down the name of a random person (other than themselves) and the names go in a hat. Then if two people randomly pick each other’s names out of that hat, they will exchange gifts, and they no longer participate in the drawing. The remaining family members go on to round two. Again, they write down the name of anyone left, and again, any two people who pick each other exchange gifts.
This continues until everyone is paired up. And yes, if exactly two people remain, they still go through the process of selecting each other, even though they know who their partner will be.
On average, what is the expected number of rounds until everyone is paired up?
Without Replacement: 22.1 rounds
With Replacement: 26.7 rounds
Explanation:
We are using Monte-Carlo simulation via MATLAB with one million simulations. There are two scenarios: without replacment and with replacement. For without replacement, below is the code for one trial:
function rounds = getAvgRoundsNoReplacement(N) % Given N potential pairs of 2N people, use the Monte-Carlo method to % determine the average number of rounds before everyone is paired off. % Assume NO replacement. rounds = 0; pairs = N; while pairs > 0 rounds = rounds + 1; totalPeople = 2*pairs; % We first have everyone write down their preferred gift target giftMatrix = NaN(totalPeople, totalPeople - 1); % They can't write down their own names for k = 1:totalPeople row = 1:totalPeople; row = row(row ~= k); giftMatrix(k, :) = row; end % Have each person write down their names and add to the pool recPool = NaN(totalPeople, 1); for k = 1:totalPeople idx = randi(totalPeople - 1); recPool(k) = giftMatrix(k, idx); end % Next we do the draw; % Assume NO replacement giftList = NaN(totalPeople, 1); giftIdx = randperm(totalPeople); for k = 1:totalPeople giftList(k) = recPool(giftIdx(k)); end % Finally we see if pairs can be matched for k = 1:totalPeople if giftList(k) == k continue; % No self-gifting! end lucky = giftList(k); if giftList(k) ~= -1 && giftList(lucky) == k % found a match! pairs = pairs - 1; % Ensuring no double counting giftList(k) = -1; giftList(lucky) = -1; end end end end
With replacement, we simply modify the drawing simulation with:
% Next we do the draw; % Assume with replacement giftList = NaN(totalPeople, 1); for k = 1:totalPeople giftIdx = randi(totalPeople); giftList(k) = recPool(giftIdx); end
So for the above, we let each person pick something from the pool and two people can pick the same slip of paper.
We get for the average rounds:
Below are their overlaid distributions
It is interesting to see that for both cases, they have similar distributions, but the without replacement case has a lower mean than its replacement counterpart. An intuitive explanation for this is that with replacement, it is more likely for multiple people to draw the same person. However, that lucky person can only form a gift-giving pair with only one other person, thereby prolonging the process.
Below are the individual distributions:
Therefore, if you want the process to finish faster, go with the no replacements rule.