Efron-Stein inequality

Let $X_1,\dots ,X_n$ be independent random variables and let $f:{\mathcal{X}}^n\to \mathbb{R}$ obey $\mathbb{E}[f^2(X)]<\infty$ where $X=(X_1,\dots ,X_n)$. The Efron-Stein inequality states that

$$\mathbb{V}(f(X))\le \sum _{i=1}^n\mathbb{E}[(f(X)-\mathbb{E}[f(X)|X^{(i)}]{)}^2]=:v,$$

The Efron-Stein inequality is a fundamental result for bounding the variance of functions of random variables. It implies various other results such as bounded difference inequalities (though sometimes not the strongest versions).

We can write $v$ in several different ways. First we can write it as a function of $f$ acting on iid copies:

$$v=\frac{1}{2}\sum _{i=1}^n\mathbb{E}[(f(X)-f({\mathbf{X}}_i^{\prime }){)}^2],$$

where ${\mathbf{X}}_i^{\prime }=(X_1,\dots ,X_{i-1},X_i^{\prime },X_{i+1},\dots ,X_n)$ and $X_i^{\prime }$ is an iid copy of $X_i$. Next we can write it as

$$v=\underset{Z_1,\dots ,Z_n}{\inf }\sum _{i=1}\mathbb{E}[(f(X)-Z_i{)}^2],$$

where $Z_i$ is $(X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n)$-measurable (i.e., the only randomness comes from $X_i$).

Efron-Stein inequalities also exist for random matrices, see here.

References

• An Efron-Stein inequality for nonsymmetric statistics by Steele.
• Concentration Inequalities by Boucheron, Lugosi, Massart, Chapter 3.1