[Math] Efron-Stein inequality

probability

The Efron-Stein inequality sais that if $X_1,\ldots,X_n$ are independent random variables on say $R^n$, and $f:R^n \rightarrow R$ s.t. $Z:=f(X_1,\ldots,X_n)$ has finite variance, then

$$\operatorname{Var}(X)\le \sum_{i=1}^n E[(Z-E^{(i)}[Z]]$$

where $E^{(i)}$ denotes conditional expectation taken w.r.t. $X_i$ by keeping the rest of the variables fixed.

On going through the proof, it is not clear to me why do we need the variables to be independent and where is that used in the proof?

Best Answer

Let $E^{(i)}[Z]$ denote the conditional expectation $E[Z|X_1, \ldots, X_{i-1}, X_{i+1}, \ldots X_n]$.

At some point of the proof, we want to prove that $$E^{(i)}[(Z-E^{(i)}[Z])^2] = \tfrac{1}{2} E^{(i)}[(Z-Z_i^\prime)^2].$$ For this, we use a classical trick: if $X$ and $Y$ are i.i.d's then $\mbox{var}(X) = E[\tfrac{1}{2}(X-Y)^2]$.

Related Solutions

[Math] Expected value and variance of ratio of two sums of two sets of random variables

If $X_i \backsim \operatorname{Gamma}(\alpha,\beta)$ where $\alpha$ is the shape and $\beta$ is the scale parameter then $$ \mathbb{E}\left[ X_i \right] = \alpha \beta \quad \quad \mbox{and} \quad \quad \mathbb{V}\mbox{ar}\left[ X_i \right] = \alpha \beta^2 $$

From the properties of the gamma distribution $$ \overline{X} \backsim \operatorname{Gamma}\left(n \alpha, \beta/n \right) $$ which means $$ \mathbb{E}\left[ \bar{X}\right] = \alpha\beta \quad \quad \mbox{and} \quad \quad \mathbb{V}\mbox{ar}\left[\bar{X}\right] = \alpha \beta^2/n $$ Then for $$ Y_i | X_i \backsim \operatorname{Gamma}\left(\alpha, \beta X_i \right) $$ $$ \mathbb{E}\left[ Y_i | X_i \right] =\alpha \beta X_i \quad \quad \mbox{and} \quad \quad \mathbb{V}\mbox{ar}\left[Y_i | X_i \right] = \alpha (\beta X_i )^2 $$

From the law of total expectation we have \begin{equation} \begin{split} \mathbb{E}\left[\frac{\bar{Y}}{\bar{X}}\right]&= \left. \mathbb{E}\left[ \mathbb{E}\left[ \frac{\bar{Y}}{\bar{X}} \right| X_1, \ldots, X_n \right] \right] \\ &= \mathbb{E}\left[ \frac{1}{\bar{X}} \frac{1}{n} \sum_{i=1}^n\mathbb{E} [ Y_i \big| X_1, \ldots, X_n ] \right] \\ &= \mathbb{E}\left[ \frac{1}{\bar{X}} \frac{1}{n} \sum_{i=1}^n\mathbb{E}[ Y_i \big| X_i ] \right] \\ & = \mathbb{E}\left[ \frac{1}{\bar{X}} \frac{1}{n} \sum_{i=1}^n \alpha \beta X_i \right] \\ & = \alpha \beta \mathbb{E}\left[ \frac{1}{\bar{X}} \frac{1}{n} \sum_{i=1}^n X_i \right] \\ & = \alpha \beta \mathbb{E}\left[ \frac{1}{\bar{X}} \bar{X} \right] \\ & = \alpha \beta \mathbb{E}\left[ 1 \right] \\ & = \alpha \beta \\ \end{split} \end{equation}

From the law of total variance we have \begin{equation*} \begin{split} \mathbb{V}\mbox{ar}\left[\frac{\bar{Y}}{\bar{X}}\right] &= \left. \mathbb{V}\mbox{ar}\left[ \mathbb{E}\left[ \frac{\bar{Y}}{\bar{X}} \right| X_1, \ldots, X_n \right] \right] + \left. \mathbb{E}\left[ \mathbb{V}\mbox{ar} \left[ \frac{\bar{Y}}{\bar{X}} \right| X_1, \ldots, X_n \right] \right] \\ &= \left. \mathbb{V}\mbox{ar}\left[ \frac{1}{\bar{X} } \frac{1}{n} \mathbb{E}\left[ \sum_{i=1}^nY_i\right| X_1, \ldots, X_n \right] \right] + \left. \mathbb{E}\left[ \frac{1}{\bar{X}^2 } \frac{1}{n^2} \mathbb{V}\mbox{ar} \left[ \sum_{i=1}^nY_i \right| X_1, \ldots, X_n \right] \right] \\ &= \mathbb{V}\mbox{ar}\left[ \frac{1}{\bar{X} } \frac{1}{n} \sum_{i=1}^n \mathbb{E}\left[ Y_i\big| X_i\right] \right] + \mathbb{E}\left[ \frac{1}{\bar{X}^2 } \frac{1}{n^2} \sum_{i=1}^n \mathbb{V}\mbox{ar} [ Y_i \big| X_i] \right] \\ &= \mathbb{V}\mbox{ar}\left[ \frac{1}{\bar{X} } \frac{1}{n} \sum_{i=1}^n \alpha \beta X_i \right] +\mathbb{E}\left[ \frac{1}{\bar{X}^2 } \frac{1}{n^2} \sum_{i=1}^n \alpha (\beta X_i )^2 \right] \\ &= \alpha^2 \beta^2 \mathbb{V}\mbox{ar}\left[ \frac{1}{\bar{X} } \bar{X} \right] +\mathbb{E}\left[ \frac{n^2}{ (\sum_{i=1}^n X_i)^2 } \frac{\alpha \beta^2}{n^2} \sum_{i=1}^n X_i^2 \right] \\ &= \alpha^2 \beta^2 \mathbb{V}\mbox{ar}\left[ 1 \right] + \alpha \beta^2 \mathbb{E}\left[ \frac{1}{ (\sum_{i=1}^n X_i)^2 } \sum_{i=1}^n X_i^2 \right] \\ &= \alpha \beta^2 \mathbb{E}\left[ \frac{ \sum_{i=1}^n X_i^2 }{ (\sum_{i=1}^n X_i)^2 } \right] \\ \end{split} \end{equation*}

Probability – Expectation and Variance of $Y=\max(X_1,\ldots,X_n)$ for Uniform Distribution

Notice that $$\mathbb{P}(Y \leq y) = \mathbb{P}(\max(X_1, \dots, X_n) \leq y)\text{.}$$ Now, note that if the largest of $n$ numbers is less than $y$, it follows that each of the $n$ numbers must be less than $y$ as well.

So, $$\mathbb{P}(\max(X_1, \dots, X_n) \leq y) = \mathbb{P}(X_1 \leq y \cap X_2 \leq y \cap\cdots\cap X_n \leq y)\text{.}$$ By independence, we have $$\mathbb{P}(X_1 \leq y \cap X_2 \leq y \cap\cdots\cap X_n \leq y) =\mathbb{P}(X_1 \leq y) \mathbb{P}(X_2 \leq y)\cdots\mathbb{P}(X_n \leq y)=y^n$$ for $y \in [0, 1]$. Hence, $$F_{Y}(y)=\mathbb{P}(Y \leq y) = \begin{cases} 0, & y < 0 \\ y^n, & y \in [0, 1] \\ 1, & y > 1\text{.} \end{cases}$$ The PDF of $Y$ is thus $$f_{Y}(y)=F^{\prime}_{Y}(y) = \begin{cases} ny^{n-1}, & y \in [0, 1] \\ 0, & \text{otherwise.} \end{cases}$$

Thus, $Y$ follows a Beta distribution with $\alpha = n$ and $\beta = 1$. Hence, the mean is $$\mathbb{E}[Y]=\dfrac{\alpha}{\alpha+\beta}=\dfrac{n}{n+1}$$ and the variance is $$\text{Var}(Y) = \dfrac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)} = \dfrac{n}{(n+1)^2(n+2)}\text{.}$$

Best Answer

Related Solutions

[Math] Expected value and variance of ratio of two sums of two sets of random variables

Probability – Expectation and Variance of $Y=\max(X_1,\ldots,X_n)$ for Uniform Distribution

Related Question