Fixed points of permutation

Recall the example of derangements (Deragements). Let us pick a random permutation $f$ on $[n]$. A fixed point is a value $i \in [n]$ for which $f(i) = i$. (so this is the student who receives their own homework when the homework is returned at random order) How many students do we expect to receive their own homework? (or how many fixed points do we expect?)

More formally, we are working with the sample space of all $n!$ permutations, i.e., $\Omega = \{f: [n] \rightarrow [n]\}$ and uniform distribution.

Exercise 113

Prove: The probability that $i$ is a fixed point is $1/n$.

Let $X$ be the random variable denoting the number of students who receive their own homework, i.e., the number of fixed points. Therefore, we can write $X$ as a sum of indicators variables $X_i$ indicating whether $i$ is a fixed point. We have $X = \sum_{i \in [n]} X_i$. This implies that ${\mathbb E}[X] = \sum_i {\mathbb E}[X_i] = n\cdot (1/n) = 1$.

This implies that, regardless of how large the class is, the expected number of students receiving their own homework is one!