# How can I prove Chebyshev's sum inequality with probabilistic methods?

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.

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

• "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. Jan 13, 2021 at 14:22
• @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.
– Seva
Jan 13, 2021 at 14:34
• 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? Jan 13, 2021 at 14:53
• Ah, this may be fixed: after we made $\mathbb{E} A=0$, there exists $c$ such that $A(B-c)\geqslant 0$. Jan 13, 2021 at 15:45
• "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 Jan 14, 2021 at 13:19

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.

• The first inequality ("0 <= ...") is not trivial, and does not follow immediately from the "note that". Jan 14, 2021 at 12:25
• @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? Jan 14, 2021 at 17:09
• 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. Jan 14, 2021 at 17:14
• @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.) Jan 14, 2021 at 21:21
• 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. Jan 14, 2021 at 21:33

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.