Bounded differences property

A function $f(x_1,\dots ,x_n)$ has bounded differences with constants $c_i$ when changing only $x_i$ changes its value by at most $c_i$.

If $X_1,\dots ,X_n$ are independent random variables and $f$ has bounded differences constants $c_i$, thenand the same bound holds for the lower tail.

For a nonempty $A\subseteq \{0,1{\}}^n$ of relative size at least $\epsilon \in (0,1]$, its Hamming distance function $F(x)=d(x,A)$ has the bounded differences property with all constants one. If $\mu =\mathbb{E}F$, the concentration bound at $F=0$ gives $\epsilon \le 2e^{-2{\mu }^2/n}$, so $\mu \le t/2$ for $t=\sqrt{2n\log (2/\epsilon )}$. Then $\mathrm{Pr}(F>t)\le 2e^{-2(t-\mu {)}^2/n}\le \epsilon$, proving that the radius-$t$ neighbourhood contains at least $(1-\epsilon )2^n$ cube points.

If a function of independent coordinates has one-sided squared-difference proxy at most $v$, Talagrand's one-sided inequality gives a Gaussian lower-tail bound $\mathbb{P}(Z-\mathbb{E}Z\le -t)\le e^{-t^2/(2v)}$. Applied to the negative of a concave function, it gives the corresponding upper-tail bound.