Monte Carlo methods are useful in a wide variety of applications especially where a deterministic solution may be difficult or impossible to compute. In our class we specifically used it to do numerical integration but it can be used in areas are varied as finance or graphics. Despite their flexibility, MC methods can require many iterations to achieve the desired accuracy.

Latin Hypercube sampling can improve the efficiency of Monte Carlo simulations by picking the input samples better. Whereas MC methods typically pick points at random within the domain, Latin Hypercube sampling samples the entire domain more systematically.

Latin hypercube sampling begins by estimating each parameter’s uncertainty using a probability distribution. For some applications such as numerical integration we would only use uniform distributions in each dimension since we are trying to see which fraction of points fall within the object of interest and which outside. On the other hand if we were using Monte Carlo methods for numerical optimization then we might instead use normal distributions to generate the possible values for each parameter.

Then we would break up the distribution into N equal probability segments and a value for the parameter would be generated from each segment. Either the midpoint or the endpoints of each segment are used to generate the N parameter value. A visualization of a sample segmented pdf is below for N = 10 and assuming a normal distribution for the probable parameter values. Notice that each segment has equal area. Midpoints of each segment were used to generate the black points on the bottom:

These random values are saved in a matrix P . The first row has N possible values for the first parameter and the i^th row has the possible values for the i^th parameter.

Lastly each row is shuffled to break the correlations between the parameter values. Thus the smallest values of parameter 1 is not always grouped with the smallest values of parameter 2 and so on. Then each column is used as the input for one run of the Monte Carlo function. Thus we will have N sets of values to feed into the MC method.

Using the Latin hypercube method, we can more reliably sample the whole parameter space with fewer iterations. This can help improve convergence rates and speed up execution.

http://en.wikipedia.org/wiki/Latin_hypercube_sampling

http://en.wikipedia.org/wiki/Monte_Carlo_method