Mean number of replacements in a uniform random permutation

Question

I'm having a trouble understanding the logic behind the derivation of probability for a certain event. I'll state my question and explain the part which's bothering me:

"In a permutation of an ordered numbers set $(1,2,3,....,n) \:, n>=2$, each event in which two numbers $i$ and $j$, $i\neq j$, swap places ($i\longleftrightarrow j$) is called a replacement. For example, in the permutation $(7,5,6,3,2,4,1)$ of the ordered numbers set $(1,2,3,4,5,6,7)$, there are two replacements: $1\longleftrightarrow 7$ and $2\longleftrightarrow 5$.

What is the expectation of the number of replacements in a uniform and randomly given permutation of the ordered numbers set $(1,2,3,4,5,6,7)$?

Ps.: By uniform, it means that all the permutations have the same probabilities."

My solution: There are $\frac {42}{2}=21$ couples of numbers which can participate in a replacement, so I defined the following indicator:

$$\forall i\neq j, \:\:\:\:\:\mathcal{X}_{i,j}=\begin{cases} 1,& i,j \:are \:swapped\:\\ 0,& otherwise\end{cases}$$

Hence, the number of replacements in a given permutation is:

$$X=\sum\limits_{1\le i<j\le 7} \mathcal{X}_{i,j}$$

But I'm having a trouble calculating the probability that two numbers $i,\: j$ are a replacement. My first instinct tells me it's $\frac {2}{42}=\frac {1}{21}$, for out of 42 couples it can be picked twice. However, that means that $E[\mathcal{X}]=1$ which is wrong... the answer in the book is $E[\mathcal{X}]=\frac{1}{2}$ but I cannot understand why. Thanks in advance for any help!

Answer 1

The probability that $X_{i,j}=1$ is by symmetry exactly the same as the one that $X_{i,j}=0$. To see why, pick a permutation $\pi$ where $(i,j)$ is a replacement. Then $\pi\circ[i,j]$ is another permutation, where $(i,j)$ is not; you therefore have exactly the same number of permutations where $(i,j)$ is a replacement than of permutations where it is not, since $$ \phi\colon \pi \mapsto \pi\circ[i,j] $$ is a bijection. This implies $\mathbb{E} X_{i,j} = \mathbb{P}\{X_{i,j}=1\} = \mathbb{P}\{X_{i,j}=0\}.$

Now, the number of permutations $\pi$ where $\{i,j\} = \{\pi(i),\pi(j)\}$ is $2\cdot 5!$: indeed, this is leaving only $5$ elements out of $7$ (the remaining ones to permute) to choose, times the two choices (swapping $i$ and $j$ or not), leading to $2\cdot 5!$ permutations. In particular, such a permutation $\pi$ is picked with probability $\frac{2\cdot 5!}{7!} = \frac{1}{21}$.

Thus, $\mathbb{E} X_{i,j} = \frac{1}{2}\frac{1}{21}.$ But you have $\binom{7}{2}=2$ pairs $(i,j)$, so overall the sum is $$\mathbb{E} X = 21\cdot \frac{1}{2}\cdot\frac{1}{21} = \frac{1}{2}.$$

Answer 2

If I interpret this problem correctly we are counting the expected number of two-cycles in a random permutation. This gives the species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{V}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, v) = \exp\left(z + v\frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \frac{z^5}{5} + \cdots\right)$$ which is $$G(z, v) = \exp\left((v-1)\frac{z^2}{2} + \log\frac{1}{1-z}\right) = \frac{1}{1-z}\exp\left((v-1)\frac{z^2}{2}\right).$$

As this is an EGF to get the OGF of the average number of replacements we must differentiate with respect to $v$, computing $$\left.\frac{\partial}{\partial v} G(z, v)\right|_{v=1}.$$

This is $$\left.\frac{1}{1-z}\exp\left((v-1)\frac{z^2}{2}\right) \frac{z^2}{2}\right|_{v=1} = \frac{1}{1-z} \frac{z^2}{2}.$$

This gives for the average number of replacements $$[z^n] \frac{1}{1-z} \frac{z^2}{2} = \frac{1}{2} [z^{n-2}] \frac{1}{1-z} = \frac{1}{2}$$ when $n\ge 2$ and zero when $n=1.$

Corollary. We see that the expected number of $m$-cycles is $1/m$ and hence the expected total number of cycles is $$\sum_{m=1}^n \frac{1}{m} = H_n\sim\log n.$$