Upper bound of the expectation of sum of the absolute value pairs

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

$\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$.

Answer 4

$\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}}$

I will borrow the excellent idea of user fedja about a simplex. Without loss of generality (wlog), the iid random variables (rv's) are simple functions, of the form $\sum_{j=1}^k x_j\,1_{E_j}$ for some disjoint measurable sets $E_j$ and some (not necessarily distinct) $x_j$'s in $[0,1]$. Then $\E S$ is a convex function of $x:=(x_1,\dots,x_n)\in[0,1]^n$ and hence attains its maximum in $x\in[0,1]^n$ at some $x\in\{0,1\}^n$. Hence, wlog each of the iid rv's takes only two values, $1$ and $0$, with probabilities $p$ and $q:=1-p$, for some $p\in[0,1]$. So, the exact upper bound on $\E S$ is \begin{equation*} \E S_*:=\sup_{p\in[0,1]}\E|N_1(p)-N_2(p)|=\sup_{p\in[0,1]}T(p),\tag{0} \end{equation*} where $N_1(p),N_2(p)$ are iid binomial rv's with parameters $n,p$, \begin{equation*} T(p):= \sum_{i,j=0}^n|i-j|\binom ni\binom nj a_{i+j}(p), \end{equation*} and \begin{equation*} a_k(p):=a_{n,k}(p):=p^{k}q^{2n-k}. \end{equation*}

We have \begin{equation*} T(p)=\sum_{k=0}^{2n}a_k(p)s_k, \end{equation*} \begin{align*} s_k:=\sum_{i=0}^k|i-(k-i)|\binom ni\binom n{k-i} &= \frac2n\,m \binom{n}{m} (n-k+m) \binom{n}{k-m} \tag{1} \\ &= \left\{ \begin{aligned} 2n\,\binom{n-1}{m-1}^2 &\text{ if }k=2m-1,\\ 2n\,\binom{n-1}{m-1} \binom{n-1}{m} &\text{ if }k=2m, \end{aligned} \right. \end{align*} where $m:=\left\lceil \frac{k}{2}\right\rceil$; the second equality in (1) was obtained with Mathematica (I will check it later).

Next, \begin{equation*} T(p)=T_1(p)+T_0(p), \tag{1.5} \end{equation*} \begin{equation*} T_1(p):=\sum_{m=1}^{n}a_{2m-1}(p)s_{2m-1},\quad T_0(p):=\sum_{m=1}^{n}a_{2m}(p)s_{2m}. \end{equation*}

Further, $T_1(p)$ is a hypergeometric expression and, accordingly, it satisfies the diff. eq. \begin{equation*} pq (1-4npq) T_1 '(p)+(p-q) (1-2npq) T_1 (p) +(p-q)(pq)^2 T_1 ''(p)=0. \tag{2} \end{equation*} Also, we have the symmetry $T_1(1-p)=T_1(p)$. So, $T'_1(1/2)=0$. Moreover, if $0<p<1/2$, $2npq>1$, and $T_1 '(p)$, then (2) and the positivity of $T_1(p)$ imply $T_1 ''(p)>0$. So, there are no local maxima of $T_1$ in the interval \begin{equation*} J_n:=\{p\colon 0<p<1/2,2npq>1\}. \end{equation*}

Let us now state two lemmas.

Lemma 1. For $n\ge12$ and $p\in[0,1/2)\setminus J_n$, we have $T_1(p)<T_1(1/2)$, so that \begin{equation*} \max_{0<p<1}T_1(p)=T_1(1/2). \tag{3} \end{equation*}

Lemma 2. For $n\le11$, (3) holds.

These lemmas will be proved at the end of the answer.

Lemmas 1 and 2, together with the previous observations that $T_1$ is positive and symmetric and that there are no local maxima of $T_1$ on $J_n$, yield (3) for all natural $n$.

The consideration of $T_0(p)$ is similar to, and much easier than, that of $T_1(p)$. We have \begin{equation*} (1-4npq) T_0'(p)-2n(p-q) T_0(p)+ (p-q)pq T_0''(p)=0. \end{equation*} So, there are no local maxima of $T_0$ in the entire interval $[0,1/2)$. Also, $T_0(0)=0<T_0(1/2)$. Therefore, $\max_{0<p<1}T_0(p)=T_0(1/2)$, and so, in view of (3), $\max_{0<p<1}T(p)=T(1/2)$, for all natural $n$. That is, the exact upper bound on $\E S$ is \begin{equation*} \E S_*=T(1/2)=\E|N_1(1/2)-N_2(1/2)|. \end{equation*}

For large $n$, using the normal approximation to the binomial distribution with parameters $n,p=1/2$, we see that the best upper bound on $\E S$ can be approximated as follows: \begin{equation*} \E|N_1(1/2)-N_2(1/2)| \approx\E|Z_1-Z_2|\sqrt{n\tfrac12\,\tfrac12}=\E|Z\sqrt2|\sqrt{n/2}=\frac1{\sqrt\pi}\,\sqrt n, \end{equation*} where $Z,Z_1,Z_2$ are iid standard normal rv's.

It remains to prove the two lemmas. Lemma 2 is proved by direct calculation, using the fact that $T_1(p)$ is a polynomial in $p$ of degree $2n$. It remains to present

Proof of Lemma 1. We have \begin{equation*} T_1(p)\le T(p)=\E|N_1(p)-N_2(p)|\le\sqrt{\E(N_1(p)-N_2(p))^2}= \sqrt{2\mathsf{Var}\,N_1(p)}=\sqrt{2npq}\le1 \tag{4} \end{equation*} for $p\in[0,1/2)\setminus J_n$. On the other hand, \begin{equation*} T_1(1/2)= 2^{1-2 n} n\sum_{m=1}^{n}\binom{n-1}{m-1}^2 =2^{1-2 n} n \binom{2 (n-1)}{n-1}, \end{equation*} which is easily seen to be increasing in natural $n$, with $T_1(1/2)=1.0091\ldots>1$ for $n=12$. So, in view of (4), Lemma 1 follows.