In this segment, we derive and discuss the Markov inequality,
a rather simple but quite useful and powerful fact about
probability distributions.
The basic idea behind the Markov inequality as well as
many other inequalities and bounds in probability theory
is the following.
We may be interested in saying something about the
probability of an extreme event.
By extreme event, we mean that some random variable takes a
very large value.
If we can calculate that probability exactly, then, of
course, everything is fine.
But suppose that we only have a little bit of information
about the probability distribution at hand.
For example, suppose that we only know the expected value
associated with that distribution.
Can we say something?
Well, here's a statement, which is quite intuitive.
If you have a non-negative random variable, and I tell
you that the average or the expected value is rather
small, then there should be only a very small probability
that the random variable takes a very large value.
This is an intuitively plausible statement, and the
Markov inequality makes that statement precise.
Here is what it says.
If we have a random variable that's non-negative and you
take any positive number, the probability that the random
variable exceeds that particular number is bounded
by this ratio.
If the expected value of X is very small, then the
probability of exceeding that value of a will also be small.
Furthermore, if a is very large, the probability of
exceeding that very large value drops down because this
ratio becomes smaller.
So that's what the Markov inequality says.
Let us now proceed with a derivation.
Let's start with the formula for the expected value of X,
and just to keep the argument concrete, let us assume that
the random variable is continuous so that the
expected value is given by an integral.
The argument would be exactly the same as in the discrete
case, but in the discrete case, we would be using a sum.
Now since the random variable is non-negative, this integral
only ranges from 0 to infinity.
Now, we're interested, however, in values of X larger
than or equal to a, and that tempts us to consider just the
integral from a to infinity of the same quantity.
How do these two quantities compare to each other?
Since we're integrating a non-negative quantity, if
we're integrating over a smaller range, the resulting
integral will be less than or equal to this integral here,
so we get an inequality that goes in this direction.
Now let us look at this integral here.
Over the range of integration that we're considering, X is
at least as large as a.
Therefore, the quantity that we're integrating from a to
infinity is at least as large as a times the density of X.
And now we can take this a, which is a constant, pull it
outside the integral.
And what we're left with is the integral of the density
from a to infinity, which is nothing but the probability
that the random variable takes a value larger
than or equal to a.
And now if you compare the two sides of this inequality,
that's exactly what the Markov inequality is telling us.
Now it is instructive to go through a second derivation of
the Markov inequality.
This derivation is essentially the same conceptually as the
one that we just went through except that it is more
abstract and does not require us to write down any explicit
sums or integrals.
Here's how it goes.
Let us define a new random variable Y, which is equal to
0 if the random variable X happens to be less than a and
it is equal to a if X happens to be larger
than or equal to a.
How is Y related to X?
If X takes a value less than a, it will still be a
non-negative value, so X is going to be at least as large
as the value of 0.
that Y takes.
If X is larger than or equal to a, Y will be a, so X will
again be at least as large.
So no matter what, we have the inequality that Y is always
less than or equal to X. And since this is always the case,
this means that the expected value of Y will be less than
or equal to the expected value of X.
But now what is the expected value of Y?
Since Y is either 0 or a, the expected value is equal to a
times the probability of that event, which is a times the
probability that X is larger than or equal to a.
And by comparing the two sides of this inequality, what we
have is exactly the Markov inequality.
Let us now go through some simple examples.
Suppose that X is exponentially distributed with
parameter or equal to 1 so that the expected value of X
is also going to be equal to 1, and in that case, we obtain
a bound of 1 over a.
To put this result in perspective, note that we're
trying to bound a probability.
We know that the probability lies between 0 and 1.
There's a true value for this probability, and in this
particular example because we have an exponential
distribution, this probability is equal to e to the minus a.
The Markov inequality gives us a bound.
In this instance, the bound takes the form of 1 over a,
and the inequality tells us that the true value is
somewhere to the left of here.
A bound will be considered good or strong or useful if
that bound turns out to be quite close to the correct
value so that it also serves as a fairly accurate estimate.
Unfortunately, in this example, this is not the case
because the true value falls off exponentially with a,
whereas the bound that we obtained falls off at a much
slower rate of 1 over a.
For this reason, one would like to have even better
bounds than the Markov inequality, and this is one
motivation for the Chebyshev inequality that we will be
considering next.
But before we move there, let us consider one more example.
Suppose that X is a uniform random variable on the
interval from minus 4 to 4, and we're interested in saying
something about the probability that X is larger
than or equal to 3.
So we're interested in this event here.
So the value of the density, because we have a range of
length 8, the value of the density is 1/8.
So we know that this probability has a true value
of 1 over 8, which we can indicate on a diagram here.
Probabilities are between 0 and 1.
We have a true value of 1 over 8.
Lets us see what the Markov inequality is
going to give us.
There's one difficulty that X is not a non-negative random
variable, so we cannot apply the Markov
inequality right away.
However, the event that X is larger than or equal to 3 is
smaller than the event that the absolute value of X is
larger than or equal to 3.
That is, we take this blue event and we also add this
green event, and we say that the probability of the blue
event is less than or equal to the probability of the blue
together with the green event, which is the event that the
absolute value of X is larger than or equal to 3.
So now we have a random variable, which is
non-negative, and we can apply the Markov inequality and
write that this is less than or equal to the expected value
of the absolute value of X divided by 3.
What is this expectation of the absolute value of X?
X is uniform on this range.
The absolute value of X will be taking values only
between 0 and 4.
And because the original distribution was uniform, the
absolute value of X will also be uniform on the
range from 0 to 4.
And for this reason, the expected value is going to be
equal to 2, and we get a bound of 2/3.
This is a pretty bad bound.
It is true, of course, but it is quite far
from the true answer.
Could we improve this bound?
In this particular example, we can.
Because of symmetry, we know that the probability of being
larger than or equal to 3 is equal to the probability of
being less than or equal to minus 3.
Or the probability of this event, which is the blue and
the green, is twice the probability of
just the blue event.
Or to put it differently, this probably here is equal to 1/2
of the probability that the absolute value of x is larger
than or equal to 3, and therefore, by using the same
bound as here, we will obtain and answer of 1/3.
So by being a little more clever and exploiting the
symmetry of this distribution around 0, we get a somewhat
better bound of 1/3, which is, again, a true bound.
It is more informative than the original bound, but still
it is quite far away from the true answer.