 Solution

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

For a variable

Z

of finite variance and

t > 0

P (∣ Z - EZ ∣ \geq t) \leq \frac{Var Z}{t ^{2}} .

On that event,

(Z - EZ)^{2} \geq t^{2}

. Thus

t^{2} P (∣ Z - EZ ∣ \geq t) \leq E [(Z - EZ)^{2}]

, proving the assertion. Equivalently apply Markov's inequality to the squared deviation.

 New to topics? Read the docs here!