Hello,(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums - The Fusion of Science and Community**

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

# Chernoff Bound for Binomial Distribution

Loading...

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 |

**Physics Forums - The Fusion of Science and Community**