There are two groups $G_1, G_2$ of $n\in\mathbb N$ persons each. Each member of $G_1$ independently gives a gift to a random member of $G_2$. What is the expected number $\mathbb E[L_n]$ of members of $G_2$ that do not receive a gift?
I need to prove that $\frac{n-1}{e}\leqslant \mathbb E[L_n] \leqslant \frac n e\qquad(1)$.
This solution looks like the solution to the secretary problem. Even though the context is different. How can I prove $(1)$. I was thinking about using a combinatorial approach but that does not seem too elegant.
Is $L_{n,m}$ a supermartingale? If we consider the expected number of members of $G_2$ after the $m$-th gift was given it should decrease and depend on the number of persons that did not have a gift.
By linearity of expectation, the probability the first person in $G_2$ doesn't receive a gift will be $(1-\frac{1}{n})^n$ since the first person of $G_1$, second person of $G_1$, third, etc... must all give their gift to someone different than the first person in $G_2$. Similarly for all other people in $G_2$.
The expected number is then the sum of these and is going to be:
$$n\left(1-\frac{1}{n}\right)^n$$
One can show that the inequality described holds, following the limit definition for $e$.
Actually caring about the probability of a specific number of people receiving or not receiving gifts is a trap and is completely unnecessary for the problem.