Number of fixed points of a random permutation

Question

Consider a random permutation of numbers $1,...,31415$. Let $A$ be the number of its fixed points (i.e. numbers which are not moved by permutation). Let $B$ be the number of non-fixed points. What is the variance of $B-A$?

I have no idea.

Answer 1

Let $N = 31415$. So in this case $N = A + B$.

$\implies {\rm Var}(B-A) = {\rm Var}(N-2A) = {\rm Var}(-2A) = 4*{\rm Var}(A)$

Therefore our primary task is to calculate ${\rm Var}(A)$. We can use identity variables.

Let $X_i$ be identity random variable which becomes $1$ when ith element is at the ith position in the permutation.

$$A = X_1 + X_2 + .... + X_n$$

$X_i$ is $1$ with probability $1/N$ and $0$ with probability $(N-1)/N$

By linearity of expectation $E[A] = \frac{1}{N} \times N = 1$

$$E[A^2] = \displaystyle \sum_{n=1}^N E[X_i^2] + 2\displaystyle \sum_{i<j}E[X_iX_j] $$

Since $X_i$ is indicator variable $E[X_i] = E[X_i^2] = 1$

If $i<j, E[X_iX_j] = (n-2)!/n!$, because in $(n-2)!$ permutations $X_i = 1$ and $X_j = 1$.

$$E[A^2] = 1 + 2* n(n-1)/2 \times (n-2)!/n! = 1 + 1 = 2$$

$${\rm var}(A) = E[A^2] - (E[A])^2 = 2 - 1 = 1.$$

$${\rm var}(B-A) = 4 \times {\rm var}(A) = 4$$