46
$\begingroup$

Chebychev's Inequality Let $f$ be a nonnegative measurable function on $E .$ Then for any $\lambda>0$, $$ m\{x \in E \mid f(x) \geq \lambda\} \leq \frac{1}{\lambda} \cdot \int_{E} f. $$

What exactly is this inequality telling us? Is this saying that there is a inverse relationship between the size of the measurable set and the value of the integral?

$\endgroup$
6
  • 7
    $\begingroup$ Let $S = \{ x \in E \mid f(x) \geq \lambda\}$. Maybe it's more clear to think of Chebyshev's inequality as $\int_E f \geq \lambda m(S)$. Proof: $\int_E f \geq \int_S f \geq \int_S \lambda = \lambda m(S)$. $\endgroup$
    – littleO
    May 12 at 2:54
  • 3
    $\begingroup$ Think of it in terms of probability. When $m$ is a probability measure, this is Markov's inequality, saying that "The probability that $f(X)$ exceeds $\lambda$ is at most $\mathbb{E}[f(X)]/\lambda$." $\endgroup$
    – Clement C.
    May 12 at 3:15
  • 4
    $\begingroup$ It says that an integrable function cannot be too large on large sets. It is a generalisation of the rough intuition one gets by analysing which `spike functions' $x^{-s}$ belong to $L^1([0,1])$ $\endgroup$ May 12 at 3:18
  • 1
    $\begingroup$ "Assuming that you've never had a day with negative reputation change, the number of days when you've hit the rep-cap must be smaller than 1/200-th of your total reputation." $\endgroup$ May 12 at 17:43
  • 1
    $\begingroup$ Note this is often called Markov's inequality to distinguish it from one also called Chebyshev's inequality involving second moments $\endgroup$
    – Henry
    May 13 at 12:02
25
+500
$\begingroup$

The essential point is that $$0 \leq \lambda \cdot 1_{\{x \in E \;|\; f(x) \geq \lambda \} } \leq f$$

where $1_{\{x \in E \;|\; f(x) \geq \lambda \} }$ is the characteristic (indicator) function of $\{x \in E \;|\; f(x) \geq \lambda \}$.

Let us see.

Let $A$ be $\{x \in E \;|\; f(x) \geq \lambda \} $. Then it is clear that $$0 \leq \lambda \cdot 1_A \leq f$$ So $$0 \leq \lambda \cdot m(A)= \int_E \lambda \cdot 1_A \leq \int_E f$$

So, since $\lambda >0$, we have

$$m(\{x \in E \;|\; f(x) \geq \lambda \} )= m(A) \leq \frac{1}{\lambda}\int_E f $$

$\endgroup$
8
  • 1
    $\begingroup$ it's not about restrictions. it's about intuition. maybe constraint breeds creativity. by constraining, not really restricting, the view to probability, we might get some intuition of this inequality at least for probability and then perhaps generalise the intuition for measure theory. am i wrong? i think that's kinda what was done in the question i linked $\endgroup$
    – BCLC
    May 13 at 16:52
  • 3
    $\begingroup$ @BCLC , It is a matter of personal taste. I find the intuition in the general context of measure theory clearer and more helpful. $\endgroup$
    – Ramiro
    May 13 at 17:12
  • 1
    $\begingroup$ Apparently the OP was happy with this, but imho it does not answer the question. $\endgroup$
    – Carsten S
    May 14 at 7:35
  • 1
    $\begingroup$ @DullandWitlessBoi, Yes, exactly. I will add line make it explicit. Thanks. $\endgroup$
    – Ramiro
    May 19 at 20:26
  • 1
    $\begingroup$ Thanks, I've seen both the $\textbf{1}$ notation and also with $\chi_S$. Just wanted to be sure!! :) $\endgroup$
    – user711703
    May 20 at 1:43
75
$\begingroup$

It can be helpful to draw a picture:

enter image description here

Here:

  • the blue curve is $f(x)$,
  • the base of the red box is the set $\{x \in E: f(x) \ge \lambda\}$,
  • the height of the red box is $\lambda$.

Chebyshev's inequality says that the area in the red box is less than the area under the blue curve $f(x)$.

The only issue with this picture is that, depending on $\lambda$ and $f$, you might have multiple boxes under the curve at different locations, instead of just one. But then the same thing applies to the sum of the areas under the boxes.

$\endgroup$
7
  • $\begingroup$ helpful to think of probability here? or not really? i was thinking back to my 1st question on maths se Borel-Cantelli Lemma “Corollary” in Royden and Fitzpatrick $\endgroup$
    – BCLC
    May 13 at 3:47
  • 8
    $\begingroup$ I was looking for this answer! Life changing when I first saw it. +1 $\endgroup$ May 13 at 5:02
  • $\begingroup$ The picture is nice. However, in the last paragraph of the answer there is a flaw. The "multiple boxes" may be uncountable many ones. So we can not simply consider "the sum of the areas under the boxes". Example: take $f$ to be the indicator function of the irrationals in $[0,1]$ and $\lambda =1/2$, consider $\{x \in [0,1] \mid f(x) \geq 1/2\}$. In this case we will have an uncountable set of "boxes". $\endgroup$
    – Ramiro
    May 15 at 11:59
  • $\begingroup$ @Ramiro Sure. Or, for a countably infinite example, the indicator function on the fat cantor set. And probably "most" measurable functions are pathological like this in some sense. But my goal here is to provide intuition, not a proof (the proof is pretty much trivial once one understands the concept) $\endgroup$
    – Nick Alger
    May 15 at 12:39
  • 2
    $\begingroup$ @Ramiro I'd also like to add that the idea of thinking about measures in terms of sums of boxes is actually a good intuition, as this mirrors the process of how the Lebesgue outer measure is constructed. $\endgroup$
    – Nick Alger
    May 15 at 13:01
15
$\begingroup$

You could think of it like this. At a birthday party, everyone eats a certain amount of cupcakes. The total number of cupcakes eaten is greater than or equal to $\lambda$ times the number of people who ate at least $\lambda$ cupcakes.

Translating this into a proof: Let $S = \{ x \in E \mid f(x) \geq \lambda \}$. Then $$ \int_E f \geq \int_S f \geq \int_S \lambda = \lambda m(S). $$

$\endgroup$
1
6
$\begingroup$

Flip it around, and cutting E for simplicity, we get:

$$m\{ f(x) \ge \lambda \} * \lambda \leq \int f$$

The measure over the region where $f$ is at least $\lambda$, times $\lambda$, isn't bigger than the integral over the entire region.

Imaging we take a our function, and we define a cut off we call $\lambda$. We shave off everything higher than $\lambda$, and we set everything under $\lambda$ to zero. Chebychev simply states we didn't make its integral bigger by doing this.

Let $g_S$ be the function 1 on $S$ and 0 elsewhere. Then $\lambda g_S$ is 0 everywhere except on some set $S$, where it equals $\lambda$. The integral is equal to the measure of $S$ times $\lambda$.

This $g = \lambda g_{f(x)\ge\lambda}$ is (non-strictly) under $f$, and the set where it is non-zero is exactly your set $A$, where it has height $\lambda$. Its integral is $\lambda$ times the measure of the set it is non-zero. The difference between them, $h = f-g$ is non-negative, and $\int f = \int (g+h)$. $h$ is non-negative, so you'd expect adding it to $g$ would make its integral not-smaller.

$\int g$ is basically our $m\{f(x) \ge \lambda\} * \lambda$ here, and $h$ is the excess portion of $f$ above $g$.

$\endgroup$
5
$\begingroup$

In a probabilistic setting, this leads to an upper bound on the total of two tails of a distribution when the tails start at equal distances on either side of the mean:

$$P(|X-\mu| \geq \lambda) = P((X-\mu)^2 \geq \lambda^2) $$ $$ \leq \frac{E[(X-\mu)^2]}{\lambda^2} = \frac{\sigma^2}{\lambda^2}, $$

where $\mu$ is the mean of random variable $X$ and $\sigma^2$ is its variance.

Written slightly differently as

$$ P(|X-\mu| \geq \lambda\sigma )\leq \frac{1}{\lambda^2}, $$

it says that no more than $1/\lambda^2$ of the distribution's values can be $\lambda$ or more standard deviations away from the mean.

EDIT: It's also worth mentioning that integrating the left-hand side piece (after multiplying by $\lambda$), aka the area in the popular picture below,

$$ \lambda m\{x \in E \mid f(x) > \lambda\}, $$ we have

$$ \int_0^\infty \lambda m\{x \in E \mid f(x) > \lambda\} \; d\lambda = \frac{1}{2}\int_E f^2 $$

from layer-cake representation.

$\endgroup$
1
2
$\begingroup$

Let's assume the usual setup of non-negative, measurable functions on a space with finite Lebesgue measure. Bounded functions are integrable, but there are many integrable functions that are not bounded. A natural question therefore, is "how unbounded can they be?" Chebyshev gives a quantitative answer: in rough terms, it says that an integrable function cannot be too large on large sets, with the power law type decay $m(f>r)\le C/r$.

(When $r$ is too small the inequality becomes rather weak especially in probability theory or when your measure space is otherwise finite so let’s ignore that scenario.)

One could guess that something like Chebyshev should hold by checking the inequality on 'spike functions' $x^{-s}$ for $s>0$. For the range $s\in(0,1)$, $x^{-s}$ are in $L^1([0,1])$ despite being unbounded. In this case, for $r>1$ $$m(x^{-s}>r)= m((0,r^{-1/s}))=\frac1{r^{1/s}} < \frac 1r $$ since $r^{1/s}>r$, in turn since $1/s>1$.

If we allow $s$ to be too big i.e. $s>1$ i.e. $1/s<1$, then the inequality reverses: $$ \frac 1{r^{1/s}} > \frac1r$$ So we cannot expect the inequality of Chebyshev type to hold with the decay $1/r$, even if we replace the factor $\int f dx$ by something finite.

It’s interesting that the borderline case of $1/x$ which is $s=1$ just barely fails to be integrable; one manifestation of this is that it achieves the $1/r$ bound exactly. Another way to rephrase Chebyshev is therefore that integrable functions are dominated by (a rearrangement of) $C/x$. This actually leads one to consider the ‘weak $L^1$ space’ which is essentially a space of functions for which we have Chebyshev’s inequality (but not necessarily $L^1$ control). This space turns out to be very useful in harmonic analysis (see for example, the Marcinkiewicz interpolation theorem and its application to the Hardy-Littlewood maximal function).

Finally I note that we can actually refine Chebyshev into a comparison with other power laws $1/x^s$, or even any decreasing function. This comes from first rewriting the set before applying Chebyshev

$$m(f>r)=m(f^s > r^s) \le \frac{\|f\|_{L^s}^s}{r^s}$$

This lets you recover the sharp decay of other power laws as well.

Setting $s=2$ is usually what Probabilists call Chebyshev ($s=1$ is then called Markov's inequality) but you can trivially do the same trick with any increasing function instead of $x^s$; a very useful variation in extremal probability theory is the Chernoff bound $$m(f>r)\le \frac{\|e^{tf}\|_{L^1}}{e^{tr}}$$ which gives exponential decay, if you can control the moment generating function.

$\endgroup$
2
  • $\begingroup$ This is a great answer that deserves more upvotes. Other answers (mine included) explain what the inequality says. This answer gives insight into the utility of the inequality; what it can do for you; why it shows up so much in analysis. $\endgroup$
    – Nick Alger
    May 23 at 10:45
  • 1
    $\begingroup$ Thanks for the endorsement! :) @NickAlger $\endgroup$ May 23 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.