Suppose we are given n balls, labeled 1, · · · , n, as well as n boxes, also labeled 1, · · · , n.
We randomly draw one of the n balls and one of the n boxes, and place the ball in the box. This
procedure is repeated n times, until every ball is in a box. Each time the ball is chosen uniformly
from the remaining balls, and the box is chosen uniformly from the remaining boxes.
(a) What is the probability that the ball labeled k ends up in the box labeled k?
(b) What is the expected number of label matches?
(c) What is the variance of the number of label matches?
I think for (a), should it just be 1/n^2? But I think it is not correct, because it is without replacement. Can anyone help me with this? Thanks a lot.
Best Answer
Let $\chi_i$ be the binary random variable representing the event that ball $i$ is placed into box $i$. That is to say, $\chi_i=\begin{cases}1&\text{if ball}~i~\text{is matched with box}~i\\0&\text{otherwise}\end{cases}$
Question (1) can be rephrased as calculating $Pr(\chi_k=1)$. As alluded to in the comments we recognize that the arrangement of balls in boxes is precisely a permutation and each position in the permutation is equally likely to be any of the numbers (or equivalently each box is equally likely to have any of the balls). For a more formal explanation, one can approach this with multiplication principle noting that there are $(n-1)!$ ways to arrange balls into boxes satisfying that box $k$ gets ball $k$. As a result, the probability we are looking for is $Pr(\chi_k=1)=\frac{1}{n}$.
Letting $X$ represent the total number of boxes with their correct balls (i.e. the number of fixed points in the permutation) we recognize that $X=\chi_1+\chi_2+\dots+\chi_n$
Question (2) asks us to find $E[X]$ which using the above and linearity of expectation gives us $E[X]=E[\chi_1+\chi_2+\dots+\chi_n]=E[\chi_1]+E[\chi_2]+\dots+E[\chi_n]=n\cdot\frac{1}{n}=1$
Question (3) asks us to find $Var[X]$ which we have the option to expand as $E[X^2]-E[X]^2$. We already found $E[X]=1$ earlier, so all that remains apart from arithmetic is to calculate $E[X^2]$. Using that $X=\chi_1+\chi_2+\dots+\chi_n$ again we find:
$$\begin{array}{rl}X^2 &= (\chi_1+\chi_2+\dots+\chi_n)(\chi_1+\chi_2+\dots+\chi_n)\\ &= \chi_1\chi_1+\chi_1\chi_2+\chi_1\chi_3+\dots+\chi_n\chi_{n-1}+\chi_n\chi_n\\ &=\sum\limits_{k=1}^n\chi_k^2 + 2\sum\limits_{k=1}^n\sum\limits_{j=k+1}^n\chi_k\chi_j\end{array}$$
We have then $E[X^2]=E\left[\sum\limits_{k=1}^n\chi_k^2 + 2\sum\limits_{k=1}^n\sum\limits_{j=k+1}^n\chi_k\chi_j\right]$ which simplifies quite nicely due to symmetry and properties of binomial random variables.
From here there is one small probability calculation left and then a bit of arithmetic to finish.
Continued: