11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ 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). $\endgroup$ – k88074 Nov 30 at 21:00
  • $\begingroup$ 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'$. $\endgroup$ – TheSimpliFire Nov 30 at 21:45
  • $\begingroup$ 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]$). $\endgroup$ – k88074 Dec 1 at 8:53
  • $\begingroup$ 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). $\endgroup$ – k88074 Dec 1 at 8:57
  • $\begingroup$ 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)]$. $\endgroup$ – TheSimpliFire Dec 1 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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