Talagrand showed that if $f$ is a convex $1$-Lipschitz function on $\mathbb{R}^n$, and if $\mu$ is a product of probability measures supported over the interval, then $f$ has Gaussian concentration w.r.t. to $\mu$:
$$
P(\vert f - E\_{\mu}f\vert > \epsilon) < C \exp(-c\epsilon^2)
$$
for some absolute constants $c$ and $C$.


I would like to understand to what extent convexity is necessary in the special case where $\mu$ is the uniform measure on the discrete hypercube $\{0,1\}^n$. What are "representative" counterexamples if convexity is not assumed? 



Talagrand's inequality for the discrete cube

> 
> there is no convexity assumption needed there.
> 
> 
> 


Nevertheless here is a counterexample of $1$-Lipschitz function on $\mathbb{R}^{N}$ which fails to satisfy concentration inequality on the Hamming cube $\{-1,1\}^{N}$ as $N$ goes to infinity. 


Take $N$ to be even. Let 
$$
A = \left\{ (x\_{1}, \ldots, x\_{N}) \in \{0,1\}^{N}\, : x\_{1}+\ldots+x\_{N}\leq \frac{N}{2}\right\}.
$$
Next, define a function 


$$
f(x) = \inf\_{y \in A} \| x-y\|\_{\mathbb{R}^{N}}
$$
Since $f$ is the distance function to a nonempty subset it follows that $f$ is $1$-Lipschitz (an exercise).


On the other hand notice that $f(x) = \sqrt{\max\{x\_{1}+\ldots+x\_{N} - \frac{N}{2},0\}}$ on $\{0,1\}^N$. Then as $N$ goes to infinity we have 
$$
\begin{aligned}
P(|f & -\mathbb{E}f| > N^{1/4}) \\ & = P\biggl(\biggl|\sqrt{\max\{\frac{(2x\_{1}-1)+\ldots+(2x\_{N}-1)}{\sqrt{N}},0\}} \\ & \qquad\qquad - \mathbb{E}\sqrt{\max\{\frac{(2x\_{1}-1)+\ldots+(2x\_{N}-1)}{\sqrt{N}},0\}} \biggr|>\sqrt{2} \biggr) \\ & \to P\left( | \sqrt{\max\{\xi, 0\}} - \mathbb{E} \sqrt{\max\{\xi, 0\}}|>\sqrt{2}\right)>10^{-10},
\end{aligned}
$$
where we used the central limit theorem, and $\xi$ is the standard normal Gaussian $\xi\in N(0,1)$. 


