Paper detail

Remarks on Talagrand's deviation inequality for Rademacher functions

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 ^n_2$; namely, he proved that $$P(|f-M_f| > c) \le 4 e^{-t^2/4σ^2}$$ where $σ$ 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-η)δ_0 + ηδ_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 $\varepsilon$) of the Bourgain, Lindenstrauss, Milman result [BLM] that for $1\le r < s \le 2$ and $\varepsilon >0$, every $n$-dimensional subspace of $L_s \ (1+\varepsilon)$-embeds into $\ell ^N_r$ with $N = c(r,s,\varepsilon)n$.