Stochastic Mechanics Stochastic Modelling Random Media and Applied Probability Signal Processing and Image Synthesis (Formerly: Mathematical Economics and Finance Applications of Mathematics) Stochastic Optimization 57 Stochastic Control Stochastic Models in Life Sciences Edited by B. Rozovskii G. Grimmett Advisory Board D. Dawson D. Geman I. Karatzas F. Kelly Y. Le Jan B. Øksendal G. Papanicolaou E. Pardoux StochasticModellingandAppliedProbability formerly:ApplicationsofMathematics 1 Fleming/Rishel,DeterministicandStochasticOptimalControl(1975) 2 Marchuk,MethodsofNumericalMathematics(1975,2nd.ed.1982) 3 Balakrishnan,AppliedFunctionalAnalysis(1976,2nd.ed.1981) 4 Borovkov,StochasticProcessesinQueueingTheory(1976) 5 Liptser/Shiryaev,StatisticsofRandomProcessesI:GeneralTheory(1977,2nd.ed.2001) 6 Liptser/Shiryaev,StatisticsofRandomProcessesII:Applications(1978,2nd.ed.2001) 7 Vorob’ev,GameTheory:LecturesforEconomistsandSystemsScientists(1977) 8 Shiryaev,OptimalStoppingRules(1978) 9 Ibragimov/Rozanov,GaussianRandomProcesses(1978) 10 Wonham,LinearMultivariableControl:AGeometricApproach(1979,2nd.ed.1985) 11 Hida,BrownianMotion(1980) 12 Hestenes,ConjugateDirectionMethodsinOptimization(1980) 13 Kallianpur,StochasticFilteringTheory(1980) 14 Krylov,ControlledDiffusionProcesses(1980) 15 Prabhu,StochasticStorageProcesses:Queues,InsuranceRisk,andDams(1980) 16 Ibragimov/Has’minskii,StatisticalEstimation:AsymptoticTheory(1981) 17 Cesari,Optimization:TheoryandApplications(1982) 18 Elliott,StochasticCalculusandApplications(1982) 19 Marchuk/Shaidourov,DifferenceMethodsandTheirExtrapolations(1983) 20 Hijab,StabilizationofControlSystems(1986) 21 Protter,StochasticIntegrationandDifferentialEquations(1990) 22 Benveniste/Métivier/Priouret,AdaptiveAlgorithmsandStochasticApproximations(1990) 23 Kloeden/Platen,NumericalSolutionofStochasticDifferentialEquations(1992,corr.3rdprinting 1999) 24 Kushner/Dupuis, NumericalMethodsforStochasticControlProblemsinContinuousTime (1992) 25 Fleming/Soner,ControlledMarkovProcessesandViscositySolutions(1993) 26 Baccelli/Brémaud,ElementsofQueueingTheory(1994,2nd.ed.2003) 27 Winkler,ImageAnalysis,RandomFieldsandDynamicMonteCarloMethods(1995,2nd.ed. 2003) 28 Kalpazidou,CycleRepresentationsofMarkovProcesses(1995) 29 Elliott/Aggoun/Moore,HiddenMarkovModels:EstimationandControl(1995) 30 Hernández-Lerma/Lasserre,Discrete-TimeMarkovControlProcesses(1995) 31 Devroye/Györfi/Lugosi,AProbabilisticTheoryofPatternRecognition(1996) 32 Maitra/Sudderth,DiscreteGamblingandStochasticGames(1996) 33 Embrechts/Klüppelberg/Mikosch,ModellingExtremalEventsforInsuranceandFinance(1997, corr.4thprinting2003) 34 Duflo,RandomIterativeModels(1997) 35 Kushner/Yin,StochasticApproximationAlgorithmsandApplications(1997) 36 Musiela/Rutkowski,MartingaleMethodsinFinancialModelling(1997,2nd.ed.2005) 37 Yin,Continuous-TimeMarkovChainsandApplications(1998) 38 Dembo/Zeitouni,LargeDeviationsTechniquesandApplications(1998) 39 Karatzas,MethodsofMathematicalFinance(1998) 40 Fayolle/Iasnogorodski/Malyshev,RandomWalksintheQuarter-Plane(1999) 41 Aven/Jensen,StochasticModelsinReliability(1999) 42 Hernandez-Lerma/Lasserre,FurtherTopicsonDiscrete-TimeMarkovControlProcesses(1999) 43 Yong/Zhou,StochasticControls.HamiltonianSystemsandHJBEquations(1999) 44 Serfozo,IntroductiontoStochasticNetworks(1999) 45 Steele,StochasticCalculusandFinancialApplications(2001) 46 Chen/Yao,FundamentalsofQueuingNetworks:Performance,Asymptotics,andOptimization (2001) 47 Kushner,HeavyTrafficAnalysisofControlledQueueingandCommunicationsNetworks(2001) 48 Fernholz,StochasticPortfolioTheory(2002) 49 Kabanov/Pergamenshchikov,Two-ScaleStochasticSystems(2003) 50 Han,Information-SpectrumMethodsinInformationTheory(2003) (continuedafterindex) Søren Asmussen Peter W. Glynn Stochastic Simulation: Algorithms and Analysis Authors Søren Asmussen Peter W. Glynn Department of Theoretical Statistics Department of Management Science Department of Mathematical Sciences and Engineering Aarhus University Institute for Computational and Ny Munkegade Mathematical Engineering DK–8000 Aarhus C, Denmark Stanford University [email protected] Stanford, CA 94305–4026 [email protected] Managing Editors B. Rozovskii G. Grimmett Division of Applied Mathematics Centre for Mathematical Sciences 182 George St. Wilberforce Road, Cambridge CB3 0WB, Providence, RI 02912 UK USA [email protected] [email protected] Mathematics Subject Classifi cation (2000): 65C05, 60-08, 62-01, 68-01 Library of Congress Control Number: 2007926471 ISSN: 0172-4568 ISBN-13: 978-0-387-30679-7 e-ISBN-13: 978-0-387-69033-9 © 2007 Springer Science+Business Media, LLC All rights reserved. This work may not be t ranslated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or s cholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identifi ed as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper. 9 8 7 6 5 4 3 2 1 springer.com Preface Sampling-based computational methods have become a fundamental part ofthenumericaltoolsetofpractitionersandresearchersacrossanenormous number of different applied domains and academic disciplines. This book is intended to provide a broad treatment of the basic ideas and algorithms associated with sampling-based methods, often also referred to as Monte Carlo algorithms or as stochastic simulation. The reach of these ideas is illustrated here by discussing a wide range of different applications. Our goalistoprovidecoveragethatreflectstherichnessofboththeapplications and the models that have found wide usage. Of course, the models that are used differ widely from one discipline to another. Some methods apply across the entire simulation spectrum, whereas certain models raise particular computational challenges specific to those model formulations. As a consequence, the first part of the book focuses on general methods, whereas the second half discusses model- specificalgorithms.Themathematicallevelisintendedtoaccommodatethe reader, so that for models for which even the model formulation demands some sophistication on the part of the reader (e.g., stochastic differential equations), the mathematical discussion will be at a different level from that presented elsewhere. While we deliver an honest discussion of the basic mathematical issues that arise in both describing and analyzing al- gorithms, we have chosen not to be too fussy with regard to providing precise conditions and assumptions guaranteeing validity of the stated re- sults.Forexample,sometheoremstatementsmayomitconditions(suchas moment hypotheses) that, while necessary mathematically, are not key to vi Preface understandingthe practicaldomainofapplicabilityofthe result.Likewise, in some arguments, we have provided an outline of the key mathematical steps necessary to understand (for example) a rate of convergence issue, without giving all the mathematical details that would serve to provide a complete and rigorous proof. Asaresult,webelievethatthisbookcanbeausefulsimulationresource to readers with backgrounds ranging from an exposure to introductory probabilitytoamuchmoreadvancedknowledgeofthearea.Giventhewide rangeof examplesandapplicationareasaddressed,our expectationis that students,practitioners,andresearchersinstatistics,probability,operations research, economics, finance, engineering, biology, chemistry, and physics willfindthebooktobe ofvalue.Inadditiontoprovidingadevelopmentof the area pertinent to each reader’s specific interests, our hope is that the book also serves to broaden our audience’s view of both Monte Carlo and stochastic modeling, in general. There exists an extensive number of texts on simulation and Monte Carlo methods. Classical general references in the areas covered by this book are (in chronological order) Hammersley & Handscombe [173], Ru- binstein [313], Ripley [300], and Fishman [118]. A number of further ones can be found in the list of references; many of them contain much practi- cally orienteddiscussion not at all coveredby this book. There are further a number of books dealing with special subareas, for example Gilks et al.[129]onMarkovchainMonteCarlomethods,Newman&Barkema[276] on applications to statistical physics, Glasserman [133] on applications to mathematicalfinance,andRubinstein & Kroese[318]onthe cross-entropy method. In addition to standard journals in statistics and applied probability, the readerinterestedinpursuingthe literatureshouldbe awareofjournals like ACM TOMACS (ACM Transactions of Modeling and Computer Sim- ulation), Management Science, and the IEEE journals. Of course, today systematic scans of journals are to a large extent replaced by searches on the web.At the endof the book after the References section,we givesome selected web links, being fully aware that such a list is likely to be out- datedsoon.Theselinksalsopointtosomeimportantrecurrentconferences on simulation, see in particular [w3.14], [w3.16], [w3.17], [w3.20]. The book is designed as a potential teaching and learning vehicle for use in a wide variety of courses. Our expectation is that the appropriate selectionofmaterialwill be highly discipline-dependent, typically covering alargeportionofthematerialinPartAongeneralmethodsandusingthose special topics chapters in Part B that reflect the models most widely used within that discipline. In teaching this material, we view some assignment of computer exercises as being essential to gaining an understanding and intuitionforthematerial.Inteachinggraduatestudentsfromthisbook,one of us (SA) assigns a computer lab of three hours per week to complement lectures oftwo hours per week.Exercises labeled(A) aredesignedfor such Preface vii a computer lab (although whether three hours is sufficient will depend on thestudents,andcertainlysomehomepreparationisneeded).Wehavealso deliberatelychosentonotfocusthe bookonaspecific simulationlanguage orsoftwareenvironment.Giventhebroadrangeofmodelscovered,nosingle programmingenvironmentwouldprovideagooduniversalfit.Wepreferto lettheuserorteachermakethesoftwarechoiceherself.Finally,asamatter of teaching philosophy, we do not believe that programming should take a centralrolein a coursetaught fromthis book. Rather,the focus shouldbe on understanding the intuition underlying the algorithms described here, as well as their strengths and weaknesses. In fact, to avoid a focus on the programming per se, we often hand out pieces of code for parts that are tedious to program but do not involve advanced ideas. Exercises marked (TP) are theoretical problems, highly varying in difficulty. Since the first slow start of the writing of this book in 1999, we have received a large number of useful comments, suggestions, and corrections on earlier version of the manuscript. Thanks go first of all to the large number of students who have endured coping with these early versions. It wouldgo too far to mentionall the colleagueswho havehelped in one way oranother.However,foradetailedreadingoflargerpartsitisapleasureto thank HansjörgAlbrecher,Morten Fenger-Grøn,Pierre L’Ecuyer, Thomas Mikosch, Leonardo Rojas-Nandayapa, and Jan Rosiński. At the technical level,LarsMadsenhelpedwithmanyproblemsthatwerebeyondourLATEX ability. A list of typos will be kept at [w3.1], and we are greatful to be informed of misprints as well as of more serious mistakes and omissions. Aarhus and Stanford Søren Asmussen February 2007 Peter W. Glynn Contents Preface v Notation xii I What This Book Is About 1 1 An Illustrative Example: The Single-Server Queue . . . 1 2 The Monte Carlo Method . . . . . . . . . . . . . . . . 5 3 Second Example: Option Pricing. . . . . . . . . . . . . 6 4 Issues Arising in the Monte Carlo Context . . . . . . . 9 5 Further Examples . . . . . . . . . . . . . . . . . . . . . 13 6 Introductory Exercises . . . . . . . . . . . . . . . . . . 25 Part A: General Methods and Algorithms 29 II Generating Random Objects 30 1 Uniform Random Variables. . . . . . . . . . . . . . . . 30 2 Nonuniform Random Variables. . . . . . . . . . . . . . 36 3 Multivariate Random Variables . . . . . . . . . . . . . 49 4 Simple Stochastic Processes . . . . . . . . . . . . . . . 59 5 Further Selected Random Objects . . . . . . . . . . . . 62 6 Discrete-Event Systems and GSMPs . . . . . . . . . . 65 III Output Analysis 68 1 Normal Confidence Intervals . . . . . . . . . . . . . . . 68 Contents ix 2 Two-Stage and Sequential Procedures . . . . . . . . . . 71 3 Computing Smooth Functions of Expectations . . . . . 73 4 Computing Roots of Equations Defined by Expectations 77 5 Sectioning, Jackknifing, and Bootstrapping . . . . . . . 80 6 Variance/Bias Trade-Off Issues . . . . . . . . . . . . . 86 7 Multivariate Output Analysis . . . . . . . . . . . . . . 88 8 Small-Sample Theory . . . . . . . . . . . . . . . . . . . 90 9 Simulations Driven by Empirical Distributions . . . . . 91 10 The Simulation Budget . . . . . . . . . . . . . . . . . . 93 IV Steady-State Simulation 96 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 96 2 Formulas for the Bias and Variance . . . . . . . . . . . 102 3 Variance Estimation for Stationary Processes . . . . . 104 4 The Regenerative Method . . . . . . . . . . . . . . . . 105 5 The Method of Batch Means . . . . . . . . . . . . . . . 109 6 Further Refinements . . . . . . . . . . . . . . . . . . . 110 7 Duality Representations . . . . . . . . . . . . . . . . . 118 8 Perfect Sampling . . . . . . . . . . . . . . . . . . . . . 120 V Variance-Reduction Methods 126 1 Importance Sampling . . . . . . . . . . . . . . . . . . . 127 2 Control Variates . . . . . . . . . . . . . . . . . . . . . . 138 3 Antithetic Sampling . . . . . . . . . . . . . . . . . . . . 144 4 Conditional Monte Carlo . . . . . . . . . . . . . . . . . 145 5 Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6 Common Random Numbers . . . . . . . . . . . . . . . 149 7 Stratification. . . . . . . . . . . . . . . . . . . . . . . . 150 8 Indirect Estimation . . . . . . . . . . . . . . . . . . . . 155 VI Rare-Event Simulation 158 1 Efficiency Issues . . . . . . . . . . . . . . . . . . . . . . 158 2 Examples of Efficient Algorithms: Light Tails . . . . . 163 3 Examples of Efficient Algorithms: Heavy Tails . . . . . 173 4 Tail Estimation . . . . . . . . . . . . . . . . . . . . . . 178 5 Conditioned Limit Theorems . . . . . . . . . . . . . . . 183 6 Large-Deviations or Optimal-Path Approach . . . . . . 187 7 Markov Chains and the h-Transform . . . . . . . . . . 190 8 Adaptive Importance Sampling via the Cross-Entropy Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 9 Multilevel Splitting . . . . . . . . . . . . . . . . . . . . 201 VII Derivative Estimation 206 1 Finite Differences . . . . . . . . . . . . . . . . . . . . . 209 2 Infinitesimal Perturbation Analysis . . . . . . . . . . . 214