# Talagrand's inequality for L1 norm

I have a series of $$n$$ independent random variables $$X_1,\ldots, X_n$$, each with the support $$[0,1]$$, and a monotone convex function $$f:\mathbb{R}^n \rightarrow \mathbb{R}$$ that is 1-Lipshitz in L1 norm, i.e., for every $$x,y \in \mathbb{R}^n$$, it holds that $$f(x)-f(y) \leq \sum_{i=1}^{n} |x_i-y_i|$$. I want to have a concentration bound like Talagrand.

Is it true that $$Pr[ \mid f(X_1,\ldots,X_n) - E[f(X_1,\ldots,X_n)] \mid > t] \leq c_1 \cdot e^{-\frac{t^2}{c_2}}$$ for some constants $$c_1,c_2>0$$ (that are independent of $$n$$, and the distributions of $$X_i$$, and the function $$f$$, as long as the conditions hold)?

Do I need more conditions for the inequality to hold?

Yes, you do need more conditions. For instance, if $$f(x_1,\dots,x_n)\equiv x_1+\dots+x_n$$ and the $$X_i$$'s are (say) iid Bernoulli with parameter $$1/2$$, then $$f$$ is $$1$$-Lipschitz in the $$L^1$$-norm but, by the central limit theorem, your inequality will hold for all real $$t>0$$ only if $$c_2\gtrsim n/2$$ as $$n\to\infty$$.
• @TomerEzra : Here is the logic: If your inequality is not true for a specific $1$-Lipschitz $f$, then it cannot be true for all $1$-Lipschitz $f$, right? (But, of course, it is true indeed for some $1$-Lipschitz $f$, say for $f=0$.) Apr 7, 2022 at 13:38