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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.