Monte Carlo

The Monte Carlo method provides approximate solutions to a variety of mathematical problems by performing statistical sampling experiments on a computer. Remarkably, the method applies to problems with absolutely no probabilistic content as well as to those with inherent probabilistic structure. This alone does not give the Monte Carlo method an advantage over other methods of approximation. However, among all numerical methods that rely on n-point evaluations in m-dimensional space to produce an approximate solution, the Monte Carlo method has absolute error of estimate that decreases as n ^−l/2 whereas, in the absence of exploitable special structure, all others have errors that decrease as n ^−l/m at best. This property gives the Monte Carlo method a considerable edge in computational efficiency as m, the size of the problem, increases. Combinatorial settings illustrate this property especially well. Whereas the exact solution to a combinatorial problem with m elements often has computational cost that increases exponentially or superexponentially with m, the Monte Carlo method. frequently provides an estimated solution with tolerable error at a cost that increases no faster than as a polynomial in m.

This chapter introduces the reader to fundamental issues that arise when applying the Monte Carlo method to solving a commonly encountered problem in numerical computation. In its most basic form the problem is to evaluate the volume of a bounded region in multi-dimensional euclidean space. The more general problem is to evaluate the integral of a function on such a region. The Monte Carlo method often offers a competitive and sometimes the only useful solution to the problem. The appeal of the Monte Carlo method arises when the shape of the region of interest makes solution by analytical methods impossible and, in the case of the more general function integration, when little is known about the smoothness and variational properties of the integrand, or what is known precludes the applications of alternative numerical evaluation techniques.

Generating a random sample constitutes an essential feature of every Monte Carlo experiment. If as in expression (2.67), is to be estimated, then a procedure that randomly generates points from the uniform distribution on ℱ^m would suffice. When the cost of evaluating φ(x) in Algorithm \({\overline \zeta _n}\) in Sec. 2.7 is prohibitively high, the equivalence of expression(1) and in expression (2.72c) becomes of interest. Recall that, for A⊑ℬ ⊑ℝ^m, 0≤F(A) ≤F≤ F(ℬ) ≤F(ℝ^m) = 1. Since F is a distribution function, an alternative procedure randomly samples Z ⁽¹⁾,...,Z ⁽ⁿ⁾ independently from F and computes as an unbiased estimate of ζ. Although generating Z ⁽ⁱ⁾ from F always costs more than generating X ⁽ⁱ⁾ from the uniform distribution on ℱ^m, evaluating k(Z ⁽ⁱ⁾) may be considerably less costly than evaluating φ(X ⁽ⁱ⁾).

Section 2.7 broadened the concept of a Monte Carlo experiment to the general problem of evaluating the Lebesgue-Stieltjes integral where z = (z ₁,..., z _m ), {F(z)} is a joint d.f. on the m-dimensional region ℱ and {k(z)} denotes a weighting kernel defined on Also, the introduction to Ch. 3 indicates that alternative d.f.s and kernels may exist which satisfy expression (1). We call each {F(z), k(z);z ∈ ℱ } satisfying expression (1) a sampling plan, since each provides a basis for generating data which can be used to estimate ζ unbiasedly. Whereas Ch. 3 describes how to generate data efficiently from a particular {F(z), z ∈ℱ } once a sampling plan is chosen, the present chapter studies the relative desirability of alternative sampling plans from the viewpoint of computational efficiency.

This chapter considerably broadens the range of application of the Monte Carlo method by introducing the concept of a random tour on discrete, continuous, and general state spaces. This development serves several purposes, of which the ability to sample from a multivariable distribution remains preeminent. Let {F(x), x ∈ ℋ} denote an m-dimensional d.f. defined on a region ℋ ⊆ ℝ ^m , and let {g(x), x ∈ ℋ} denote a known function satisfying ∫_ℋ g ²(x)dF(x) < ∞. Suppose that the objective is to evaluate

As in Ch. 5, we take as our objective the estimation of , where F denotes an m-dimensional d.f. on \(X \subseteq {\mathbb{R}^m}\). Consider a Monte Carlo Markov sampling experiment composed of n independent replications, each of which begins in a state drawn from an initializing nonequilibrium distribution π₀. After a warm-up interval of k — 1 steps on each replication, sampling continues for t additional steps and one uses the n independent truncated sample paths or realizations, each of length t, to estimate µ. Whereas Ch. 5 concentrates on sample path generating algorithms and a conceptual understanding of convergence to an equilibrium state, this chapter focuses on sampling plan design and statistical inference. With regard to design, the chapter shows how the choices of k, n, π₀, and t affect computational and statistical efficiency. With regard to statistical inference, it describes methods for estimating the warm-up interval k that significantly mitigate the influence of the initial states drawn from the nonequilibrium distribution π₀. Also, it describes methods for computing asymptotically valid confidence intervals for µ in expression (1) as n → ∞ for fixed t, as t → ∞ for fixed n and as both n → ∞ and t → ∞. Because confidence intervals inevitably depend on variance estimates, we need to impose a moderately stronger restriction on g. Whereas the assumption \(\int_X {{g^2}\left( {\text{x}} \right){\text{d}}F\left( {\text{x}} \right)} < \infty \) in Ch. 5 guarantees a finite variance for a single observation on a sample path, the assumption \(\int_X {{g^4}\left( {\text{x}} \right){\text{d}}F\left( {\text{x}} \right)} < \infty \) is necessary for us to obtain consistent estimators of that variance and of other variances that play essential roles in the derivation of asymptotically valid confidence intervals for µ.

Every Monte Carlo experiment relies on the availability of a procedure that supplies sequences of numbers from which arbitrarily selected nonoverlapping subsequences appear to behave like statistically independent sequences and where the variation in an arbitrarily chosen subsequence of length k (≥1) resembles that of a sample drawn from the uniform distribution on the k-dimensional unit hyper-cube \({\mathcal{I}^k}\). The words “appear to behave” and “resemble” alert the reader to yet another potential source of error that arises in Monte Carlo sampling. In practice, many procedures exist for generating these sequences. In addition to this error of approximation, the relative desirability of each depends on its computing time, on its ease of use, and on its portability By portability, we mean the ease of implementing a procedure or algorithm on a variety of computers, each with its own hardware peculiarities.