Efron-Stein inequality

独立な確率変数 $X_1,\dots,X_n$ による和 $Z = X_1 + \cdots + X_n$ の分散は

$\displaystyle \mathrm{Var}(Z) = \sum_{i=1}^n \mathrm{Var}(X_i)$

という関係が成り立つが、似たような関係式を一般の関数 $Z = f(X_1,\dots,X_n)$ に対して述べたのがEfron-Stein inequalityである

独立な確率変数 $X_1,\dots,X_n$ によって定義されるsquare-integrableな関数 $Z = f(X_1,\dots,X_n)$ に対して以下の関係が成り立つ:
$\displaystyle \mathrm{Var}(Z) \leq \sum_{i=1}^n \mathbb{E} \left[ \left( Z - \mathbb{E}^{(i)}Z \right)^2\right]$

ただし、 $\mathbb{E}^{(i)}Z$ は $X^{(i)} = (X_1,\dots,X_{i-1},X_{i+1},\dots,X_n)$ によって条件付けられた $Z$ の期待値、すなわち $X_i$ の確率分布を $\mu_i$ と表した時の
$\displaystyle \mathbb{E}^{(i)}Z = \int_{\mathcal{X}} f(X_1,\dots,X_{i-1},x_i,X_{i+1},\dots,X_n) d\mu_i(x_i)$

$Z = \sum_{I=1}^n X_i$ であるときは $Z - \mathbb{E}^{(i)}Z = X_i - \mathbb{E}X_i$ よりEfron-Stein inequalityの右辺は $\sum_{i=1}^n \mathrm{Var}(X_i)$ となり、冒頭で述べた「和の分散が分散の和」の不等式版が得られる*1

証明の肝は、 $Z - \mathbb{E}Z$ をDoob decompositionによって $L^2$ 空間で直交する確率変数の和で表すというアイディアである

証明

$\mathbb{E}_i Z$ を $(X_1,\dots,X_i)$ によって条件付けた $Z$ の期待値、すなわち

$\displaystyle \mathbb{E}_i Z = \int_{\mathcal{X}^{n-i}} f(X_1,\dots,X_{i},x_{i+1},\dots,x_n) d\mu_{i+1}(x_{i+1})\dots d\mu_n (x_n)$

とし、

$\displaystyle \Delta_i = \mathbb{E}_i Z - \mathbb{E}_{i-1}Z$

と定義すれば*2、いわゆるtelescoping sumにより

$\displaystyle Z - \mathbb{E}Z = \sum_{I=1}^n \Delta_i$

が成り立ち、さらに任意の $j > i$ に対して $\mathbb{E}_i \Delta_j = 0$ より $\mathbb{E}_i [\Delta_j \Delta_i ] = \Delta_i \mathbb{E}_i \Delta_j = 0$ となるが、これは

$\displaystyle \begin{align*} \mathrm{Var}(Z) &= \mathbb{E}\left[\left( \sum_{i=1}^n \Delta_i \right)^2\right] \\ &= \sum_{i=1}^n \mathbb{E}[\Delta_i^2] + 2\sum_{j > i} \mathbb{E}[\Delta_i \Delta_j] \\ &= \sum_{i=1}^n \mathbb{E}[\Delta_i^2] \end{align*}$

を意味する

Fubini's theoremより $\mathbb{E}_i [\mathbb{E}^{(i)}Z] = \mathbb{E}_{i-1} Z$ であることに注目すると $\Delta_i = \mathbb{E}_i [Z - \mathbb{E}^{(i)}Z ]$ と表せ、Jensen's inequalityより