(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Hi all, just a quick question here - the setup is as follows: X is a random variable, [itex]X \sim \operatorname{Bin}(m,p)[/itex] where [itex]p=2^{-\sqrt{\log n}}(\log n)^2[/itex] and [itex]m \geq 2^{\sqrt{\log n}}c[/itex] for constants c, n (n "large" here). I wish to show that [itex]\mathbb{P}(X < c) \leq e^{-(\log n)^2 c/3}[/itex]. 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 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'm told observing the fact that [itex]\mu = \mathbb{E}(X) \geq (\log n)^2 c = \mu '[/itex] should also help, so I suspect maybe what we really need is to show is [itex]\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}[/itex] but as I said, no luck so far since I can't prove step [itex](*)[/itex] 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! -S

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Probability problem: upper bounds on binomial CDF

**Physics Forums | Science Articles, Homework Help, Discussion**