 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2010/b/4/a/solution

For a nonnegative random variable

Y

and

a > 0

P (Y \geq a) \leq \frac{E Y}{a} .

X

of finite mean

μ

σ^{2}

, Chebyshev inequality states that for every

t > 0

P (∣ X - μ ∣ \geq t) \leq \frac{σ ^{2}}{t ^{2}} .

To prove it, apply Markov inequality to the nonnegative variable

(X - μ)^{2}

at threshold

t^{2}

P (∣ X - μ ∣ \geq t) = P ((X - μ)^{2} \geq t^{2}) \leq \frac{E [( X - μ ) ^{2} ]}{t ^{2}} .

 New to topics? Read the docs here!