Given a random permutation of numbers 1,...,n, what is the expected number of fixed points?

Given a random permutation of numbers 1,...,n, what is the expected number of fixed points?

Approach: Use indicator variables and linearity of expectation.

1. Let I_i be indicator that i is fixed point. E[I_i]=1/n. Sum over i=1..n gives 1.

Follow-up: What is the probability of no fixed points?

Key concepts: linearity of expectation, indicator variables, permutations.