Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.