= Talagrand's one-sided bounded differences inequality
{c}
A useful precise version of <Talagrand's one-sided bounded differences inequality> assumes that <independent random variables> $X_i$ enter a <measurable> <function> $f$ for which there are nonnegative coordinate weights $c_i(x)$ satisfying the \i[global] comparison
$$
f(x)-f(y)\leq\sum_i c_i(x)\mathbf1_{\{x_i\ne y_i\}}\qquad\text{for every }x,y.
$$
Put $Z=f(X)$ and $V=\mathbb E\sum_i c_i(X)^2$. When $0<V<\infty$ and $Z$ is <integrable>,
$$
\mathbb P(Z\leq\mathbb EZ-t)\leq\exp[-t^2/(2V)],\qquad t\geq0.
$$
The global comparison is stronger than bounding separate coordinate changes at one input. This distinction matters for a lower tail.<Probability in High Dimension by Ramon van Handel>[Theorem 4.20 and Remark 4.25]{ref}
For a differentiable <convex function> on $[0,1]^n$, the supporting-gradient inequality verifies the comparison with $c_i(x)=|\partial_i f(x)|$. Thus $V=\mathbb E\lVert\nabla f(X)\rVert^2$ controls the lower tail. Applying the theorem to the negative of a <concave function> gives its upper tail. For example, $f(x)=\sum_i x_i$ has $V=n$, giving $e^{-t^2/(2n)}$ as a valid, though conservative, lower-tail bound.
Back to article page
