Expected number of fixed points of permutation equals one
Suppose is a natural number. Consider the uniform distribution on the symmetric group of degree , i.e., the symmetric group on a set of size . The expected number of fixed points for a permutation picked according to the uniform probability distribution equals .
We note that the number of permutations that fix a particular element in the set is , hence the probability that is fixed is . By linearity of expectation, the expected number of fixed points is the sum, for each point, of the probability that it is fixed. This sum is .
Note that expectation is linear even when the random variables in question are not independent.