I was studying permutation groups and I founs this question-
Let $S_n$ be the group of all permutations of the set $X=\{1,2,\dots,n\}$. Given a permutation $\sigma\in S_n$, let $f(\sigma)$ denote the number of fixed points of $\sigma$.
a. Show that the average number of fixed points is $1$, i.e.,
$$\frac 1{|S_n|}\sum_{\sigma\in S_n}f(\sigma)=1$$b. Find the average value of $f(\sigma)^2$.
All that comes to my mind is to use Inclusion Exclusion Principle to calculate the number of combinations for a given value of $f(\sigma)$. That is, explicitly calculate the number of permutations of $X$ with exactly $r$ fixed points, denoted by $S_n(r)$. But, that is not a very easy task since we are doing it for a general $n$ which means $S_n(r)$ will be in the form of a summation, all of which needs to be summed again over all $r$. Also, this approach is not quite elegant. It becomes a real headache however in b since there you need to take a square as well. Also, we are never really using any property of permutation groups while solving this problem.
Is there any other approach that can make life easier?
While it is suggested in the comments and in an answer to use expectations of random variables, I don't think that is what the question asks of me considering the fact that the course in which I got the problem (it's a group theory course by the way) is far away from that. Is there any other ways to go about it?
Best Answer
As in many cases where a random variable is equal to the number of occurrences of several events, a fruitful technique is to write that random variable as a sum of indicator random variables.
Let $X_i$ be a random variable which is $1$ if $\sigma(i)=i$, and $0$ otherwise. Letting $X=X_1+\dots+X_n$, this means that $f(\sigma)=X$. It follows that $$ E[f(\sigma)]=E[X]=E[X_1]+\dots+E[X_n]=nE[X_1], $$ $$ E[f(\sigma)^2]=E[(X_1+\dots+X_n)^2]\stackrel{*}=nE[X_1^2]+n(n-1)E[X_1X_2] $$ In $\stackrel{*}=$, I expanded out $(X_1+\dots+X_n)^2$, distributed the $E[]$, and then collected identically distributed terms.
All that remains is to compute $E[X_1]$, $E[X_1^2]$, and $E[X_1X_2]$. These random variables only take the values $0$ and $1$, so computing their expectations involves computing a certain probability. I leave the rest to you.