5.9.4 Stratified Sampling

5.9.4  Stratified Sampling

Consider crude Monte Carlo estimator

[5.89]

for some quantity ψ = E[f  (U)], U ~ Un((0,1)n). Stratify the region (0,1)n into w disjoint subregions:

[5.90]

Define w random vectors Xj ~ Un(Ωj). Then f  (U) can be represented as a mixture, in the sense of Section 3.11, of the f  (Xj) using weights pj = Pr(X ∈ Ωj). Consequently

[5.91]

[5.92]

With the method of stratified sampling, we apply a separate Monte Carlo estimator for each expectation E[f  (Xj)] and use the probabilities pj to take the probability-weighted mean. The result is an unbiased estimator

[5.93]

where mj is the sample size emplopyed on subregion Ωj. The standard error for stratified sampling is:

[5.94]

where σj is the standard deviation of f  (Xj). This formula suggests that, when partitioning (0,1)n, we do so in a manner that minimizes the terms pj σj. Consider Exhibit 5.15. This depicts a function f on an interval (0,1), which has been partitioned into three subintervals Ω1, Ω2, and Ω3. The variability of f over the entire interval (0,1) is greater than its variability over any subinterval.  We expect each standard deviation σj of fj (X) to be less than the standard deviation σ of f  (X). This will help minimize the terms pj σj.

Exhibit 5.15: Over the entire interval (0,1), f takes on a greater range of vales than it does over any of the individual subintervals Ω1, Ω2, or Ω3.

Formula [5.93] also suggests that we maximize each sample size mj. If the total sample size m = m1 + m2 + … + mw is fixed, we can increase one term mj only at the expense of the others. An optimal choice of sample sizes is to set, for each j,

[5.95]

The preceding optimization techniques depend upon the quantities σj, which typically will not be known. Accordingly, optimizing a stratified sampling analysis is often a matter of trial and error. A simple solution is to employ a preliminary Monte Carlo analysis to estimate the quantities σj.

Exercises
5.8

Consider the definite integral

[5.96]

Use the following steps to estimate the integral with stratified sampling:

  1. Apply to the integral a change of variables

    [5.97]

    to obtain an integral of form

    [5.98]

  2. Stratify the new region of integration (0,1)2 into three subregions:
    • Ω1 = {u : u1 ≤ .5 and  u2 ≤ .5},
    • Ω2 = {u : (u1 ≤ .5 and  u2 > .5) or (u1 > .5 and  u2 ≤ .5)},
    • Ω3 = {u : u1 > .5 and  u2 > .5}.
  3. Sketch the three subregions.
  4. Explain in your own words why these subregions are a reasonable choice for stratified sampling.
  5. Define Yj ~ U2(Ωj) for j = 1, 2, 3. Estimate the mean μj and standard deviation σj of f  (Yj) for each j as follows:
    1. Generate 50 U2(Ωj) pseudorandom vectors  for each j.
    2. For each j, calculate sample means and sample standard deviations  of the .
  6. Based upon the estimated standard deviations , apply [5.96] to determine a suitable sample size mj to be used in each subregion Ωj. Assume m = 1000.
  7. Compare your three results m1, m2, and m3 with the expected number of pseudorandom vectors u[k] that would fall in each of Ω1, Ω2, and Ω3 if stratified sampling were not used and crude Monte Carlo estimator [5.89] were used with the same total sample size of m = 1000.
  8. Based upon your values mj from item (f), specify an estimator for [5.98] of form [5.93].
  9. Based upon your estimated means and standard deviations from item (e), estimate the standard error of your estimator as well as the standard error of the corresponding crude Monte Carlo estimator. (Hint: For the crude Monte Carlo estimator, treat the random variable f(U) as a mixture, in the sense of Section 3.11, of three distributions.)
  10. Based upon your results from item (i), how much would you need to increase the sample size for the crude Monte Carlo estimator in order for it to have the same standard error as your stratified sampling estimator from item (h)?
  11. Apply your estimator from item (h) to estimate [5.98].

Solution