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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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).