**2**

**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 ...

Start Free Trial

No credit card required