Upper bound of the expectation of sum of the absolute value pairs We have two arrays $A,B$ of length $n$. All values are i.i.d drawn from same distribution on $[0,1]$. If we sort $A,B$ in non-decreasing order and let $A_{(i)},B_{(i)}$ denote the i-th value in the sorted array. Then we have $S=\sum_{i=1}^n|A_{(i)}-B_{(i)}|$. What is the upper bound of $\mathbb{E}[S]$?
I believe it must be the uniform distribution in order to get the upper bound, but I can't prove that. 
I've searched order statistics and I think that may give me some upper bound, but the expression is too complex and I can't complete the derivation.
 A: It is, indeed, true (and trivial) that the worst distribution is concentrated at the endpoints. I'm just failing to see why it is obvious that the worst case is symmetric.
Indeed, let us consider all discrete distributions $P(x=x_j)=p_j$ with $0\le x_1< x_2\dots<x_m\le 1$. Note that $P(A_{(i)}=x_k,B_{(i)}=x_{\ell})$ depends in some complicated way on $p_j$ but does not depend on $x_j$ at all. Thus $E|A_{(i)}-B_{(i)}|$ is a linear function on our simplex, so it attains its maximal value at one of the vertices. However, all vertices are precisely of the type $P(x=0)=p, P(x=1)=1-p$. 
One has to argue here a bit carefully because formally we do not allow $x_j$ to glue together, but it is easy to see that having all of them near the endpoints gives almost the same expectation as the glued distribution because only the jumps of length about $1$ are relevant.
So, the $O(\sqrt n)$ bound becomes obvious (the expectation of the absolute value of the difference of two sums of $n$ iid Bernoulli variables is not hard to estimate). I still want to see why $p=\frac 12$ is the worst case scenario without any computation requiring pen and paper. 
@MarkL.Stone It's nothing fancy, really. First, you note that for 2 standard Gaussians $X,Y$, we have
$$
E|X-Y|=\frac 1{2\pi}\iint_{(-\infty,\infty)^2} |x-y|e^{-\frac{x^2+y^2}{2}}dx\,dy
\\
\overset{(z=x+y,\ t=x-y)}=
\frac 1{2\pi}\iint_{(-\infty,\infty)^2} |t|e^{-\frac{z^2+t^2}{4}}d\frac z2\,dt
\\
=\frac 1{2\sqrt\pi}\int_{(-\infty,\infty)} |t|e^{-\frac{t^2}{4}}\,dt=\frac 2{\sqrt\pi}\,.
$$
Next you recall that the density of $A_{(i)}$ is proportional to $x^{i-1}(1-x)^{n-i}$. Ignoring $-1$, which matters only for small $i$, we see that it has maximum at $i/n$ with the second derivative of the logarithm being minus
$$
i(i/n)^{-2}+(n-i)((n-i)/n)^{-2}=\frac{n^3}{i(n-i)}\,.
$$
Approximating by the appropriate Gaussian, we get
$$
E|A_{(i)}-B_{(i)}|\approx \frac 2{\sqrt\pi}n^{-3/2}\sqrt{i(n-i)}\,,
$$
so the expectation of the sum is about
$$
\frac 2{\sqrt\pi}n^{-3/2}\sum_{i=1}^n\sqrt{i(n-i)}\approx
\frac 2{\sqrt\pi}n^{-3/2}\int_0^n\sqrt{x(n-x)}\,dx=
\frac 2{\sqrt\pi}n^{-3/2}\frac{\pi n^2}8=\frac{\sqrt\pi}{4}\sqrt n
$$
(the integral is just the area of the upper half-disk of radius $n/2$ centered at $(n/2,0)$).
Of course, you need to do some error analysis in these computations to make the argument complete, but it is fairly routine.
A: To finish fedja's argument (that is not a perfect way, probably, but respectively short and does not require serious computations.)
Assume that the distribution of each $A_i$ and $B_i$ is 0 with probability $1-p=q$ and 1 with probability $p$. Denote by $\lambda_k=\binom{n}kp^k(1-p)^{n-k}$ the probability that $\sum_j A_j=k$.
$$\mathbb{E} [S]=\sum_i P[A_{(i)}\ne B_{(i)}]=2\sum_iP[A_{(i)}=0,B_{(i)}=1]=\\2\sum_iP\left[\sum_j A_j\leqslant i-1\right]P\left[\sum_j B_j\geqslant i\right]=\\ 2\sum_i (\lambda_0+\lambda_1+\dots+\lambda_{i-1})(\lambda_i+\lambda_{i+1}+\dots+\lambda_n)=2\sum_{i<j} (j-i)\lambda_i\lambda_j=\\ \sum_{i,j}|i-j|\lambda_i\lambda_j=\Phi((p\cdot t+q)^n(p\cdot t^{-1}+q)^n).$$ Here $\Phi$ denotes a linear functional on the space of real Laurent polynomials, satisfying $\Phi(t^k)=|k|$ for all integer $k$. On the subspace of Laurent polynomials $h(t)$ satisfying $h(t)=h(t^{-1})$ we have $\Phi(h)=\frac2{\pi}\int_0^\infty -(h(e^{i\tau}))'\frac{d\tau}\tau$ (it suffices to check this for $h(t)=(t^k+t^{-k})/2$, $k>0$, and the identity reduces to $\int_0^\infty \frac{\sin k\tau}{\tau}d\tau=\frac{\pi}2$.) In our situation $h(e^{i\tau})=(p^2+q^2+2pq\cos \tau)^n$ and integrating by parts we get $$\Phi(h)=\frac2{\pi}\int_0^\infty -(h(e^{i\tau}))'\frac{d\tau}\tau=
\frac2{\pi}\int_0^\infty (1-h(e^{i\tau}))'\frac{d\tau}\tau=\frac2{\pi}\int_0^\infty (1-h(e^{i\tau}))\frac{d\tau}\tau,$$
and this expression $1-(p^2+q^2+2pq\cos \tau)^n=1-(1-2pq(1-\cos \tau))^n$ is obviously maximal for $p=q=1/2$ pointwise.
A: $\newcommand{\al}{\alpha}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\Si}{\Sigma}
\newcommand{\thh}{\theta}
\newcommand{\om}{\omega}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\E}{\operatorname{\mathsf E}} 
\renewcommand{\P}{\operatorname{\mathsf P}}
\newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} 
\newcommand{\tf}{\widetilde{f}}$ 
This answer is a modification of the excellent answer by Fedor Petrov. This modification possibly requires less effort to follow, since it uses a known result. (I wonder why I did not decide to pursue this path earlier. :-) ) 
As noted in the beginning of previous answer (based on very different ideas), 
the exact upper bound on $\E S$ is 
\begin{equation*}
 \E S_*:=\sup_{p\in[0,1]}\E|N_1(p)-N_2(p)|,\tag{*}
\end{equation*}
where $N_1(p),N_2(p)$ are iid binomial rv's with parameters $n,p$. 
For any rv $X$, we have the formula 
\begin{equation*}
 \E|X|=\frac2\pi\,\int_0^\infty\frac{1-\Re f_X(t)}{t^2}\,dt, 
\end{equation*}
where $f_X$ is the characteristic function (cf) of $X$, so that $f(t)=\E e^{itX}$. 
For instance, this formula for $\E|X|$ is a special case of formula (3.13) in the paper Positive-part moments via characteristic functions, which appears as formula (35) in the arXiv version of that paper. 
In our case, $X=N_1(p)-N_2(p)$ and, again with $q:=1-p$, we have 
\begin{equation*}
 f_X(t)=(q+pe^{it})^n(q+pe^{-it})^n=(1-4pq\sin^2\tfrac t2)^n,
\end{equation*}
which is obviously real-valued and attains its minimum in $p\in[0,1]$ at $p=\tfrac12$, for each natural $n$ and each real $t$. So, the $\sup$ in (*) is attained at $p=\tfrac12$. 
