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

9

Interlude: The Infamous Upper Tail

9.1 Motivation: Non-Lipschitz Functions

Consider the random graph G(n, p) with p = p(n) = n−3/4. Let X be the number of triangles in this graph. We have image. The random variable X is a function of the image independent variables corresponding to whether a particular edge is present or not. Changing any of these variables could change the value of X by as much as n − 2 in the worst case. Applying the method of bounded differences with these Lipschitz coefficients is useless to obtain a non-trivial concentration result ...

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