1
$\begingroup$

From Wikipedia

The Efron–Stein inequality (or influence inequality, or MG bound on variance) bounds the variance of a general function.

Suppose that $X_1 \dots X_n, X_1' \dots X_n'$ are independent with $X_i'$ and $X_i$ having the same distribution for all $i$.

Let $X = (X_1,\dots , X_n), X^{(i)} = (X_1, \dots , X_{i-1}, X_i',X_{i+1}, \dots , X_n)$. Then $$ \mathrm{Var}(f(X)) \leq \frac{1}{2} \sum_{i=1}^{n} E[(f(X)-f(X^{(i)}))^2]. $$

I wonder how this equality can be useful? It is supposed to provide an upper bound on $\mathrm{Var}(f(X))$, but I don't see $E[(f(X)-f(X^{(i)}))^2]$ in this bound is easier to compute than $\mathrm{Var}(f(X))$.

Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

I was lectured this inequality last year on a course where the course examined concentration of measure phenomenon and noise sensitivity of functions of binary numbers {-1,1}. We were just given this result without any application. The lecturer said something this kind of inequality if quite useful to topics he studied, which was models for polymer growth. We were not given any non-trivial examples. The bound itself is not very good. I think I tried with it with some simple functions of binomial distribution, the result was a factor of n out.

I apologise if my answer is not as helpful as you hoped.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .