put n balls into n boxes 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.
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&amp;\text{if ball}~i~\text{is matched with box}~i\\0&amp;\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 &amp;= (\chi_1+\chi_2+\dots+\chi_n)(\chi_1+\chi_2+\dots+\chi_n)\\ &amp;= \chi_1\chi_1+\chi_1\chi_2+\chi_1\chi_3+\dots+\chi_n\chi_{n-1}+\chi_n\chi_n\\
&amp;=\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.


   $E[X^2]=nE[\chi_1] + 2\binom{n}{2}E[\chi_1\chi_2]$


From here there is one small probability calculation left and then a bit of arithmetic to finish.


   You need to calculate $E[\chi_1\chi_2]$.  Remember that the product of two binary random variables is again a binary random variable and the expected value of a binary random variable is just the probability that the random variable takes the value 1.  That is to say $\chi_1\chi_2=\begin{cases}1&amp;\text{if ball}~1~\text{is in box}~1~\text{and ball}~2~\text{is in box}~2\\0&amp;\text{otherwise}\end{cases}$ and $E[\chi_1\chi_2]=Pr(\chi_1\chi_2=1)$




Continued:


   $Pr(\chi_1\chi_2=1)=Pr(\chi_1=1)\cdot Pr(\chi_2=1\mid \chi_1=1)=\frac{1}{n}\cdot\frac{1}{n-1}$ (note, these random variables are dependent on one another).  We get then $$Var[X]=E[X^2]-E[X]^2=n\cdot\frac{1}{n}+2\binom{n}{2}\frac{1}{n(n-1)}-1=1+1-1=1$$
Update (The original answer was wrong, since I had not read the problem carefully. I then overlooked that boxes, once chosen, are taken out of the game as well.)

The described protocol chooses a permutation $\pi\in{\cal S}_n$ uniformly at random. The probability that for a given $k\in[n]$ we have $\pi(k)=k$ then is ${1\over n}$, by symmetry. The linearity of expectation then enforces that the expected number of correct matches is $n\cdot{1\over n}=1$. – Only the computation of the variance necessitates more work.