Markov’s Inequality

How likely is it that the absolute value of a random variable X will be greater than some specific value, say, a? 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 X is a random variable with mean \mu, and a>0 is a positive number, then

Pr[|X| \geq a] \leq \frac{|\mu|}{a}

Proof

Let I be an indicator variable such that

I = \left\{\begin{array}{cc}1 & \text{if } |X| \geq a \\ 0 & \text{otherwise}\end{array}\right.

If we take n samples from X, namely X_1, X_2, \cdots, X_n, some of them will be \geq a and the rest will be < a. Let I_1, I_2,\cdots, I_n be the value of I for the event X=X_i, 1\leq i\leq n. Therefore,

\begin{array}{ccl}\sum_{i=1}^{n}{I_i}&=&0\times \text{Number of cases where }I_i=0\\&&+1\times \text{Number of cases where } I_i=1\\&=&\text{Number of cases where } I_i=1\end{array}

and the expected value of $I$ will be

\begin{array}{ccl} E[I] & = & \frac{\sum_{i=1}^n{I_i}}{n}\\ & = & \frac{\text{Number of cases where } I_i=1}{n}\\ & = & \Pr\left[|X| \geq a\right]\end{array}.

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

  • If |X| \geq a, then I = 1 and thus aI = a \leq |X|
  • If |X| < a, then I = 0 and thus aI = 0 \leq |X|

Therefore, we have

aI \leq |X|

Taking the expectation at both sides, we have

\begin{array}{cl} & E[aI] \leq E[|X|]\\\implies & aE[I] \leq |\mu|\\\implies & a\Pr\left[|X| \geq a\right] \leq |\mu|\\\implies &\Pr\left[|X| \geq a\right] \leq \frac{|\mu|}{a}\end{array}

Proved \square

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 \geq 3 goals today is at most

\frac{0.5}{3} = \frac{1}{6} \approx 0.16.

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 X in addition to its mean.

Advertisements

One thought on “Markov’s Inequality

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s