Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Chernoff Bound for Binomial Distribution

  1. Jul 31, 2015 #1

    I've read in a paper that the following binomial distribution

    [tex]\sum_{k=floor(N/2)+1}^N{N\choose k}\varepsilon^k(1-\varepsilon)^{N-k}[/tex]

    can be upper bounded using Chernoff bound by

    [tex]e^{ floor(N/2)}\,\Phi(s_0)[/tex]




    [tex]floor(N/2)\,\Phi(s_0)=\frac{\partial}{\partial s}\left. \Phi(s)\right|_{s=s_0}[/tex]

    Could anyone explain to me how?

  2. jcsd
  3. Jul 31, 2015 #2


    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Chernoff Bound Binomial Date
I Divisibility of bounded interval of reals Feb 1, 2018
I Upper bound and supremum problem Apr 12, 2017
Bounding a truncated normal with a gamma Feb 20, 2016
Chernoff Bounds Feb 18, 2009
Applying Chernoff bound on normal distribution Dec 25, 2006