Talagrand’s Inductive Method and Isoperimetric Inequalities Involving Random Sets

Abstract

Talagrand’s isoperimetric inequality is extended to the case for which the distance from a random vector with independent components is measured not to a subset of a product space but instead to a (finite) set of random vectors assuming values in that product space. This extension is realized in particular for a general class of distances that we show includes the Hamming distance as well as Talagrand’s own convex distance. We then apply our new inequality to prove certain new exponential inequalities featuring the product of expectations of expressions involving the Hamming distances between members of pairs of random vectors satisfying suitable independence conditions.