# Random Matching in a Group

Recently I was asked such a question: N people joined a party. In this party, there is a present exchange game where each one prepares a present, these presents will be randomly shuffled and re-distributed. If there are two people receive presents prepared by the other, they become a pair of "lovers"(Regardless of sex, and one can be his own "lover"). What is the probability of generating at least one pair of lovers in this party? E.g. If there are two people in this party, the probability would be 1; and for three people, it would be 1-2/6 = 2/3.

-
I don't understand how you're dealing with the case of being one's own lover. You ask for the probability of generating at least one pair of lovers, and then you say this is $1$ for a party of two people. Does that mean that you count two people as a pair of lovers either if they receive each other's presents or if they both receive their own presents (and thus become their own lovers)? That would contradict how you introduced the term "a pair of lovers" further up. – joriki Feb 2 '13 at 16:31
Consider the $n$ guests as numbering the presents, then a "pair of lovers" is a cycle of length 2 in the permutation of the $n$ presents. It's probably easiest to count the permutations without 2-cycles (like derangements are permutations without 1-cycles), but there I'm stuck. – vonbrand Feb 2 '13 at 16:48
Using the word pair is a bad idea, I think you should say "set of lovers" to make it clear that the set can have size 1 or 2. – Byron Schmuland Feb 2 '13 at 17:41
Yes I was trying to say that the 1 length cycle also counts and thank Byron for clearing this up for me. – user1206899 Feb 3 '13 at 2:43

It looks like you want the probability that there is a cycle of length 1 or 2 in a random permutation on $\{1,\dots,N\}$. Considering the complementary event, we'd need to count the number of permutations without such small cycles. These values can be found here (including the party of size $N=1$), which give us the following probabilities for $1\leq N\leq 10$:

$$1, 1, {2\over 3}, {3\over 4}, {4\over 5}, {7\over 9}, {65\over 84}, {373\over 480}, {1259\over 1620}, {2447\over 3150}$$ or $$1., 1., .66667, .75000, .80000, .77778, .77381, .77708, .77716, .77683$$

These converge pretty rapidly to $1-\exp(-1.5)=.77686984$, but at the moment I'm not sure why.

Added: The number $C_1$ of one cycles is approximately Poisson(1), while the number $C_2$ of two cycles is approximately Poisson(1/2). Also, they are asymptotically independent so $C_1+C_2$ is approximately Poisson(3/2), and hence $\mathbb{P}(C_1+C_2=0)\approx \exp(-3/2)$.

Reference: Example 10.5.2 $\$ Short cycles in random permutations from the book "Poisson Approximation" by A.D. Barbour, Lars Holst, and Svante Janson. The authors show that the number of cycles less than or equal $f$, is approximately a Poisson random variable with mean $\sum_{r=1}^f 1/r$, and also give bounds on the error.

-
Not really the same: What is needed is the number of permutations without 2-cycles to subtract from the total. – vonbrand Feb 2 '13 at 17:35
I interpret the OP's comment about loving yourself to include all permutations with 1-cycles. But it is not perfectly clear, it's true. – Byron Schmuland Feb 2 '13 at 17:38
You are both very right and the mis understanding is on me. I was not very clear about the 1 cycle part.. I guess 'll just randomly choose an answer. Thanks for all the explanations – user1206899 Feb 3 '13 at 4:25

The number of ways not to have a pair of lovers is the number of permutations of the $n$ presents that don't have 2-cycles. Using the symbolic method (see for example Flajolet and Sedgewick's "Analytic Combinatorics"), this class is described by the (hacky) symbolic equation for labelled classes: $$\mathcal{C} = \mathop{MSet}(\mathop{Cyc}(\mathcal{Z}) - {\mathop{Cyc}}_{= 2}(\mathcal{Z}))$$ The respective exponential generating function is: \begin{align*} C(z) &= \exp \left(- \ln (1 - z) - \frac{z^2}{2} \right) \\ &= \frac{\exp \left(- \frac{z^2}{2} \right)}{1 - z} \end{align*} Dividing by $1 - z$ gives partial sums, so what we are looking at is: $$c_n = n! \left. \exp \right|_{\lfloor n / 2 \rfloor} ( - 1 / 2 )$$ Here $\left. \exp \right|_k (z)$ is the truncated exponential function, i.e., go only up to $k$-term in the exponential's series. The requested value is $n! - c_n \approx n! (1 - e^{-1/2})$, some 40% of parties have at least a pair of lovers.

This explains @ByronSchmuland's mystery, by the way.

-
Yes I programmed bruteforcely the first 32 value and it is about 38%. Thank vonbrand for this explanation in depth. – user1206899 Feb 3 '13 at 2:46