Numerical methods. Note 12

[~Home~]

Monte Carlo Integration II. Stratified Sampling.

Numerical Methods. Note~ « 12 »

Stratified sampling. This algorithm tries to distribute more points to those regions where the variance is largest. The MISER routine implements recursive stratified sampling along the following lines:

if the number of given points is too small call plain montecarlo and return
sample a fraction (N_trial) of given points randomly from the given volume
for each dimension:
	subdivide the volume into two subvolumes (left and right) along this dimension
	estimate the (sub)variances in the two subvolumes
pick the dimension whith the largest (sub)variance
subdivide your volume in two along this dimension
distribute the remaining points between the two subvolumes proportional to (sub)variances (N_left and N_right)
dispatch two recursive calls to each of the sub-volumes
estimate the grand average and grand variance:
	grand_average = (N_trial*trial_average+N_left*left_average+N_right*right_average)/(N_trial+N_left+N_right)
return

Quasi-Random (Low-discrepancy) sampling. Lattices. The idea of the quasi-random sampling is to distribute points "more uniformly" than in random sampling thus (hopefully) reducing the error. One of the quasi-random methods is lattices, which can be considered as a grid with non-orthogonal axes. Let α_k, k=1:n be a set of (wisely chosen) irrational numbers. Then the i-th point is generated as

x_i = { frac(i α₁), ... , frac(i α_n) },

where frac(z) denotes the fractional part of z. The problem with this method is that a high accuracy arithmetics is needed in order to generate a reasonable amount of quasi-random numbers.

Problems

(non-obligatory) Implement the recursive stratified sampling routine. The routine should calculate the average and the variance for a given function in multi dimensions over a given rectangular volume.
Try combinations of plain and stratified sampling with lattices and see whether this improves things.
Calculate ∫₀^π ^dx/_π~∫₀^π ^dy/_π~∫₀^π ^dz/_π (1-cos(x)cos(y)cos(z))^-1~=~Γ(1/4)⁴/(4π³) ≈ 1.3932039296856768591842462603255