2
$\begingroup$

I would like to prove Chebyshev's sum inequality, which states that:

If $a_1\geq a_2\geq \cdots \geq a_n$ and $b_1\geq b_2\geq \cdots \geq b_n$, then
$$ \frac{1}{n}\sum_{k=1}^n a_kb_k\geq \left(\frac{1}{n}\sum_{k=1}^n a_k\right)\left(\frac{1}{n}\sum_{k=1}^n b_k\right) $$
I am familiar with the non-probabilistic proof, but I need a probabilistic one.

$\endgroup$
7
$\begingroup$

Let $A$ be the random variable attaining the values $a_1,\dotsc,a_n$ with equal probabilities, and define $B$ similarly, subject to $\mathbb P(B=b_i|A=a_i)=1$. Then $\mathbb E(A)=\frac1n\,\sum_{1\le i\le n} a_i$, $\mathbb E(B)=\frac1n\,\sum_{1\le i\le n} b_i$, and $\mathbb E(AB)=\frac1n\,\sum_{1\le i\le n} a_ib_i$. Since $a_i$ and $b_i$ are similarly ordered, we have $\mathrm{Cov}(A,B)>0$ whence $\mathbb E(AB)\ge\mathbb E(A)\mathbb E(B)$.

$\endgroup$
  • 9
    $\begingroup$ "Since $a_i$ and $b_i$ are similarly ordered, we have ${\rm Cov}(A,B)>0$" - is this somehow obvious? Looks like essentially the same statement which should be proved. $\endgroup$ – Fedor Petrov Jan 13 at 14:22
  • 1
    $\begingroup$ @FedorPetrov: Well taken. Seems you are right when it comes to a formal proof, and yet on the intuitive level, this is considered the most standard property of covariance. So maybe what I have written is more of an informal, but convincing explanation, than a rigorous proof. $\endgroup$ – Seva Jan 13 at 14:34
  • 1
    $\begingroup$ I like the following informal explanation of Chebyshev/rearrangement inequality: if you buy 17 sportcars, 10 smartphones and 3 apple pies you clearly pay more than when you buy 17 smartphones, 10 pies and 3 sportcars, or any other permutation, or if you buy 17+10+3 items for an average price. This is pretty intuitive, what is here to prove at all? $\endgroup$ – Fedor Petrov Jan 13 at 14:53
  • 1
    $\begingroup$ Ah, this may be fixed: after we made $\mathbb{E} A=0$, there exists $c$ such that $A(B-c)\geqslant 0$. $\endgroup$ – Fedor Petrov Jan 13 at 15:45
  • 1
    $\begingroup$ "Since $a_i$ and $b_i$ are similarly ordered, we have $\mathrm{Cov}(A,B)>0$" is obvious for $n=2$ with no equalities. So you can increase $\sum a_ib_i$ by pairwise rearrangements until the two sequences have similar orderings overall $\endgroup$ – Henry Jan 14 at 13:19
11
$\begingroup$

A more general inequality is $$Ef(X)g(X)\ge Ef(X)\,Eg(X),\tag{1}$$ where $f$ and $g$ are nondecreasing (say bounded) functions from $\mathbb R$ to $\mathbb R$ and $X$ is any real-valued random variable. (In your case, $X$ is uniformly distributed on the set $[n]:=\{1,\dots,n\}$, whereas $f$ and $g$ are any nondecreasing bounded functions from $\mathbb R$ to $\mathbb R$ such that $f(j)=a_j$ and $g(j)=b_j$ for all $j\in[n]$.)

To prove (1), note that $(f(x)-f(y))(g(x)-g(y))\ge0$ for all real $x$ and $y$, since $f$ and $g$ are nondecreasing. Therefore, letting $Y$ denote an independent copy of $X$, we have $$0\le E(f(X)-f(Y))(g(X)-g(Y)) \\ =Ef(X)g(X)+Ef(Y)g(Y)-Ef(X)g(Y)-Ef(Y)g(X) \\ =Ef(X)g(X)+Ef(Y)g(Y)-Ef(X)\,Eg(Y)-Ef(Y)\,Eg(X) \\ =Ef(X)g(X)+Ef(X)g(X)-Ef(X)\,Eg(X)-Ef(X)\,Eg(X) \\ =2[Ef(X)g(X)-Ef(X)\,Eg(X)],$$ whence (1) follows.

$\endgroup$
  • $\begingroup$ The first inequality ("0 <= ...") is not trivial, and does not follow immediately from the "note that". $\endgroup$ – einpoklum Jan 14 at 12:25
  • $\begingroup$ @einpoklum : This inequality is a particular case of the following: If a random variable $Z$ is nonnegative, then $EZ\ge0$. Does this look nontrivial for you? $\endgroup$ – Iosif Pinelis Jan 14 at 17:09
  • $\begingroup$ But you didn't apply the expectation to a variable. You applied it to one multiplicand out of two, which you have not established is nonnegative. ... or - maybe you've just gotten the parentheses wrong? I think that might be it. $\endgroup$ – einpoklum Jan 14 at 17:14
  • 1
    $\begingroup$ @einpoklum : Of course, the expectation is of the product, not of the first factor. It is a standard and convenient convention to write $EX$ and $EXYZ$ for $E[X]$ and $E[XYZ]$; see e.g. the two-line display near the middle of page 1685 in the paper at projecteuclid.org/euclid.aop/1176988477 . Otherwise, the multiline display in my answer here would have to contain a huge number of brackets and look terrible, I think. (It helps to remember that $E$ is a linear operator, and no brackets or parentheses are needed to express the action of such an operator.) $\endgroup$ – Iosif Pinelis Jan 14 at 21:21
  • 1
    $\begingroup$ The application of the E to the entire produced is non-standard enough for me, with a Ph.D. in theoretical Comp Sci, not to realize that's what you were doing. So, changed it. $\endgroup$ – einpoklum Jan 14 at 21:33
3
$\begingroup$

I do not know whether this counts, but you may do the following.

At first, you may suppose that $a_n>0$ (otherwise replace all $a_i$ to $a_i-a_n+1$). Consider the probabilistic distribution $\mu$ on $\{1,\ldots,n\}$ such that $p_i={\rm prob} (X=i)=a_i/(a_1+\ldots+a_n)$. Then $p_1+\ldots+p_n=1$, $p_1\geqslant \ldots \geqslant p_n$, and we want to prove that $\mathbb{E}_{\mu} b\geqslant \mathbb{E}_{\lambda} b\,\, (*),$ where $\lambda$ is a uniform distribution, and $b:i\to b_i$ is a decreasing function. For doing this we construct a coupling, that is, a joint distribution $\nu$ of $(X,Y)\in\{1,\ldots,n\}^2$ such that $X$ is distributed as $\mu$, $Y$ as $\lambda$ and $Y\geqslant X$. This gives $(*)$ since $$\mathbb{E}_{\mu} b=\mathbb{E}_\nu b(X)\geqslant \mathbb{E}_\nu b(Y)=\mathbb{E}_\lambda b.$$ For constructing $\nu$, partition the semiinterval $[0,1)$ onto $n$ semiintervals $\Delta_1,\ldots,\Delta_n$ (from left to right) of lengths $1/n$ and semiintervals $\delta_1,\ldots,\delta_n$ of lengths $p_1,\ldots,p_n$. Choose a random point $x\in [0,1]$ at uniform and denote $(X,Y)=(k,i)$ if $x\in \Delta_i\cap \delta_k$.

It remains to prove that $i\geqslant k$. Assume the contrary: $k>i$. Then $x\geqslant p_1+\ldots+p_i\geqslant ip_i$; $1-x\leqslant p_{i+1}+\ldots+p_n\leqslant (n-i)p_i$; $x/i\geqslant p_i\geqslant (1-x)/(n-i)$; $x\geqslant i/n$; $x\notin \Delta_i$. A contradiction.

$\endgroup$

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.