Probability that Secret Santa arrangement will result in perfect pairings for couples

Question

4 couples, 8 people total, participate in a Secret Santa gift exchange. Call the people A, B, C, D, E, F, G, H. Assume A+B are a married couple. Likewise, assume C+D, E+F, and G+H are all couples. All 8 people put their names on a piece of paper and then the people randomly draw names from the bowl. If a person draws their own name, they hold onto the paper with their name while drawing a second piece of paper, then they replace the piece of paper with their own name. This ensures that nobody draws their own name until the last person. When the last person draws, if the name in the bowl is their own, then that person switches names with the second last person to draw. This is guaranteed to be valid because the second to last person did not choose the last person. Thus, after switching the last person will have a valid name and the second to last person will have the last person's name.
a) Assume they draw in this order: A, B, C, D, E, F, G, H. What is the probability that everyone draws their own partner's name?
b) Assume they draw in a random order. What is the probability that everyone draws their own partner's name?

Answer 1

I am no expert at probability, but I think I can answer part a)

The probability for A to draw Bs name is $\frac17$ as choosing his own name would result in a redraw. This leaves 7 remaining names in the hat, so Bs chance to draw A is $\frac17$.

Similarly, the probability for C to draw D and vice versa is $\frac15$ each. E and F have a probability of drawing each other of $\frac13$ each.

In the case this all comes to be, only two names remain in the hat: G and H. As you can not draw your own name, the probability of drawing the partners name is $1$.

The total probability is therefore: $\frac17 * \frac17 * \frac15 * \frac15 * \frac13 * \frac13 * 1 * 1 = \frac1{11025} \approx 0.01\%$

Answer 2

If the order is random, then there are 8! different permutations that are equal likely. However, we can partition those 8! permutations by considering what position the first member of each couple is in the order of choosing. There are only 14 choices for the locations of the first member of each couple:
1, 2, 3, 4
1, 2, 3, 5
1, 2, 3, 6
1, 2, 3, 7
1, 2, 4, 5
1, 2, 4, 6
1, 2, 4, 7
1, 2, 5, 6
1, 2, 5, 7
1, 3, 4, 5
1, 3, 4, 6
1, 3, 4, 7
1, 3, 5, 6
1, 3, 5, 7

The solution comes down to answering these questions:

1. How many of the 8! permutations fall into each of those 14 partitions?
   and
2. What is the probability of a perfect pairing for couples within each partition?

These are pretty simple counting problems.

For example, look at the case where the first member of each couple is in positions
1, 2, 4, 5. There are 8 choices for the person in the first position, 6 choices for the second position, 4 choices for the fourth position, 2 for the fifth. Then, there are only 4 people remaining to place in positions 3, 6, 7, and 8. But, in position 3 only the partner of the person in position 1 or position 2 can go there. So, there are two choices. Then, 3 for position 6; 2 for position 7; 1 for position 8. In all, 8642232*1.

In general, there are always 864*2 ways to fill the positions of the first members of each couple. Then, for each of a remaining position, $k$, (a position for the second member of each couple), the number of choices is the number of first positions prior to $k$ minus the number of second positions prior to $k$.

The probability of a perfect pairing for couples given the positions of the first member of each couple is also a fairly easy problem. Again, use the example where the first positions are 1, 2, 4, 5. The probability the person in position 1 chooses their partner is $1/7$. The probability the second person chooses their partner given the first did is $1/6$ (they can't choose themselves and their partner was already chosen, so 6 choices remain). The probability the third person chooses their partner given the first two did is $1/6$. The probability the fourth chooses their partner given the first four did is $1/4$. Fifth person: $1/3$; sixth person: $1/3$; seventh person: $1/2$; In general, a first person from a partnership in position $k$ has $8-k+1$ names in the bowl to choose from, but one of them is their own name, so the probability they choose their partner given everyone prior has chosen their partner is $1/(8-k)$. For someone who is the second person from their partnership and in position $k$, all names in the bowl are valid choices, so the probability of choosing their partner is $1/(8-k+1)$.

The final probability is
$$\frac{1}{8!} [ \left( \text{number of ways to have first members in positions 1, 2, 3, 4} \right) *\left( P[\text{perfect couple pairing given first positions }1, 2, 3, 4] \right)+...$$ $$+ \left( \text{number of ways to have first members in positions 1, 3, 5, 7} \right) *\left( P[\text{perfect couple pairing given first positions }1, 3, 5, 7] \right) ]$$ $$\approx5.95 \times 10^{-5} \approx 1.2008 \times \frac{1}{4 \times 7!}$$

In the general case with $n$ couples and $2n$ people total, the number of ways to position the first member of each couple is given by the Catalan number $$\frac{1}{n+1} {{2n}\choose{n}} $$ With $n$ large (I've tried up to 10,000), it appears that the probability gets close to $$1.359 \times \frac{1}{n \times (2n-1)!}$$

R code:

#exact calculation by enumerating all possible choices
n=4
firstpositions=c(1:n)
done=FALSE
cnt=factorial(n)
probperfectpair=1/(factorial(2*n-1)*n)
while (!done) {
  k=n
  while (firstpositions[k]==(2*k-1)) k=k-1
  if (k==n) firstpositions[k]=firstpositions[k]+1 else {
    firstpositions[k:n]=firstpositions[k]+c(1:(n-k+1))
  }
  if (sum(firstpositions==(2*c(1:n)-1))==n) done=T
  print(firstpositions)
  secondpositions=setdiff(1:(2*n),firstpositions)
  probperfectpair=c(probperfectpair,1/(prod(2*n-firstpositions)*prod(2*n-secondpositions+1)))
  cnt1=sum(firstpositions<secondpositions[1])
  for (i in 2:(n-1)) cnt1=cnt1*(sum(firstpositions<secondpositions[i])-(i-1))
  cnt=c(cnt,cnt1)
}
sum(cnt*probperfectpair)/sum(cnt)                        #actual probability
(sum(cnt*probperfectpair)/sum(cnt))/probperfectpair[1]   #probability normalized by 
                                                         #1/(factorial(2*n-1)*n) 



#estimated "normalized" probability and standard error using simulations
estprob=function(n,nsim=1000000) {
  lf=lfactorial(2*n-1)+log(n)
  estp=rep(0,nsim)
  firstpositions=secondpositions=c(1:n)
  for (isim in 1:nsim) {
    rs=sample(2*n,2*n)
    i=1
    if ((rs[1] %% 2)==1) j=match(rs[1]+1,rs) else j=match(rs[1]-1,rs)
    rs[i]=rs[j]=0
    secondpositions[1]=j
    for (i1 in 2:n) {
      i=match(T,rs>0)
      firstpositions[i1]=i
      if ((rs[i] %% 2)==1) j=match(rs[i]+1,rs) else j=match(rs[i]-1,rs)
      rs[i]=rs[j]=0
      secondpositions[i1]=j
    }
    estp[isim]=exp(lf-sum(log(2*n-firstpositions))-sum(log(2*n-secondpositions+1)))
  }
  return(c(mean(estp),sqrt(var(estp)/nsim)))
}
estprob(4,nsim=10000)
```