O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required