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
    Hello,

    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]

    where

    [tex]\Phi(s)=\left(1-\varepsilon(1-e^s)\right)^N[/tex]

    and

    [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?

    Thanks
     
  2. jcsd
  3. Jul 31, 2015 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

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




Similar Discussions: Chernoff Bound for Binomial Distribution
  1. Chernoff Bounds (Replies: 2)

  2. Binomial distribution (Replies: 1)

Loading...