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.

Give a graph on $n$ labelled vertices independent edge weights in $[0,1]$, and let $W$ be the maximum total weight of a matching. Put each edge into the block of its lower-numbered endpoint. There are at most $n-1$ independent blocks. Every matching uses at most one edge from any block, since the block's edges share that endpoint. Changing a whole block therefore changes the weight of each fixed matching by at most one. Comparing the old and new maximizing matchings shows the same bound for $W$.

The Doob exposure martingale for these blocks has increments bounded by one, so Azuma's inequality givesThe important feature is grouping independent edge coordinates into vertex-centred blocks. Exposing all edges separately would give a weaker denominator of order $n^2$ on a dense graph. Identical distributions are unnecessary; independence and the common range bound suffice.

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.