Can You Make It To 2023?

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?

`R`

Functions to run the Sampling Scheme DescribedThis function iteratively selects \(n\) people (excluding self), and people could be selected more than once.

This function takes the bowl of names from `sample.everyone.else`

, draws \(n\) names, checks whether two people got each other, and returns the number of matches.

This table demonstrates a small, four-person example of `party.sampler`

where each person is represented by a number (`1`

through `4`

).

`party`

is the the person someone else drew, `party[party] == 1:4`

checks whether the person someone got also got them while `party != 1:4`

checks that they didn’t get themselves, and `matches`

checks whether both conditions are true.

In short, person 2 and 4 got each other (and should match), person 1 got themselves and should not match, and person 3 did not get matched with person 4. There should be two people removed from this round.

index | \(\texttt{party}\) | \(\texttt{party[party] == 1:4}\) | \(\texttt{party != 1:4}\) | \(\texttt{matches}\) |
---|---|---|---|---|

1 | 1 | TRUE | FALSE | FALSE |

2 | 4 | TRUE | TRUE | TRUE |

3 | 4 | FALSE | TRUE | FALSE |

4 | 2 | TRUE | TRUE | TRUE |

This function calls the `party.sampler`

function until everyone has been selected. It is thus the *main* function that is called in the simulation.

```
party.time = function(guests = 20){
i = 0
while(guests > 0){
matches = party.sampler(guests)
guests = guests - matches
i = i + 1
}
return(i)
}
```

`replicate`

repeats the `party.time`

function one million times.

```
set.seed(538)
M = 10^6
counts = replicate(n = M, expr = party.time())
sim.results = counts |> table() |> as.data.frame()
names(sim.results) = c("turns", "freq")
sim.results = sim.results |> mutate(turns = as.integer(as.character(turns)))
# save(sim.results, file = "simresults.rda")
```

Below, we see the distribution of turns until everyone has matched after a simulation with one million replications. The expected value is estimated to be \(24.02582\).