## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required