I'm going through the proof of Markov's Inequality, defined as

For a non-negative random variable $X$ with expectation $E(X)=\mu$, and any $\alpha > 0, Pr[X \geq \alpha] \leq \frac{E(X)}{\alpha}$

So, to understand what this was trying to say in the first place, I rephrased it as "the probability that non-negative r.v. $X$ takes on a value greater than $\alpha$ is upper bounded by $\frac{E(X)}{\alpha}$".

Now, my book goes into the proof in the following manner:

$E(X) = \sum_a a \times Pr[X=a]$ this line makes perfect sense

$E(X) \geq \sum_{a \geq \alpha} a \times Pr[X=a]$ why did they introduce an inequality here? The book also says that this is a crucial step where we have used the fact that $X$ takes on only non-negative values. I don't understand where that property is being used. I tried plugging in an r.v. that took negative values and didn't see anything out of the ordinary - why is it a constraint in this theorem?

$E(X) \geq \alpha \sum_{a \geq \alpha} Pr[X=a]$ how can you pull out $\alpha$ out of the summation?

$E(X) = \alpha Pr[X \geq \alpha]$ how did the inequality change places?

  • 2
    $\begingroup$ Using $a$ as a summation index where $\alpha$ is a parameter of the sum is incredibly confusing $\endgroup$ – user438666 May 29 '17 at 7:20
  • $\begingroup$ @Chris I agree! $\endgroup$ – Carpetfizz May 29 '17 at 7:25

$$E(x)=\sum_{k}k \cdot Pr[X=k]$$ until here no problem. Note that the sum is done on the support of $X$, which means that in this case the $k$ are all the possible values of $X$, and the hypothesis of non negativity allows you to say that $k\geq0$. Thus you can remove any number of terms from the sum and the remaining sum will be smaller, because the terms you removed are positives. So we have $$E(x)=\sum_{k}k \cdot Pr[X=k]\geq \sum_{k\geq\alpha}k \cdot Pr[X=k]$$ Now, the $k$ are positives and greater than $\alpha$. If you substitute every $k$ with an $\alpha$, you will obtain a smaller sum

$$E(x)=\sum_{k}k \cdot Pr[X=k]\geq \sum_{k\geq\alpha}k \cdot Pr[X=k]\geq \sum_{k\geq\alpha}\alpha Pr[X=k]=\alpha\sum_{k\geq\alpha}Pr[X=k]=\alpha Pr[X\geq\alpha]$$

Where you can pull out the $\alpha$ because it is not an index of the summation.

  • $\begingroup$ I think I'm starting to understand. The reason $X \geq 0$ is because the summation of a subset of $X$'s values, restricted to $k \geq \alpha$ is less than summation of the set of $X$'s values. That seems to be what your second line illustrates. Now, the part I don't understand is when you say "substitute every $k$ with $\alpha$ but it seems like you are using them together. what is the purpose of doing this? $\endgroup$ – Carpetfizz May 29 '17 at 7:37
  • 1
    $\begingroup$ Imagine that $X$ is some variable that can take values from 1 to 10. Then if I take the sum for $k\geq 5$, I can safely substitute every multiplicating $k$ with the number 5, because $5Pr[X=5]+6Pr[X=6]+7Pr[X=7] ...\geq 5Pr[X=5]+5Pr[X=6]+5Pr[X=7] ...$. "Every $k$" was actually misleading, I meant every multiplicating $k$ $\endgroup$ – user438666 May 29 '17 at 7:42
  • $\begingroup$ Thought I understood all of it but I'm stuck on the last part. I understand that $\sum_{k \geq \alpha} \alpha Pr[X=k] = \alpha \sum_{k \geq \alpha} Pr[X = k]$ but how come the inequality was dropped? Further more, how does the latter expression equal, $\alpha Pr[X \geq \alpha]$ ? I know that since we are summing over $k \geq \alpha$, the probability only measures values of the r.v. $X \geq \alpha$ but where did the summation go? $\endgroup$ – Carpetfizz May 29 '17 at 18:26
  • 1
    $\begingroup$ I don't understand what do you mean by "how the inequality was dropped", for your second point think of $\sum_{k\geq \alpha}Pr[X=k]= Pr[X=\alpha]+Pr[X=\alpha+1]+Pr[X=\alpha+2] ...$ as the probability that $X$ is equal to $\alpha$ OR $\alpha+1$ OR $\alpha+2$ etc.., you see that this sum amounts to the probability that $X$ is greater or equal to $\alpha$? $Pr[X\geq \alpha]$ is called a cumulative distribution function, and it can be proven rigorously that it is calculated that way (with the sum). $\endgroup$ – user438666 May 29 '17 at 20:51
  • 1
    $\begingroup$ You're welcome :) $\endgroup$ – user438666 May 29 '17 at 21:21

We have $E(X)=\sum_a aP(X=a)=\sum_{a:a<\alpha}aP(X=a)+\sum_{a:a\geq \alpha}aP(X=a)$

Since $X\geq0$ we have the values that $X$ takes are non-negatie, so $aP(X=a)\geq0$ for all $a$ (If $a$ is negative then $P(X=a)=0$ so $aP(X=a)=0$). Therefore, $\sum_{a:a<\alpha}aP(X=a)\geq0$

Thus $E(X)\geq \sum_{a:a\geq\alpha}aP(X=a)$

In this final summation, each $a\geq\alpha$ so $aP(X=a)\geq \alpha P(X=a)$ thus $\sum_{a:a\geq\alpha}aP(X=a)\geq \alpha\sum_{a:a\geq \alpha}P(X=a)=\alpha P(X\geq\alpha)$

Hence you finally get $E(X)\geq \alpha P(X\geq \alpha)$ for any $\alpha>0$.


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.