# Why is the sample variance of a Sample Average Approximation calculated in this way?

I am going through the great tutorial on Stochastic Programming by Shapiro and Philpott. When talking about Monte Carlo techniques, I get confused by the way they calculate the sample variance (page 13, equation (2.8)).

In short:

• Given a solution $$x$$, we approximate the recourse function $$Q(x)=\Bbb E_{\xi}[Q(x,\xi)]$$ by taking an i.i.d. sample of $$\xi$$, and thus obtaining $$\hat{q}_N(x)=\frac1N\sum\limits_{i=1}^NQ(x,\xi^i).$$
• The sample variance is then calculated as $$\hat{\sigma}^2_N(x)=\dfrac{1}{N(N-1)}\sum\limits_{i=1}^N[Q(x,\xi^i)-\hat{q}_N(x)]^2.$$

Since the mean is estimated from the sample itself ($$\hat{q}_N(x)$$), I would have expected to divide by $$N-1$$ (as in, e.g. Homem-de-Mello & Bayaraksan 2014 page 67, before formula (21)). Instead I find $$N(N-1)$$. I would be grateful if someone could help me understand this formula.

Since $$\hat q_{N'}(\hat x)\approx\Bbb E[Q(\hat x,\xi)]$$ and $$\Bbb V[\hat q_{N'}(\hat x)]=\Bbb V[Q(\hat x,\xi)]/N'$$, we have \begin{align}\hat\sigma_{N'}^2(\hat x)=\Bbb V[\hat q_{N'}(\hat x)]&=\frac1{N'}\cdot\frac1{N'-1}\sum_{j=1}^{N'}[Q(\hat x,\xi^j)-\Bbb E[Q(\hat x,\xi)]]^2\\&\approx\frac1{N'(N'-1)}\sum_{j=1}^{N'}[Q(\hat x,\xi^j)-\hat q_{N'}(\hat x)]^2\end{align} as required. The approximation is improved as $$N'$$ increases, under the Law of Large Numbers.

• @ TheSimpliFire thanks for your answer. Could you please further clarify the equivalence $\hat{q}_{N'}(\hat{x}) = \mathbb{E}[Q(\hat{x},\xi)]$? My understanding is that, providing that $\xi_1,\ldots,\xi_{N'}$ is an iid sample from $\xi$, $\hat{q}_{N'}(\hat{x})$ is an unbiased estimator for $\mathbb{E}[Q(\hat{x},\xi)]$, that is $\mathbb{E}[\hat{q}_{N'}(\hat{x})] = \mathbb{E}[Q(\hat{x},\xi)]$ (the first expectation taken over all the possible $N'$-size samples). Nov 30 '19 at 21:00
• Actually, the equality is only an approximation (this is outlined in section 2.2, p10). The true value of the expectation is governed by equation (2.3), p8. However, assuming the unbiased nature of $\xi_j$, for large $N'$, each weight (or probability) $p_j$ will tend to $1/N'$. Nov 30 '19 at 21:45
• Yes, it is an approximation. As far as I understand, the second equality should hold approximately too (after one substitutes $\hat{q}_{N'}(\hat{x})$ for $\mathbb{E}[Q(\hat{x},\xi)]$). Dec 1 '19 at 8:53
• Then, I am even more puzzled as to why the authors use this expression (which holds approximately, rather than a more intuitive $\hat{\sigma}^2_{N'}(\hat{x})=\dfrac{1}{N'-1}\sum\limits_{i=1}^{N'}[Q(\hat{x},\xi^i)-\hat{q}_{N'}(\hat{x})]^2$ for the sample variance (you just divide by $N'-1$ since you use the sample mean and have one less degree of freedom) as, e.g., Homem-de-Mello & Bayaraksan (2014) or Shapiro (2016). Dec 1 '19 at 8:57
• The extra $1/N'$ term is due to $\Bbb V[\hat q_{N'}(\hat x)]=\Bbb V[Q(\hat x,\xi)]/N'$ which is exact (see the top paragraph on p12). In your expression $\dfrac{1}{N'-1}\sum\limits_{i=1}^{N'}[Q(\hat{x},\xi^i)-\hat{q}_{N'}(\hat{x})]^2$, you are calculating only $\Bbb V[Q(\hat x,\xi)]$. Dec 1 '19 at 9:09