Editing Stochastic programming (section)

==== Asymptotics of the SAA optimal value ====

Suppose the sample <math>\xi^1,\dots,\xi^N</math> is i.i.d. and fix a point <math>x \in X</math>. Then the sample average estimator <math>\hat{g}_N(x)</math>, of <math>g(x)</math>, is unbiased and has variance <math>\frac{1}{N}\sigma^2(x)</math>, where <math>\sigma^2(x):=Var[Q(x,\xi)]</math> is supposed to be finite. Moreover, by the [[central limit theorem]] we have that

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"><math>
\sqrt{N} [\hat{g}_N-  g(x)] \xrightarrow{\mathcal{D}} Y_x
</math></div>

where <math>\xrightarrow{\mathcal{D}}</math> denotes convergence in ''distribution'' and <math>Y_x</math> has a normal distribution with mean <math>0</math> and variance <math>\sigma^2(x)</math>, written as <math>\mathcal{N}(0,\sigma^2(x))</math>.

In other words, <math>\hat{g}_N(x)</math> has ''asymptotically normal'' distribution, i.e., for large <math>N</math>, <math>\hat{g}_N(x)</math> has approximately normal distribution with mean <math>g(x)</math> and variance <math>\frac{1}{N}\sigma^2(x)</math>. This leads to the following (approximate) <math>100(1-\alpha)</math>% confidence interval for <math>f(x)</math>:

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"> <math>
\left[ \hat{g}_N(x)-z_{\alpha/2} \frac{\hat{\sigma}(x)}{\sqrt{N}}, \hat{g}_N(x)+z_{\alpha/2} \frac{\hat{\sigma}(x)}{\sqrt{N}}\right]
</math></div>

where <math>z_{\alpha/2}:=\Phi^{-1}(1-\alpha/2)</math> (here <math>\Phi(\cdot)</math> denotes the cdf of the standard normal distribution) and

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"><math>
\hat{\sigma}^2(x) := \frac{1}{N-1}\sum_{j=1}^{N} \left[ Q(x,\xi^j)-\frac{1}{N} \sum_{j=1}^N Q(x,\xi^j) \right]^2
</math></div>

is the sample variance estimate of <math>\sigma^2(x)</math>. That is, the error of estimation of <math>g(x)</math> is (stochastically) of order <math> O(\sqrt{N})</math>.