# Probability problem: upper bounds on binomial CDF using Chernoff

• Mar 13th 2012, 07:16 PM
simba31415
Probability problem: upper bounds on binomial CDF using Chernoff
Hi all, just a quick question here - the setup is as follows: X is a random variable, $\displaystyle X \sim \operatorname{Bin}(m,p)$ where $\displaystyle p=2^{-\sqrt{\log n}}(\log n)^2$ and $\displaystyle m \geq 2^{\sqrt{\log n}}c$ for constants c, n (n "large" here). I wish to show that $\displaystyle \mathbb{P}(X < c) \leq e^{-(\log n)^2 c/3}$. I've been told to use "Chernoff-esque bounds" here; however, after teaching myself a little about Chernoff bounds I haven't found a way to make this work - I know conceptually they're used to get upper bounds on the probability of 'tail events', and I can see that the multiplicative form could be useful but I haven't yet figured out how to translate the bounds which I've found online into a workable form for this problem (I've never used Chernoff bounds before!).

I'm told observing the fact that $\displaystyle \mu = \mathbb{E}(X) \geq (\log n)^2 c = \mu '$ might also help, so I suspect maybe what we really need is to show is $\displaystyle \mathbb{P}(X < c) = \mathbb{P}(X < \frac{\mu'}{(\log n) ^2}) < \mathbb{P}(X < \frac{\mu}{(\log n) ^2}) \leq ^{(*)} e^{- \mu / 3} \leq e^{-\mu ' /3}$ but as I said, no luck so far since I can't prove step $\displaystyle (*)$ if indeed that is the way to do it. I suspect that this result only needs a few lines of work once you have the bound you require from Chernoff, so if anyone could show me how to do this I'd be very grateful! -Sim
• Mar 14th 2012, 03:46 PM
simba31415
Re: Probability problem: upper bounds on binomial CDF using Chernoff
Sorry to bump, but I've been trying to solve this problem for ages now and I'm not getting anywhere. If anyone has any thoughts, any at all, then please respond and let me know, I'd be extremely grateful!
• Mar 31st 2012, 07:16 PM
simba31415
Re: Probability problem: upper bounds on binomial CDF using Chernoff
Could a mod please delete this thread for me? That'd be much appreciated, thank you.