Chebyshev's inequality

Suppose X is a random variable with mean

\mu

and variance

\sigma^2

. Show that:

\displaystyle P(X-\mu \geq k ) = P(X-\mu + a \geq k + a) \leq \frac{\sigma^2 + a^2}{(k+a)^2}

for positive a and k. Deduce that for k > 0,

\displaystyle P(X-\mu \geq k ) \leq \frac{\sigma^2 }{\sigma^2 + k^2}

================================

First bit done with no problems using Chebyshev's inequality. I have spent hours trying to deduce the second bit from a combination of Markov's inequality and Chebyshev, substituting lots of different things for 'a' in the first line, even taking the cases k<1 and k>1 separately (so far I've shown it's true for k<1... great :frown:

).

It seems like it's supposed to be a simple step; am I missing something?

Reply 1

ghostwalker

Dream Eater

\displaystyle \frac{\sigma^2 + a^2}{(k+a)^2}

Like most uni. maths, I am way too rusty.

But, if this is true for all a > 0, then consider quoted item as a function of a, and find when it's a minimum.

Reply 2

M. E-S.

Chebyshev's inequality states that

.

As a general rule, for any positive value of k, the following inequality holds:

.

Moreover, you are operating a translation of the random variable, which means that all of its values (and, consequently, its mean value) will be shifted by a constant a>0. This is not a problem, since

.

By virtue of these observations:

.

Choosing a=sigma the thesis follows.

L

Reply 3

Dream Eater

M. E-S.

Chebyshev's inequality states that

.

As a general rule, for any positive value of k, the following inequality holds:

.

By virtue of these observations:

.

Choosing a=sigma the thesis follows.

L

Wow, it works! The annoying thing seems to be that you get a different result depending on which version of Chebyshev you use after the translation 'k + a'. But this is very clear and precise; thanks for clearing up the confusing modulus business too! :smile:

Reply 4

ghostwalker

Dream Eater

But this is very clear and precise.

Can you explain to me the justification for the final inequality? I follow everything up to there, but can't see how the final inequality follows given the previous lines and Chebyshev's inequality. Or if you can point me to a webpage. If you have time, thanks.

Reply 5

M. E-S.

Final inequality:

Pr(|X-\mu+a|\geq\frac{k+a}{\sigma} \sigma)\leq\frac{\sigma ^2}{(k+a)^2}

.

If, for a generic

\theta>0

, we assume the following form of the Chebychev's inequality to hold

Pr(|X-\mu|\geq \theta\sigma)\leq 1/\theta^2

,

then choosing

\theta=\frac{k+a}{\sigma}

will lead to the aforementioned final inequality.

Finally, the thesis requested in the opening post will follow from the choice

a=\sigma

Pr(|X-\mu+\sigma|\geq\frac{k+\sigma}{\sigma} \sigma)\leq\frac{\sigma ^2}{(k+\sigma)^2}=\frac{\sigma^2}{k^2+\sigma^2+2k \sigma}\leq\frac{\sigma^2}{k^2+\sigma^2}

Hope I answered your question.

L

Reply 6

ghostwalker

M. E-S.

Final inequality:

Pr(|X-\mu+a|\geq\frac{k+a}{\sigma} \sigma)\leq\frac{\sigma ^2}{(k+a)^2}

.

If, for a generic

\theta>0

, we assume the following form of the Chebychev's inequality to hold

Pr(|X-\mu|\geq \theta\sigma)\leq 1/\theta^2

,

then choosing

\theta=\frac{k+a}{\sigma}

will lead to the aforementioned final inequality.

Thanks for your reply.

Sorry, but I'm missing some connection I think.

I can see that choosing

\theta=\frac{k+a}{\sigma}

we would have

Pr(|X-\mu|\geq k+a)\leq\frac{\sigma ^2}{(k+a)^2}

.

But not:

Pr(|X-\mu+a|\geq k+a)\leq\frac{\sigma ^2}{(k+a)^2}

.

I may be missing an elementary result, as I'm not overly familiar with the area.

Reply 7

M. E-S.

ghostwalker

But not:

Pr(|X-\mu+a|\geq k+a)\leq\frac{\sigma ^2}{(k+a)^2}

I TOTALLY AGREE.

Not only will I embark on a public mea culpa, but I will try to provide a possible correction.

Pr(X-\mu\geq k)\leq Pr(X-\mu\geq k+\sigma) \leq Pr(|X-\mu|\geq k+\sigma).

from this point one can use Chebychev's inequality.

Sorry for my previous mistake (hopefully I didn't make any, this time).

Thanks!

L

Reply 8

ghostwalker

M. E-S.

I TOTALLY AGREE.

Not only will I embark on a public mea culpa, but I will try to provide a possible correction.

Pr(X-\mu\geq k)\leq Pr(X-\mu\geq k+\sigma) \leq Pr(|X-\mu|\geq k+\sigma).

from this point one can use Chebychev's inequality.

Sorry for my previous mistake (hopefully I didn't make any, this time).

Thanks!

L

Thanks for the update. I do feel obliged to point out though

Pr(X-\mu\geq k)\geq Pr(X-\mu\geq k+\sigma)

Sorry.

Reply 9

Dream Eater

ghostwalker

Thanks for the update. I do feel obliged to point out though

Pr(X-\mu\geq k)\geq Pr(X-\mu\geq k+\sigma)

Sorry.

I used M. E-S.'s working above but I altered it a bit to fit with my own understanding and the definitions I was using (which, I'm hoping, are fairly universal). At least this gives me a chance to check if my method is convincing! My observations are mostly the same, with just a slightly different version of Chebyshev:

\mathrm{Observation\ 1:\ } \displaystyle P(X \geq k ) \leq P (|X| \geq k),\mathrm{\ for\ k > 0}

\mathrm{Observation\ 2\ (Chebyshev):\ } \displaystyle P(|X-\mu| \geq k) \leq \frac{\mathrm{var}(X)}{k^2}

\displaystyle P(X - \mu \geq k) = P(X - \mu + a \geq k + a) \leq P(| (X + a) - \mu | \geq k + a) \leq \frac{\mathrm{var} (X+a)}{(k+a)^2} = \frac{\mathrm{var} (X)}{(k+a)^2}

Hence giving the

\frac{\sigma^2}{(k+a)^2}

we were looking for.

EDIT: Just thought I'd mention to ghostwalker that I did in fact try that cool idea of finding the 'a' that minimizes the first function way up the first post, and unfortunately it didn't quite get there :frown:

. The minimum a was

\frac{\sigma^2}{2k}

which didn't give the final inequality whichever way you looked at it. Shame as it was an elegant idea...

Reply 10

ghostwalker

Dream Eater

\displaystyle P(| (X + a) - \mu | \geq k + a) \leq \frac{\mathrm{var} (X+a)}{(k+a)^2}

Thanks, BUT how do you justify the quoted part, since

\mu

is not the mean/expectation of

X+a

EDIT: Just thought I'd mention to ghostwalker that I did in fact try that cool idea of finding the 'a' that minimizes the first function way up the first post, and unfortunately it didn't quite get there . The minimum a was which didn't give the final inequality whichever way you looked at it. Shame as it was an elegant idea...

I got

a=\frac{\sigma^2}{k}

and it worked out. :confused:

Reply 11

Dream Eater

ghostwalker

Thanks, BUT how do you justify the quoted part, since

\mu

is not the mean/expectation of

X+a

Good point...

I got

a=\frac{\sigma^2}{k}

and it worked out. :confused:

AAAAAAAAHHHHHHHHHHHHHHH!!!!!!! I just worked it through, and I'd miscopied my working from a previous page skipping a 2! :eek3:

Okay, you've been right from the beginning and deserve about a billion reps..

Reply 12

ghostwalker

Dream Eater

Good point...

AAAAAAAAHHHHHHHHHHHHHHH!!!!!!! I just worked it through, and I'd miscopied my working from a previous page skipping a 2! :eek3:

Okay, you've been right from the beginning and deserve about a billion reps..

Warm feeling of satisfaction! (and relief) lol.

PS: Thanks for the billion reps; for some reason, they left the one off the front and it came through as zero, but appreciated anyway.

Edit: I would still be interested if the other method was workable.

Reply 13

Dream Eater

ghostwalker

Warm feeling of satisfaction! lol.

PS: Thanks for the billion reps; for some reason, they left the one off the front and it came through as zero, but appreciated anyway.

Edit: I would still be interested if the other method was workable.

I accidentally repped without leaving a comment... yes, because my post count is below 150 they don't count for much yet, unfortunately. Expect more reps when they do! :biggrin:

I have a 'to rep' list and I don't forget those that go out of their way to lend a hand!

Yeah I would too but I think there's an impasse. I've seen this problem appear in places other than the worksheet I was doing and I get the feeling from the wording that your method is probably the easiest/the intended one.