13
$\begingroup$

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?

  • 1
    An important use (also mentioned on the Wikipedia page) is that Chebyshev can be used to prove the law of large numbers.2011-03-09

3 Answers 3

15

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.

  • 1
    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$).2011-03-09
2

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

1

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