Lesson 8

It turns out that the linearity of expectation provides a very simple answer to this question. To do this, we use a standard trick—representing a random variable as a sum of indicators. Specifically, let \(\chi_{i}=[\pi(i)=i]\) — an indicator of the event “point \(i\) is a fixed point”. Then \[\alpha=\chi_{1}+\dotsb+\chi_{n}  .\] The random variables \(\chi_{1}, \dotsc, \chi_{n}\) are not independent: for example, if \(\chi_{1}=\chi_{2}=\dotsb=\chi_{n-1}=1\), then also \(\chi_{n}=1\). But their independence is not needed, as we have already discussed. It is easy to see that \[\operatorname{E}[\chi_{i}]=\Pr[\pi(i)=i]=\frac{1}{n}  .\] Thus, \(\operatorname{E}[\alpha]=n \cdot \frac{1}{n} = 1\).