markov's inequality

Markov’s Inequality

If we have a random variable $X\ge 0$ and a positive constant $a>0$, then Markov’s inequality states that

$$P(X\ge a)\le \frac{\mathbb{E}[X]}{a}$$

“Can’t have too much probaility mass too far to the right of the expected value, otherwise there’s not enough mass left to balance it out to the expected value.”
It’s a very loose bound. More useful: chebyshev inequality

EXAMPLE

If we have a random variable $X$ with an expected value of $\mathbb{E}[X]=10$, then the probability that $X$ is at least 20 is at most 50%:

$$P(X\ge 20)\le \frac{10}{20}=0.5$$

If half the time $X$ is 0, then the other half of the time it must be 20 to have an expected value of 10.

Proof:

$$\begin{array}{rl}\mathbb{E}[X]=\sum _{x}P(X=x)& \ge \sum _{x\ge a}xP(X=x)\\ & \ge \sum _{x\ge a}aP(X=x)=aP(X\ge a)\\ \Rightarrow P(X\ge a)& \le \frac{\mathbb{E}[X]}{a}\end{array}$$