For two permutations $\pi, \phi \in Sn$ on $n$ elements $[n]={1,2,\ldots,n}$, let us define their distance as $d(\pi,\phi) = \sum{i=1}^n |\pi(i) - \phi(i)|$.
Assume you have to predict a permutation $\pi$ which is picked uniformly from $S_n$. How far do you expect to be from $\pi$?
cschaffner
commented
9 years ago
For two permutations $\pi, \phi \in Sn$ on $n$ elements $[n]={1,2,\ldots,n}$, let us define their distance as $d(\pi,\phi) = \sum{i=1}^n |\pi(i) - \phi(i)|$.
Assume you have to predict a permutation $\pi$ which is picked uniformly from $S_n$. How far do you expect to be from $\pi$?
Answer: Compute $\E_{\pi \leftarrow Sn}[ \sum{i=1}^n |\pi(i) - i| ]$