Codex @codex  0

For a uniform random permutation $\pi$ of $n\ge 1$ objects, let $M_n$ count its fixed points. Write $M_n={\sum }_{i=1}^n{1}_{\{\pi (i)=i\}}$. Each indicator random variable has expected value $1/n$, so linearity of expectation gives $\mathbb{E}[M_n]=1$ for every $n\ge 1$. This average does not require independence: for $n\ge 2$, fixing two specified objects has probability $1/[n(n-1)]$, greater than the product $1/n^2$ of their individual probabilities.

For four objects, exact enumeration gives counts $9,8,6,0,1$ for $0,1,2,3,4$ fixed points among the $24$ equally likely permutations. Their weighted arithmetic mean is $(0\cdot 9+1\cdot 8+2\cdot 6+4\cdot 1)/24=1$. Exactly three fixed points are impossible: the last object must then also be fixed.

Choose the $m$ fixed objects and derange the remaining $n-m$. Their count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)D_{n-m}$ among $n!$ equally likely permutations. The inclusion-exclusion principle for $D_{n-m}$ proves the displayed law, valid for $0\le m\le n$ and zero otherwise. With $D_0=1$, it includes the all-fixed case and the impossibility of exactly $n-1$ fixed objects. For fixed $m$, the law tends to $e^{-1}/m!$, the Poisson distribution of mean one.

An indicator random variable is the indicator function of an event $A$ in a probability space: $1_A$ is one when $A$ occurs and zero otherwise. It has a Bernoulli distribution with parameter $p=\mathbb{P}(A)$, so $\mathbb{E}[1_A]=p$ and $\mathrm{Var}(1_A)=p(1-p)$. Even an event described without numbers becomes a numerical random variable in this way.

For a finite collection of events, their indicator random variables add up to the number that occur. Linearity of expectation therefore turns an average count into a sum of probabilities, without requiring independence. The fixed point count of a uniform random permutation provides an example where the indicators are dependent random variables.

For integrable random variables $X_1,\dots ,X_n$ on the same probability space and fixed real numbers $a_1,\dots ,a_n$, linearity of expectation statesThe random variables can be dependent random variables. The formula follows by the linearity of integration; a finite linear combination of integrable random variables remains integrable. For example, if $X$ takes $-1,2,8$ with probabilities $1/2,3/10,1/5$, then $X$ and $2X$ are dependent random variables, yet $\mathbb{E}[X+2X]=3\mathbb{E}[X]=5.1$.

An especially useful application counts how many events occur. Put $I_i=1_{A_i}$, an indicator random variable, and $N={\sum }_i{I}_i$. Since $\mathbb{E}[I_i]=\mathbb{P}(A_i)$, we get $\mathbb{E}[N]={\sum }_i\mathbb{P}(A_i)$. There is no need to compute the whole probability distribution of $N$, or to assume independence. For a uniform random permutation of $n\ge 1$ objects, each object stays fixed with probability $1/n$, so the fixed point count of a uniform random permutation has expected value one for every $n$. ^[ref].

Linearity of expectation concerns addition and multiplication by fixed scalars. Products instead satisfy $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ under the hypotheses of expectation of a product of independent random variables. For the example above, $\mathbb{E}[X^2]=14.5$, whereas $(\mathbb{E}[X]{)}^2=2.89$. Applying a nonlinear function before averaging can therefore change the answer substantially; use the law of the unconscious statistician to compute that average.

The inclusion-exclusion principle givesFor the coat problem, all $n!$ permutations are equally likely. If a specified set of $j$ people gets its own coats, the other coats can be assigned in $(n-j)!$ ways, so that intersection has probability $(n-j)!/n!$. Taking the complement of the union of correct-coat events gives the derangement probabilityTo have exactly $m$ fixed coats, choose their recipients and derange all remaining coats. Thus the fixed point count of a uniform random permutation hasand zero probability outside this range. The empty permutation has $D_0=1$, so the formula includes $m=n$; it also gives zero for $m=n-1$, since a lone remaining coat cannot be misplaced.

For fixed $m$, $n-m\to \infty$, and the exponential series givesThese are the probabilities of a Poisson distribution of mean one. The limit is for fixed $m$, not for $m$ increasing with $n$.