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

12

Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities

In this chapter, we give an introduction to the first of two recent approaches to concentration via powerful information-theoretic inequalities: the so-called transportation cost inequalities. These inequalities relate two different notions of “distance” between probability distributions and lead easily to concentration results. In this chapter, we prove such inequalities in the familiar and simple setting of the Hamming cube with the product measure, leading to an isoperimetric inequality that is essentially equivalent to the simple methods of bounded differences in many situations. Besides the intrinsic interest of this inequality, perhaps the main reason to ...

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