similar proof strategy can be used to show that The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used, which follow from the inequality from the list of logarithmic inequalities: Notice that the bounds are trivial for . Additive form (absolute error) The following theorem is due to Wassily Hoeffding and hence is called the Chernoff–Hoeffding theorem. Chernoff–Hoeffding theorem. Suppose are i.i.d. random variables, taking values in Let and . where is the Kullback–Leibler divergence between Bernoulli distributed random variables with parameters x and y respectively. If then which means A simpler bound follows by relaxing the theorem using , which follows from the convexity of and the fact that This result is a special case of Hoeffding's inequality. Sometimes, the bounds which are stronger for are also used. Applications Chernoff bounds have very useful applications in set balancing and packet routing in 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. Chernoff bounds are also used to obtain tight bounds for permutation routing problems which reduce network congestion while routing packets in sparse networks. Chernoff bounds are used in computational learning theory to prove that a learning algorithm is probably approximately correct, i.e. with high probability the algorithm has small error on a sufficiently large training data set. Chernoff bounds can be effectively used to evaluate the "robustness level" of an application/algorithm by exploring its perturbation space with randomization. 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 algorithms. 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 times and outputting a guess that is output by more than n/2 runs of the algorithm. (There cannot