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?
Chernoff bounds on a random variable
0
$\begingroup$
probability
-
1It's not really the Chernoff bound that applies here but Markov's inequality (http://en.wikipedia.org/wiki/Markov_inequality). The Chernoff bound is for a sum of independent random variables. – 2011-04-11
-
0He never said that the r.v. is non-negative. In any case, to apply Markov here you need an *upper* bound. – 2011-04-11
-
0Please see my answer to http://math.stackexchange.com/questions/32457/reviewing-for-exam-chernoff-bounds-for-a-series-of-random-variables. 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. – 2011-04-12
-
0I would advise some caution when using the answer leif refers to, for reasons explained in the comments. – 2011-04-12