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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
5
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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