The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan

How likely is it that the absolute value of a random variable will be greater than some specific value, say, ? The Russian mathematician Andrey Andreyevich Markov proved a simple, yet nice, result which enables us to answer the above question.

Markov’s Inequality states that if is a random variable with mean , and is a positive number, then

Proof

Let be an indicator variable such that

If we take samples from , namely , some of them will be and the rest will be . Let be the value of for the event . Therefore,

and the expected value of $I$ will be

.

Now, looking at , we can make the following observations:

If , then and thus

If , then and thus

Therefore, we have

Taking the expectation at both sides, we have

Proved

What is the use?

We can use this inequality to derive an upper bound to a random variable.

For example, suppose that Lionel Messi scores 1 goal in every two matches he plays, on average. (Therefore, he scores 0.5 goals per match, on average). Today he is playing against your team, and you hope that he does not score many goals. You ask: what is the probability that he will not score a hat-trick today? Using Markov’s inequality, we can say, the probability that he scores 3 goals today is at most

.

Therefore, there is close to 84% chance that he will not score three goals today.

Comments

Markov’s inequality, while simple, gives rather loose bound. A much tighter bound can be found using Chebyshev’s inequality if we know the variance of in addition to its mean.

## One thought on “Markov’s Inequality”