# Chebyshev's versus Markov's inequality

More important than knowing inequalities by hearts is knowing when and how to apply them and what they express.

Regarding Chebyshev's and Markov's inequality. What is the relation (if any) between them? Which one is more strict (and in which situation)? Is there an easy way to understand what they express (kind of like drawing a triangle for the triangle inequality)? What is a typical application in probability theory? What are applications outside of probability theory?

-
(Not substantial enough for an answer, so this is a comment.) You can prove Chebyshev's inequality from Markov's inequality, as the Wikipedia pages indicate. So in that sense it would seem Chebyshev is more strict. –  Mike Spivey Mar 9 '11 at 16:57
Thanks Mike Spivey and PEV. So Markov implies Chebyshev. But what are the typical uses of them and why give a separate name to Chebyshev's (seems to be important by itself even though it can be derived in a single line). –  Fabian Mar 9 '11 at 17:10
An important use (also mentioned on the Wikipedia page) is that Chebyshev can be used to prove the law of large numbers. –  Mike Spivey Mar 9 '11 at 17:42

Markov's inequality is a "large deviation bound". It states that the probability that a non-negative random variable gets values much larger than its expectation is small.

Chebyshev's inequality is a "concentration bound". It states that a random variable with finite variance is concentrated around its expectation. The smaller the variance, the stronger the concentration.

Both inequalities are used to claim that most of the time, random variables don't get "unexpected" values.

A typical application of concentration bounds is polling - if you poll 200 people, then the standard deviation is so-and-so, and so the probability that the results are off by some amount $x$ is only $p$ which is very small. You can bound $p$ using Chebyshev's inequality, although there are better bounds.

Another application is in the statistics of patients in a hospital. Suppose they conduct a survey and find that the average number of patients per day is 10. Suppose they want to be able all patients 90% of the time. Then they need to handle at most 100 patients.

The list of probability results goes on. The law of large numbers states that the average of identical random variables tends (almost certainly) to the expectation. The central limit theorem describes the behavior of the noise, but only "close" to the expectation. Chernoff bounds are large deviation bounds useful for understanding the behavior of the noise away from the expectation.

-
Am I right with the feeling that the fact that the random variable is nonnegative is essential for the inequality? Having also negative values allowed it cut assemble half of the probability at $N$ and half at $-N$ with $N$ as large as wanted and still having expectation value zero --- nevertheless, the probability to have $X$ as large as $N$ would be $1/2$. If I restrict $X$ to be nonnegative (and for simplicity assume $E(X)=1$) then the best (worst) I can do is to assemble the "counter-weight" at $X=0$ which of course restricts the weight at large $N$ to $1/N$ in order to keep $E(X)=1$. –  Fabian Mar 9 '11 at 17:40
That's accurate, and is exactly the proof of Markov's inequality. You can generalize Markov's inequality to the cases $X \geq l$ and $X \leq h$ for arbitrary $l,h$ (the bound will depend on $l$ or $h$). –  Yuval Filmus Mar 9 '11 at 19:10

As you can see in the wikipedia links, Markov's inequality can be used to prove Chebyshev's Inequality.

-

$t\mu\{x\in X : |f(x)|\geq t\}\leq\int_Xf$ is simple to remember. take a value $t$ use it for a lower bound for $f$ on $\{x\in X : |f(x)|\geq t\}$. This is definitely less or equal $\int_X f$. take the graph of a nice function $f$, draw a horizontal line at height $t$, and take the area underneath the line and under the graph.

-