= Solution
Expose the independent coordinates in order and let $M_i=\mathbb E[f\mid X_1,\ldots,X_i]$, $M_0=\mathbb Ef$. This is the <Doob exposure martingale>. For fixed earlier coordinates, write $h_i(x)=\mathbb E[f\mid X_i=x,\text{earlier coordinates}]$. The remaining coordinates have the same distribution for all $x$, and the coordinate-change hypothesis gives $|h_i(x)-h_i(y)|\leq c_i$. Thus the conditional range of $M_i-M_{i-1}$ has length at most $c_i$, and its conditional mean is zero.
Here is the <Hoeffding lemma> needed for the sharp constant. If a mean-zero <random variable> $Y$ lies in an interval of length $c$, <set> $\psi(s)=\log\mathbb Ee^{sY}$. Its second derivative is the <variance> under the exponentially tilted law. Under any such law, <variance> is at most $c^2/4$, by comparison with squared distance from the interval midpoint. Since $\psi(0)=\psi'(0)=0$, integration gives $\psi(s)\leq s^2c^2/8$ for all real $s$. Applying this conditionally and iterating the tower property yields
$$
\mathbb Ee^{s(f-\mathbb Ef)}\leq
\exp\left(\frac{s^2}{8}\sum_i c_i^2\right).
$$
The <exponential Markov bound> now gives
$$
\Pr(f-\mathbb Ef\geq t)
\leq\exp\left(-st+\frac{s^2C}{8}\right),
\qquad C=\sum_i c_i^2.
$$
For $C>0$ choose $s=4t/C$. Apply the same argument to $-f$ and add the two tails, proving the <McDiarmid inequality>
$$
\boxed{\Pr(|f-\mathbb Ef|\geq t)\leq2e^{-2t^2/C}.}
$$
For $C=0$, $f$ is constant almost surely, and every positive-deviation <probability> is zero.
For the neighbourhood application, the ambient points must be elements of $\mathcal P[n]$, equivalently binary strings; the printed $y\in[n]$ is a type error. An $n$-element ambient <set> could not generally satisfy the stated exponential-size lower bound. Use the uniform <product probability space> on the <Boolean cube> and <set> $F(y)=d(y,A)$. Flipping one coordinate changes this <Hamming distance> by at most one, so $C=n$. Put $\mu=\mathbb EF$. Since $\Pr(F=0)=|A|/2^n\geq\varepsilon$, the proved two-sided inequality gives, for $\mu>0$,
$$
\varepsilon\leq\Pr(|F-\mu|\geq\mu)
\leq2e^{-2\mu^2/n}.
$$
Consequently $\mu\leq\sqrt{(n/2)\log(2/\varepsilon)}=t/2$; the same bound is immediate if $\mu=0$. Therefore
$$
\Pr(F>t)\leq\Pr(|F-\mu|\geq t-\mu)
\leq2e^{-2(t-\mu)^2/n}\leq2e^{-t^2/(2n)}=\varepsilon.
$$
This proves the <Boolean cube expansion from bounded differences>:
$$
\boxed{|A_t|\geq(1-\varepsilon)2^n.}
$$
The meaningful range is $0<\varepsilon\leq1$; real radii are interpreted by the inequality on the integer-valued <Hamming distance>. The converted TeX's final $2^{2n}$ is another corruption: the original PDF has $2^n$.
Back to article page
