From left to right: Michael Giles and Thanos Avramidis

When we simulate the sample path of a stochastic process defined by a stochastic differential equation, except in simple special cases, we must discretize the time, and replace any estimator defined as a function of the sample path by a function of the process values at the discretization points. A too crude discretization gives too much bias for the estimator, whereas a too fine discretization makes the simulation too expensive to run.

In his paper ``Multilevel Monte Carlo Path Simulation,'' published in Operations Research in 2008, Michael Giles developed a method based on clever multigrid ideas in numerical analysis, that provides an estimator with the same low bias and almost the same variance as an estimator based on a very fine grid, with a computing effort comparable to that required with a crude discretization.

The idea is to select a decreasing sequence of discretization time steps, and write the estimator for the finest discretization as equal to the estimator for the coarsest one plus a sum of corrections, where each correction is the difference between the estimators at two successive time steps. We first run the simulation at the coarse discretization for a large sample size, then we estimate each correction term independently by simulating the difference with carefully synchronized common random numbers, using a sample size that decreases when the time step decreases. Much smaller sample sizes can be used for the corrections at the finer levels because these corrections have much smaller variances. The efficiency improvement is characterized in the paper by a general theorem showing that the computing effort often increases, as a function of one over the mean square error, at a slower rate than with the standard Monte Carlo method.The achieved rate depends on how the variance of the correction and the bias behave as a function of the time step, for the application at hand. A similar technique was proposed earlier by Stefan Heinrich for the different problem of estimating a function of a continuous parameter everywhere in a finite interval, by Monte Carlo, when only noisy observations of the function are available.

The proposed method applies to various discretization schemes, including Euler and Milstein methods. In the prize-winning paper, its efficiency was illustrated with option pricing problems in finance. Subsequent papers have examined the combination with quasi-Monte Carlo, estimation of sensitivities, jump-diffusion processes, stochastic partial differential equations, and applications to other areas than finance.

This work is a significant breakthrough in Monte Carlo methods for stochastic differential equations, and is already having a large impact on simulation research in finance.

Past Winners

To recognize outstanding contributions to the simulation literature, the INFORMS Simulation Society annually sponsors an Outstanding Simulation Publication Award. Anyone is eligible to win the Award. Journal articles, proceedings articles, books, and monographs are eligible contributions.

Past recipients of this award are:

Paul Dupuis, Kevin Leder, and Hui Wang Receive 2010 Outstanding Simulation Publication Award from the INFORMS Simulation Society

Left to right: Peter Haas, Hui Wang, Christos Alexopoulos, Kevin Leder

The 2010 Outstanding Simulation Award was awarded to Paul Dupuis and Hui Wang (Brown University) and Kevin Leder (Harvard University) for their two papers: “Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling” which appeared in Mathematics of Operations Research in 2007, and “Importance Sampling for Sums of Random Variables with Regularly Varying Tails” which appeared in ACM Transactions on Computer Modeling and Simulation in 2007. The awards committee consisted of Peter Glynn (chair), Christos Alexopoulos and Athanasios Avramidis.

2009 -- Avramidis, Athanassios (Thanos) and Pierre L'Ecuyer. 2006. Efficient Monte Carlo and quasi-Monte Carlo option pricing under the variance-gamma model, Management Science 52(12): 1930-1944.

2008 -- Asmussen, Soren and Peter Glynn. 2007. Stochastic Simulation: Algorithms and Analysis, New York: Springer.

2007 --
1. Alexopoulos, Christos and David Goldsman. 2004. To Batch Or Not To Batch?, ACM TOMACS, 14 (1): 76-114.
2. Duchon, Philippe, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. 2004. Boltzmann Samplers for Random Generation of Combinatorial Structures, Combinatorics, Probability and Computing.

2006 -- Boesel, Justin, Barry Nelson and Seong-hee Kim. 2003. Using Ranking and Selection to "Clean Up" After Simulation Optimization. Operations Research 51(5): 814-825.

2005 -- Glasserman, Paul. 2003. Monte Carlo Methods in Financial Engineering, New York: Springer.

2004 -- Not given.

2003 -- Haas, Peter. 2002. Stochastic Petri Nets: Modelling, Stability, Simulation, New York: Springer.

2002 -- Asmussen, Soren, Klemens Binswanger, and Bjarne Hojgaard. 2000. Rare events simulation for heavy-tailed distributions. Bernoulli, 6 (2): 303-322.

2001 -- Law, Averill M., and W. David Kelton. 1999. Simulation Modeling and Analysis, 3rd edition, New York: McGraw-Hill.

2000 -- Propp, James and David Wilson. 1996. Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Random Structures and Algorithms, volume 9 , 223-252. 1998. Coupling from the past: a user's guide. Microsurveys in Discrete Probability, Volume 41 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 181--192. American Mathematical Society.

1999 -- L'Ecuyer, Pierre. 1996. Combined Multiple Recursive Random Number Generators. Operations Research, 44 (5), 816--822. Maximally Equidistributed Combined Tausworthe Generators. Mathematics of Computation, 65 (213), 203-213.

1998 -- Fu, Michael, and Jian-Qiang Hu. 1997. Conditional Monte Carlo: Gradient Estimation and Optimization Applications. Boston: Kluwer Academic Press.

1997 -- Fishman, George. 1996. Monte Carlo: Concepts, Algorithms, and Applications. New York: Springer-Verlag.

1996 -- Shahabuddin, Perwez. 1994. Importance sampling for the simulation of highly reliable Markovian systems. Management Science 40 (3): 333-352.

1995 -- Niederreiter, Harald. 1992. Random number generation and quasi--Monte Carlo methods. Philadelphia: Society for Industrial and Applied Mathematics.

1994 -- Fujimoto, Richard M. 1990. Parallel discrete event simulation. Communications of the ACM 33 (10): 30-53.

1993 -- Fox, Bennett L., and Peter W. Glynn. 1990. Discrete-time conversion for simulating finite-horizon Markov processes. SIAM Journal on Applied Mathematics 50 (5): 1457-1473.

1992 -- Glasserman, Paul. 1991. Gradient estimation via perturbation analysis. Boston: Kluwer Academic Publishers.

1991 -- Whitt, Ward. 1989. Planning queueing simulations. Management Science 35 (11): 1341-1366.

1990 -- Heidelberger, Philip , Xi-Ren Cao, Michael A. Zazanis, and Rajan Suri. 1988. Convergence properties of infinitesimal perturbation analysis estimates. Management Science 34 (11): 1281-1302.

1989 -- Devroye, Luc. 1986. Non-uniform random variate generation. New York: Springer-Verlag.

1988 -- Zeigler, Bernard P. 1984. Multifacetted modelling and discrete event simulation. London: Academic Press.

1987 -- Schruben, Lee W. 1983. Confidence interval estimation using standardized time series. Operations Research 31 (6): 1090-1108.

1986 -- Not given.

1985 -- Wilson, James R., and A. Alan B. Pritsker. 1984. Experimental evaluation of variance reduction techniques for queueing simulation using generalized concomitant variables. Management Science 30 (12): 1459-1472.

1984 -- Not given.

1983 (tie) -- Meketon, Marc S., and Philip Heidelberger. 1982. A renewal theoretic approach to bias reduction in regenerative simulations. Management Science 28 (2): 173-181.

1983 (tie) -- Law, Averill M., and W. David Kelton. 1982. Confidence interval procedures for steady-state simulations, II: A survey of sequential procedures. Management Science 28 (5): 550-562.

1982 -- Lavenberg, Stephen S., and Peter D. Welch. 1981. A perspective on the use of control variables to increase the efficiency of Monte Carlo simulations. Management Science 27 (3): 322-335.

1981 -- Schruben, Lee W. 1980. A coverage function for interval estimators of simulation response. Management Science 26 (1): 18-27.