Markov’s Inequality

While looking at Tao’s post on the law of large numbers, I claimed to Alap that Markov’s inequality was “obvious”. Asked to back that up, though, I couldn’t remember why it was obvious. Take some distribution p(x). For simplicity, assume this distribution is over the non-negative reals. Then, Markov’s inequality states, for \lambda > 0

P[x\geq\lambda] \leq \frac{E[x]}{\lambda}.

Though I find it more intuitive in the form

\lambda P[x \geq \lambda] \leq E[x].

Now, a proof is pretty trivial, basically by writing down the definitions of both sides.

E[x] = \int_{x\geq 0} x p(x) dx

\lambda P[x \geq \lambda] = \int_{x\geq\lambda} \lambda p(x) dx \leq \int_{x\geq\lambda} x p(x) dx

\leq \int_{x\geq 0} x p(x) dx

However, I think more intuition can be conveyed with pictures.

Matlab Code:

function markov_inequality

fsize = 16;
lambda = 5;

x = 0:.01:15;
p = .5*exp(-(x-3).^2) + exp(-(x-7).^2/4);
p=p/sum(p)*100;

figure(1)
plot(x,p,'k-','LineWidth',2)
xlim([min(x) max(x)])
ylim([0 max(x.*p)+.25])
legend('p(x)');
set(gca,'FontSize',fsize)

figure(2)
plot(x,p.*x,'k-','LineWidth',2);
xlim([min(x) max(x)])
ylim([0 max(x.*p)+.25])
legend('x p(x)');
set(gca,'FontSize',fsize)

figure(3)
plot(x,p.*x,'k-',x,p.*lambda,'r-','LineWidth',2);
xlim([min(x) max(x)])
ylim([0 max(x.*p)+.25])
hold on;
legend('x p(x)', '\lambda p(x)');
title('\lambda=5');
set(gca,'FontSize',fsize)

figure(4)
area(x,x.*p,'FaceColor',[.7 .7 .7],'LineWidth',2)
hold on;
good = find(x>=lambda);
area(x(good),p(good)*lambda,'FaceColor',[.8 0 0],'LineWidth',2)
hold off
legend('E[x]','\lambda P[x \geq \lambda]')
xlim([min(x) max(x)])
ylim([0 max(x.*p)+.25])
set(gca,'FontSize',fsize)

end
About these ads
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

One Response to Markov’s Inequality

  1. Elazar Newman says:

    Excellent.This is first time I have seen an intuitive explanation of Markov’s inequality.

    Well done!

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