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.

  • $\begingroup$ Why the fa tag? $\endgroup$ – Jochen Wengenroth May 25 '18 at 16:07
  • $\begingroup$ I would say that the expectation is of order $\sqrt n$: the standard deviation of $A_{(i)}$ from its mean is of order $n^{-1/2}$ for $i$ in the middle range and smaller than that near the ends, the deviations to the right and to the left are about equally likely and independent for $A$ and $B$, and we have $n$ terms in the sum. $\endgroup$ – fedja May 26 '18 at 1:08
  • $\begingroup$ Asymptotically $\frac{\sqrt\pi}4n^{1/2}$, if you want to be more precise. $\endgroup$ – fedja May 26 '18 at 1:38
  • $\begingroup$ @fedja Can you show us your derivation? I Prior to your comment, had found by simulation that for A U[0,1}, S was approximately $0.443 n^{1/2}$, which is consistent with your result, but had no derivation for that, and was still trying to verify for very large n. Thanks. $\endgroup$ – Mark L. Stone May 26 '18 at 11:31
  • 1
    $\begingroup$ @WlodAA independent identically distributed $\endgroup$ – fedja May 29 '18 at 6:15

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.

  • 1
    $\begingroup$ @MarkL.Stone It is just false. Taking endpoints with probability $1/2$ each gives asymptotically $\frac 1{\sqrt\pi}\sqrt n$ (though it is worse for small $n$). One may, indeed, try to get $O(\sqrt n)$ bound for an arbitrary distribution on $[0,1]$ though. I'll let you know if I manage to do it. $\endgroup$ – fedja May 26 '18 at 13:17
  • 1
    $\begingroup$ @MarkL.Stone Yes, it is always $O(\sqrt n)$ and the symmetric endpoint distribution is asymptotically the worst one (I made an arithmetic error in my earlier computation, so it may be the worst one even for each fixed $n$, but I cannot prove that much yet). $\endgroup$ – fedja May 26 '18 at 14:36
  • 1
    $\begingroup$ Note that $\sum_{i=1}^n A_{(i)}-B_{(j)}$ is the end point of a symmetric $n$-step lazy random walk on $\mathbb Z$. The "laziness" depends on $p$, with $p=1/2$ yielding the least lazy walk. I think from here a simple coupling argument can show that $=1/2$ is the worst case. $\endgroup$ – Ron P May 28 '18 at 15:47
  • 1
    $\begingroup$ @RonP Indeed. Just split each zero step with appropriate probability and use the convexity of $|x|$. I guess this finishes the story. $\endgroup$ – fedja May 28 '18 at 15:59
  • 1
    $\begingroup$ Note finally that for the symmetric endpoint distribution $\mathbb{E}(S)=n{2n \choose n}2^{-2n}$ (so that the least upper bound can be given explicitly). This follows easily from results of Ramasubban ( Biometrika, 45 (1958), 549-556) for $\mathbb{E} |X-Y|$, where $X,Y$ are independent and identically $\mathrm{Bin}(n,p)$ distributed). $\endgroup$ – esg May 29 '18 at 18:12

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.


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


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

  • $\begingroup$ @FedorPetrov I just wonder if any of you, guys, have read my concluding discussion with RonP :lol: His approach makes the fact that $p=1/2$ is the worst case scenario a one-liner. :lol: $\endgroup$ – fedja May 29 '18 at 21:23
  • $\begingroup$ @fedja : I had not seen that. However, I cannot discern a clear argument there, even though I would not be surprised if a coupling argument exists -- can you provide details on that? It seems that the absolute value sign is missing in RonP's comment, and also I guess there has to be $B_{(i)}$ in place of $B_{(j)}$ there. $\endgroup$ – Iosif Pinelis May 30 '18 at 0:47
  • $\begingroup$ @fedja well, now I see, nice. Possibly, it makes sense to update your answer. $\endgroup$ – Fedor Petrov May 30 '18 at 6:40
  • $\begingroup$ I got it now. This is what I got: We need to maximize $E|N_1(p)-N_2(p)|$ in $p\in[0,1]$, where $N_1(p),N_2(p)$ are iid binomial rv's with parameters $n,p$. Write $N_1(p)-N_2(p)=\sum_1^n Y_i$, where the $Y_i$'s are iid symmetric rv's with values $-1,0,1$ such that $P(Y_i=1)=pq$. Use now the fact that $Y_i$ is most dispersed when $p=1/2$. $\endgroup$ – Iosif Pinelis May 30 '18 at 12:39

Your Answer

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