0 like 0 dislike
134 views
Prove

(Markov's inequality). Suppose $X$ is a nonnegative random variable and $a \in$ is a positive constant. Then
$P(X \geq a) \leq \frac{E X}{a}$
| 134 views

0 like 0 dislike
By definition of expectation, we have
\begin{aligned} E X &=\sum_{k \in X(\Omega)} k P(X=k) \\ &=\sum_{k \in X(\Omega) \text { st. } k \geq a} k P(X=k)+\sum_{k \in X(\Omega) \text { s.t. } k<a} k P(X=k) \\ & \geq \sum_{k \in X(\Omega) \text { s.t. } k \geq a} k P(X=k) \\ & \geq \sum_{k \in X(\Omega) \text { s.t. } k \geq a} a P(X=k) \\ &=a \sum_{k \in X(\Omega) \text { s.t. } k \geq a} P(X=k) \\ &=a P(X \geq a) \end{aligned}

where the first inequality follows from the fact that $X$ is nonnegative and probabilities are nonnegative, and the second inequality follows from the fact that $k \geq a$ over the set $\{k \in X(\Omega)$ s.t. $k \geq a\}$.
Notation: "s.t." stands for "such that".
Dividing both sides by $a$, we recover
$P(X \geq a) \leq \frac{E X}{a}$
by Platinum (132,156 points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike