1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
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

  1. Mar 6, 2012 #1
    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
  2. jcsd
  3. Mar 7, 2012 #2
    No thoughts anyone? Sorry to bump but I could really use some help with this, any thoughts at all please respond!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook