The set of 2n numbers {1,2,3,...,2n} are split randomly into two subsets of n elements. Then we sort each subset. Denote the two ordered subsets by $A={a_1 ,a_2 ,...,a_n } (a_1 <a_2 <...<a_n )$ and $B={b_1 ,b_2 ,...,b_n } (b_1 >b_2 >...>b_n )$. What is the expectation E(S) of S, where $S=\sum_{i=1}^n(|a_i-b_i|$?


If we pick $x,y$ and $j$

what is the probability that $a_i=x,b_i=y$?

without loss of generality we have $x<y$.

Then it is $\dfrac{\binom{x-1}{i-1}\binom{y-x-1}{2i-x}}{2^y}$

So our result is $2\sum\limits_{i=1}^n \sum\limits_{x<y}\dfrac{(y-x)\binom{x-1}{i-1}\binom{y-x-1}{2i-x}}{2^y}$

  • $\begingroup$ So you can calculate in cubic complexity, $\endgroup$ – Jorge Fernández Hidalgo Jan 1 '17 at 2:16
  • $\begingroup$ Can you explain a little bit more details please? I cannot follow every step. Thanks. $\endgroup$ – Della Jan 16 '17 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.