Applications of the Chernoff–Hoeffding Bounds
In this chapter we present some non-trivial applications of the Chernoff– Hoeffding bounds arising in the design and analysis of randomized algorithms. The examples are quite different, a fact that illustrates the usefulness of these bounds.
2.1 Probabilistic Amplification
The following situation is quite common. We have a probabilistic algorithm that on input x, computes the correct answer f(x) with probability strictly greater than 1/2. For concreteness, let us assume that the success probability is p ≥ 3/4 and that the algorithm has two possible outcomes, 0 and 1. To boost our confidence we run the algorithm n times and select the majority answer. What is the probability that this procedure is ...