Editing Monte Carlo integration (section)

=== MISER Monte Carlo ===
The MISER algorithm is based on recursive [[stratified sampling]]. This technique aims to reduce the overall integration error by concentrating integration points in the regions of highest variance.<ref>{{harvnb|Press|Farrar|1990|pp=190-195}}</ref>

The idea of stratified sampling begins with the observation that for two [[Disjoint sets|disjoint]] regions ''a'' and ''b'' with Monte Carlo estimates of the integral <math>E_a(f)</math> and <math>E_b(f)</math> and variances <math>\sigma_a^2(f)</math> and <math>\sigma_b^2(f)</math>, the variance Var(''f'') of the combined estimate
<math display="block">E(f) = \tfrac{1}{2} \left (E_a(f) + E_b(f) \right )</math>
is given by,
<math display="block">\mathrm{Var}(f) = \frac{\sigma_a^2(f)}{4 N_a} + \frac{\sigma_b^2(f)}{4 N_b}</math>

It can be shown that this variance is minimized by distributing the points such that,
<math display="block">\frac{N_a}{N_a + N_b} = \frac{\sigma_a}{\sigma_a + \sigma_b}</math>

Hence the smallest error estimate is obtained by allocating sample points in proportion to the standard deviation of the function in each sub-region.

The MISER algorithm proceeds by bisecting the integration region along one coordinate axis to give two sub-regions at each step. The direction is chosen by examining all ''d'' possible bisections and selecting the one which will minimize the combined variance of the two sub-regions. The variance in the sub-regions is estimated by sampling with a fraction of the total number of points available to the current step. The same procedure is then repeated recursively for each of the two half-spaces from the best bisection. The remaining sample points are allocated to the sub-regions using the formula for ''N<sub>a</sub>'' and ''N<sub>b</sub>''. This recursive allocation of integration points continues down to a user-specified depth where each sub-region is integrated using a plain Monte Carlo estimate. These individual values and their error estimates are then combined upwards to give an overall result and an estimate of its error.