You and 25 strangers are in a room for 25 rounds of "speed dating." Each round, you are randomly paired with another person, regardless of whether you have seen them before or not. What is the probability that after 25 rounds, you have talked to only 1 person? 2 people? All 25 people?
The probability of talking to only 1 person is $\left(\frac{1}{25}\right)^{25} * {25 \choose 1} $, but after 2 people is where I get lost.
Running a simulation, I get about a $25\%$ chance of having talked to exactly 15 people. How do I get to this mathematically? I thought it might be
$$ \left(\frac{1}{25}\right)^{25} * (25 * 24 * 23 *…*15) * {25 \choose 15} ,$$
however it does not get me anywhere close to $25\%$.
Best Answer
Suppose there are $n$ other people and $r$ rounds and you want to find the probability of getting $k$ distinct matches, $1\le k\le r$. We need to partition the rounds into $k$ sets where you meet the same person in each set; the number of ways to do this is $S(r,k)$, the second-kind Stirling number. Then there are $\frac{n!}{(n-k)!}$ ways to assign people to these sets. Since there are $n^r$ possible outcomes without restrictions, the probability is $$\frac{n!S(r,k)}{(n-k)!n^r}$$ For extremal values of $k$ the Stirling number can be simplified: $S(r,1)=S(r,r)=1$ and $S(r,2)=2^{r-1}-1$. Here $n=r=25$, whereupon the probability for $k=15$ is about $20.7\%$.