APPENDIX

I   Monte Carlo Integration

In a generic sense, Monte Carlo simulation¹ is an invaluable experimental tool for tackling difficult problems that are mathematically intractable; but the tool is imprecise in that it provides statistical estimates. Nevertheless, provided that the Monte Carlo simulation is conducted properly, valuable insight into a problem of interest is obtained, which would be difficult otherwise.

In this appendix, we focus on Monte Carlo integration, which is a special form of Monte Carlo simulation. Specifically, we address the difficult integration problem encountered in Chapter 5 dealing with computation of the differential entropy h(Y), based on the mathematically intractable conditional probability density function of (5.102) in Chapter 5.

To elaborate, we may say:

Monte Carlo integration is a computational tool, which is used to integrate a given function defined over a prescribed area of interest that is not easy to sample in a random and uniform manner.

Let W denote the difficult area over which random sampling of the differential entropy h(Y) is to be performed. To get around this difficulty, let V denote an area so configured that it incudes the area W and is easy to randomly sample. Desirably, the selected area V enclosed W as closely as possible for the simple reason that samples picked outside of W are of no practical interest.

Suppose now we pick a total of N samples in the area V, randomly and uniformly. Then according to Press, et al. (1998), the basic Monte Carlo integration theorem states that a computed “estimate” of the integral defining the differential entropy h(Y) is given by

where the average value (i.e., mean) is defined by

and the mean-square value is defined by

The y_i in (I.2) and (I.3) is the ith sample of the random variable Y picked from the area V. The “plus or minus” sign in the approximate formula of (I.1) should not be viewed as a rigorous bound. Rather, it represents a “one standard-deviation error” that results from the use of Monte Carlo integration.

Clearly, the larger we make the number of samples N, the smaller this error will be, resulting in a more accurate integration. However, this improvement is attained at the cost of increased computational complexity.

       Notes

1 Monte Carlo simulation derives its name from the city, Monte Carlo, Monaco, which is widely known in Europe for its casino gambling: a “game of chance.”

The term “Monte Carlo” was introduced into the technical literature by von Neumann and Ulam during World War II. Its adoption was intended as a codeword for the secret work that was going on at that time in Los Alamos, New Mexico, USA.