Blog posts

2017

Chernoff Bound

Published:

For $i=1,..,n$, let $X_i$ be independent random variables that take the value 1 with probability $p_i$ and 0 otherwise. Suppose at least one of the $p_i$ is nonzero. Let $X=\sum\limits_{i=1}^N{X_i}$, and let $\mu = E[X] = \sum\limits_{i=1}^N{p_i}$