Concentration of measure and bounds on variance - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T19:44:44Z http://mathoverflow.net/feeds/question/54795 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54795/concentration-of-measure-and-bounds-on-variance Concentration of measure and bounds on variance tristes_tigres 2011-02-08T17:25:32Z 2011-02-08T22:30:54Z <p>I am trying to characterize the sensitivity of a function $f: R^N\to{}R$ to the perturbations in the input vector $\mathbb{x}=\left[x_1,\dots{}x_N\right]$. For that purpose, I evaluate Cramer-Rao bound for Gaussian i.i.d. arguments.</p> <p>The function has a singularity at the point $\mathbb{x}_0$ where $f(\mathbb{x}_0)=0$, in the sense that $\|\nabla{}f\|\sim{}1/f$ as $\mathbb{x}\to\mathbb{x}_0$</p> <p>The Cramer-Rao bound then doesn't make sense, because it diverges at $\mathbb{x}_0$, while the variance of $f$, obviously, remains bounded. What I am looking for, I guess, some type of "concentration of measure"/"deviation inequality"-type sharp bound on the variance of $f$. </p> <p>The literature on concentration of measure phenomenon is extensive and deals with fairly advanced topics, whereas I am looking for something rather more basic. If you could point towards some starting point, your help will be appreciated.</p> http://mathoverflow.net/questions/54795/concentration-of-measure-and-bounds-on-variance/54827#54827 Answer by Tom LaGatta for Concentration of measure and bounds on variance Tom LaGatta 2011-02-08T22:30:54Z 2011-02-08T22:30:54Z <p>Let $X_i$ and $X'_i$ be i.i.d random variables. Write $f = f(X_1, \dots, X_n),$ and define $$f_i = f(X_1, \dots, X'_i, \dots, X_n)$$ as the same function with the $i$th input replaced by the independent copy $X'_i$. </p> <p>The <a href="http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/AEifns.pdf" rel="nofollow"><b>Efron-Stein inequality</b></a> states that $$\operatorname{Var}(f) \le \tfrac 1 2\sum_{i=1}^n \ \mathbb E(f - f_i)^2.$$</p> <p>Since your random variables are Gaussians, the system satisfies the <a href="http://www.stat.berkeley.edu/~sourav/talk_matrix2.pdf" rel="nofollow"><b>Poincaré inequality</b></a> too: $$\operatorname{Var}(F) \le C \ \mathbb E |\nabla f|^2.$$</p>