Results 1 to 3 of 3

Math Help - Probability problem: upper bounds on binomial CDF using Chernoff

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    USA
    Posts
    4

    Question 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, X \sim \operatorname{Bin}(m,p) where p=2^{-\sqrt{\log n}}(\log n)^2 and m \geq  2^{\sqrt{\log n}}c for constants c, n (n "large" here). I wish to show that \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 \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 \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 (*) 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
    Last edited by simba31415; March 13th 2012 at 07:18 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2012
    From
    USA
    Posts
    4

    Unhappy 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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2012
    From
    USA
    Posts
    4

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of a problem concerning least upper bounds
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: August 22nd 2011, 09:25 AM
  2. Least Upper Bounds
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 3rd 2010, 06:15 PM
  3. least upper bounds!
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 10th 2008, 12:41 PM
  4. Greatest lower bounds and least upper bounds
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 31st 2008, 06:31 PM
  5. more help upper bounds
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 14th 2006, 08:00 PM

Search Tags


/mathhelpforum @mathhelpforum