Markov's Inequality

From CS2800 wiki

TODO: Test with math package installed! Also can we link within math mode (?) For a nonnegative random variable X and a > 0, P(X >= a) <= E(X) / a

[math]2^A [/math] and [math]A \times B [/math] Proof: TODO: Need math package installed to display. ([math]ax [/math] = 3 = [math]\frac{1}{1} [/math])


Markov's Inequality is an example of a concentration inequality, an inequality that provides bounds on how a random variable (in this case, X) differs from some value (in this case, a). Markov's inequality is useful because they apply to any non-negative random variable. Notice how the bound depends on E(X) and a. If X returns large values on average (E(X) is large) then it is likely X is large. Similarly if E(X) is small, then it likely that X is small. Bigger E(X) means higher probability, so E(X) intuitively goes in the numerator. a is our definition of large. It is more likely that I am taller than 3' than it is that I am taller than 10', Pr(X \geq 3) \geq P(r(X \geq 10). This suggests that increasing a decreases the probability, so a goes in the denominator. ddd