Remarks on Talagrand's deviation inequality for Rademacher functions

Abstract

Recently Talagrand [T] estimated the deviation of a function on $\{0,1{\}}^n$ from its median in terms of the Lipschitz constant of a convex extension of $f$ to ${\ell }_2^n$; namely, he proved that $$P(|f-M_f|>c)\le 4e^{-t^2/4{\sigma }^2}$$ where $\sigma$ is the Lipschitz constant of the extension of $f$ and $P$ is the natural probability on $\{0,1{\}}^n$. Here we extend this inequality to more general product probability spaces; in particular, we prove the same inequality for $\{0,1{\}}^n$ with the product measure $((1-\eta ){\delta }_0+\eta {\delta }_1{)}^n$. We believe this should be useful in proofs involving random selections. As an illustration of possible applications we give a simple proof (though not with the right dependence on $\epsilon$) of the Bourgain, Lindenstrauss, Milman result [BLM] that for $1\le r<s\le 2$ and $\epsilon >0$, every $n$-dimensional subspace of $L_s(1+\epsilon )$-embeds into ${\ell }_r^N$ with $N=c(r,s,\epsilon )n$.