# Markov's Inequality Proof confusion

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?

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

## 2 Answers

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

• 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? – Carpetfizz May 29 '17 at 7:37
• 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$ – user438666 May 29 '17 at 7:42
• 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? – Carpetfizz May 29 '17 at 18:26
• 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). – user438666 May 29 '17 at 20:51
• You're welcome :) – 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$.