Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have some random variable with an expected value of $n/8$. I want to use Chernoff bounds to show that with some high probability, the actual value is at least $(1 - \epsilon)n/24$. How could I go about this?

share|improve this question
1  
It's not really the Chernoff bound that applies here but Markov's inequality (en.wikipedia.org/wiki/Markov_inequality). The Chernoff bound is for a sum of independent random variables. –  Akhil Mathew Apr 11 '11 at 17:51
    
He never said that the r.v. is non-negative. In any case, to apply Markov here you need an upper bound. –  Yuval Filmus Apr 11 '11 at 19:00
    
Please see my answer to math.stackexchange.com/questions/32457/…. It's about the same, with different numbers. You do need to know, however, that your random variable is a sum of 0/1 Poisson trials which are either independent or negatively correlated. –  leif Apr 12 '11 at 5:50
    
I would advise some caution when using the answer leif refers to, for reasons explained in the comments. –  Did Apr 12 '11 at 13:07

1 Answer 1

The result isn't true. Take the random variable which is $0$ w.p. $1-\epsilon$ and $n/8\epsilon$ w.p. $\epsilon$. Its expectation is $n/8$ yet it is not concentrated at all around its expectation.

In order to use a concentration bound you need to know more about your random variable, e.g. its variance (then you can use Chebyshev), boundedness (then you can use Markov) or it being a sum of a lot of "small" variables (then you can use Chernoff).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.