0
$\begingroup$

The distance between a permutation $\pi$ of [n] and the sorted order of [n] is defined as $$\sum_{i=1}^n |\pi(i)−i|.$$

Assuming uniform probability distribution over all the permutations of [n], given that for two specific distinct numbers j, k in [n], π(j) = j, π(k) = k, find the expected distance between π and the sorted order of [n].

I do not know the answer. I tried to solve using conventional by calculating maximum possible distance and summing over 1 to max distance multiplied by It's probability.

But, this happened to be very difficult as finding probability of particular distance value is not easy.

I can't think of any solution using indicator random variable which is generally used to solve this questions .

How to solve this?

$\endgroup$

1 Answer 1

0
$\begingroup$

If $\pi(j)=j,\pi(k)=k$ then the rest can be treated as a permutation of $n-2$ elements. Now for every $i \neq j,k$ and a valid $s$, $P(\pi(i) - i = s) = (n-3)!/(n-2)! = (n-2)^{-1}$ . Hence $$ E(|\pi(i) - i|) = \sum_{s=1,s \neq j,k}^n \frac{|s-i|}{(n-2)} $$ Thus summing over $i$ gives $$ E(\sum_{i=1, i\neq j,k}^n |\pi(i) - i|) = \sum_{i}\sum_{s=1,s \neq j,k}^n \frac{|s-i|}{(n-2)} $$

A closed formed expression should be derivable from this but its a nasty calculation!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .