Theorem. Effron-Stein Inequailty.
\[ \mathop{\mathrm{\text{Var}}}[F] \le \frac{1}{2} \sum_{i=1}^{n} \mathop{\mathrm{\mathbb{E}}}_{X_1,X_2,\ldots, X_n, X_i'}(F(X_1,\ldots, X_i, \ldots, X_n) -F(X_1,\ldots, X_i', \ldots, X_n))^2 \]
Proof. We can prove a weaker version (just drop the \(1/2\)) by induction on \(n\). The formula reduces to Jensen’s Inequality if you set \(n=1\).
Now, lets try to do \(n=2\). The extension from \(n\) to \(n+1\) should just follow the same pattern.
It turns out that you can prove the inequality point-wise. I.e., fix \(Y\) and condition on it. You do some algebra and apply Cauchy-Shwarz and/or Jensens and it works.
Example. You can use this to show that MAXCUT of a random graph concentrates. weird rmk: we don’t actually know what it concentrates around! Of course it is \(\Theta(n)\) [the setting is \(G(n,d/n)\) for constant \(d\) ]. But the precise value is an open question.
Theorem. Azuma-Hoeffding Bound
Suppose you have a martingale with almost surely bounded differences, namely, \(|X_k-X_{k-1}|\le d_k\).
Then we have \[ \Pr[|X-\mathop{\mathrm{\mathbb{E}}}X| > t] \le 2\exp( \frac{-t^2}{2\sum d_k^2}. ) \]
In the special case where the increment bounds \(d_k\) are all the same this is
\[ \Pr[|X-\mathop{\mathrm{\mathbb{E}}}X| > t] \le 2\exp( \frac{-t^2}{2nd^2}. ) \]
Proof.
As always we do the Chernoff trick: Markov the exponential MGF. We bound the exponential MGF by some convexity argument that works using the boundedness of the increments.
Corollary. McDiarmid’s Inequality
Suppose \(F(X_1,\ldots, X_n)\), where $X_1,, $ are iid, is lipschitz: i.e., if you mess with a few coordinates you don’t mess with it v much.
Then we also get a chernoff-like tail bound concentration thing.
For instance, if messing with one variable can change the value by at most \(d\) then we have
\[ \Pr[|F(X_1,\ldots, X_n) - \mathop{\mathrm{\mathbb{E}}}F| > t] \le 2\exp( \frac{-2t^2}{nd^2} ). \]
Proof. This is actually the special case of Azuma Hoeffding applied to the Doob Martingale defined by sequentially revealing more information about the variables feeding into \(F\).