Editing Chernoff bound (section)

==Applications==
Chernoff bounds have very useful applications in [[set balancing]] and [[Packet (information technology)|packet]] [[routing]] in [[sparse graph|sparse]] networks.

The set balancing problem arises while designing statistical experiments. Typically while designing a statistical experiment, given the features of each participant in the experiment, we need to know how to divide the participants into 2 disjoint groups such that each feature is roughly as balanced as possible between the two groups.<ref name="0bAYl6d7hvkC">Refer to this [https://books.google.com/books?id=0bAYl6d7hvkC&pg=PA71 book section] for more info on the problem.</ref>

Chernoff bounds are also used to obtain tight bounds for permutation routing problems which reduce [[network congestion]] while routing packets in sparse networks.<ref name="0bAYl6d7hvkC" />

Chernoff bounds are used in [[computational learning theory]] to prove that a learning algorithm is [[Probably approximately correct learning|probably approximately correct]], i.e. with high probability the algorithm has small error on a sufficiently large training data set.<ref>{{cite book |first1=M. |last1=Kearns |first2=U. |last2=Vazirani |title=An Introduction to Computational Learning Theory |at=Chapter 9 (Appendix), pages 190–192 |publisher=MIT Press |year=1994 |isbn=0-262-11193-4 }}</ref>

Chernoff bounds can be effectively used to evaluate the "robustness level" of an application/algorithm by exploring its perturbation space with randomization.<ref name="Alippi2014">{{cite book |first=C. |last=Alippi |chapter=Randomized Algorithms |title=Intelligence for Embedded Systems |publisher=Springer |year=2014 |isbn=978-3-319-05278-6 }}</ref>
The use of the Chernoff bound permits one to abandon the strong—and mostly unrealistic—small perturbation hypothesis (the perturbation magnitude is small). The robustness level can be, in turn, used either to validate or reject a specific algorithmic choice, a hardware implementation or the appropriateness of a solution whose structural parameters are affected by uncertainties.

A simple and common use of Chernoff bounds is for "boosting" of [[randomized algorithm]]s. If one has an algorithm that outputs a guess that is the desired answer with probability ''p'' > 1/2, then one can get a higher success rate by running the algorithm <math>n = \log(1/\delta) 2p/(p - 1/2)^2</math> times and outputting a guess that is output by more than ''n''/2 runs of the algorithm. (There cannot be more than one such guess.) Assuming that these algorithm runs are independent, the probability that more than ''n''/2 of the guesses is correct is equal to the probability that the sum of independent Bernoulli random variables {{math|''X<sub>k</sub>''}} that are 1 with probability ''p'' is more than ''n''/2. This can be shown to be at least <math>1-\delta</math> via the multiplicative Chernoff bound (Corollary 13.3 in Sinclair's class notes, {{math|''μ'' {{=}} ''np''}}).:<ref>{{Cite web|url = http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|title = Class notes for the course "Randomness and Computation"|date = Fall 2011|access-date = 30 October 2014|last = Sinclair|first = Alistair|archive-url = https://web.archive.org/web/20141031035717/http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|archive-date = 31 October 2014|url-status = dead}}</ref>

:<math>\Pr\left[X > {n \over 2}\right] \ge 1 - e^{-n \left(p - 1/2 \right)^2/(2p)} \geq 1-\delta</math>