optimality of Markov and Chebyshev

Is Markov’s inequality optimal? In a somewhat trivial sense, no. Suppose $X\ge 0$ has mean $\mu$. Consider $t=\mu /2$. By Markov, $\mathbb{P}(X\ge t)\le \mu /t=2$, which is trivial. Since probabilities, are bounded by 1 we can always write

$$\mathbb{P}(X\ge t)\le \min \{\mu /t,1\}.$$

We can also arrive at this conclusion in a slightly more interesting way. For any nonrandom $v\ge 0$, write $\mathbb{P}(X\ge t)=\mathbb{P}(X+v\ge t+v)\le (\mu +v)/(t+v)$. Therefore,

$$\mathbb{P}(X\ge t)\le \underset{v\ge 0}{\inf }\frac{\mu +v}{t+v}.$$

Optimizing over $v$ gives $\min \{u/t,1\}$ on the right hand side.

Achieving Markov

The optimization perspective on Markov’s inequality demonstrates (though it can of course be proved more directly) that the distributions which attain Markov’s inequality take two values. More precisely, if $X\ge 0$ and $\mathbb{P}(X\ge a)=\mu /a$ then $X$ takes the value 0 and $a$. Consequently, the equality can hold only for a single threshold. That is, no distribution can attain $\mathbb{P}(X\ge t)=\mu /t$ for all $t>0$.

Another way to state the optimality is that, for $t\ge 1$,

$$\underset{X\ge 0:\mathbb{E}X=1}{\sup }\mathbb{P}(X\ge t)=\frac{1}{t}.$$

This has consequences for concentration inequalities. In particular, if $X_1$ and $X_2$ are iid and each take two values, then $X_1+X_2$ can take three values. Therefore, Markov’s inequality cannot be tight for more than one random variable.

Achieving Chebyshev

Since $\mathbb{P}(|X-\mu {|}^t\ge t^2)=\mathbb{P}(|X-\mu |\ge t)$ for $t>0$, Chebyshev’s inequality is obtained if Markov is attained by $|X-\mu |$. This implies that random variables $X$ attaining equality in Chebyshev’s inequality can take 3 values: $|X-\mu |=0$, and $|X-\mu |=a$ for some $a$. That is, $X=\mu$, $X=a+\mu$, and $X=-a+\mu$.

As above, if $X_1,X_2$ are iid and each take two values, then $X_1+X_2$ can take three values. This implies that Chebyshev might be tight for sums of two variables. But if $X_3$ is a third iid rv, then $X_1+X_2+X_3$ can take four values, meaning that Chebyshev’s inequality cannot be tight for more than two random variables. This was first proved by Ghosh and Meedenin 1977: On the non-attainability of Chebyshev bounds.