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

7

The Method of Averaged Bounded Differences

Sometimes, the function f for which we are trying to show a concentration result does not satisfy the conditions needed to apply the simple method of bounded differences: the Lipschitz coefficients are simply too large in the worst case. The function is not “smooth”. In such cases, the method of average bounded differences can be deployed, needing only an averaged smoothness condition. That is, we need a bound of the form

image

(7.1)

or the similar

image

(7.2)

At first glance, getting a handle ...

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