Simulation and the Monte Carlo Method E-Book

Reuven Y. Rubinstein

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Probability and Statistics
• Sprache: Englisch

Seitenzahl: 643

Veröffentlichungsjahr: 2011

Beschreibung

This accessible new edition explores the major topics in MonteCarlo simulation Simulation and the Monte Carlo Method, Second Editionreflects the latest developments in the field and presents a fullyupdated and comprehensive account of the major topics that haveemerged in Monte Carlo simulation since the publication of theclassic First Edition over twenty-five years ago. Whilemaintaining its accessible and intuitive approach, this revisededition features a wealth of up-to-date information thatfacilitates a deeper understanding of problem solving across a widearray of subject areas, such as engineering, statistics, computerscience, mathematics, and the physical and life sciences. The book begins with a modernized introduction that addressesthe basic concepts of probability, Markov processes, and convexoptimization. Subsequent chapters discuss the dramatic changes thathave occurred in the field of the Monte Carlo method, with coverageof many modern topics including: * Markov Chain Monte Carlo * Variance reduction techniques such as the transform likelihoodratio method and the screening method * The score function method for sensitivity analysis * The stochastic approximation method and the stochasticcounter-part method for Monte Carlo optimization * The cross-entropy method to rare events estimation andcombinatorial optimization * Application of Monte Carlo techniques for counting problems,with an emphasis on the parametric minimum cross-entropymethod An extensive range of exercises is provided at the end of eachchapter, with more difficult sections and exercises markedaccordingly for advanced readers. A generous sampling of appliedexamples is positioned throughout the book, emphasizing variousareas of application, and a detailed appendix presents anintroduction to exponential families, a discussion of thecomputational complexity of stochastic programming problems, andsample MATLAB programs. Requiring only a basic, introductory knowledge of probabilityand statistics, Simulation and the Monte Carlo Method,Second Edition is an excellent text for upper-undergraduate andbeginning graduate courses in simulation and Monte Carlotechniques. The book also serves as a valuable reference forprofessionals who would like to achieve a more formal understandingof the Monte Carlo method.

Leseprobe

CONTENTS

Preface

Acknowledgments

1 Preliminaries

1.1 Random Experiments

1.2 Conditional Probability and Independence

1.3 Random Variables and Probability Distributions

1.4 Some Important Distributions

1.5 Expectation

1.6 Joint Distributions

1.7 Functions of Random Variables

1.8 Transforms

1.9 Jointly Normal Random Variables

1.10 Limit Theorems

1.11 Poisson Processes

1.12 Markov Processes

1.13 Efficiency of Estimators

1.14 Information

1.15 Convex Optimization and Duality

Problems

References

2 Random Number, Random Variable, and Stochastic Process Generation

2.1 Introduction

2.2 Random Number Generation

2.3 Random Variable Generation

2.4 Generating From Commonly Used Distributions

2.5 Random Vector Generation

2.6 Generating Poisson Processes

2.7 Generating Markov Chains and Markov Jump Processes

2.8 Generating Random Permutations

Problems

References

3 Simulation of Discrete-Event Systems

3.1 Simulation Models

3.2 Simulation Clock and Event List for DEDS

3.3 Discrete-Event Simulation

Problems

References

4 Statistical Analysis of Discrete-Event Systems

4.1 Introduction

4.2 Static Simulation Models

4.3 Dynamic Simulation Models

4.4 The Bootstrap Method

Problems

References

5 Controlling the Variance

5.1 Introduction

5.2 Common and Antithetic Random Variables

5.3 Control Variables

5.4 Conditional Monte Carlo

5.5 Stratified Sampling

5.6 Importance Sampling

5.7 Sequential Importance Sampling

5.8 The Transform Likelihood Ratio Method

5.9 Preventing the Degeneracy of Importance Sampling

Problems

References

6 Markov Chain Monte Carlo

6.1 Introduction

6.2 The Metropolis-Hastings Algorithm

6.3 The Hit-and-Run Sampler

6.4 The Gibbs Sampler

6.5 Ising and Potts Models

6.6 Bayesian Statistics

6.7 * Other Markov Samplers

6.8 Simulated Annealing

6.9 Perfect Sampling

Problems

References

7 Sensitivity Analysis and Monte Carlo Optimization

7.1 Introduction

7.2 The Score Function Method for Sensitivity Analysis of DESS

7.3 Simulation-Based Optimization of DESS

7.4 Sensitivity Analysis of DEDS

Problems

References

8 The Cross-Entropy Method

8.1 Introduction

8.2 Estimation of Rare-Event Probabilities

8.3 The CE Method for Optimization

8.4 The Max-cut Problem

8.5 The Partition Problem

8.6 The Traveling Salesman Problem

8.7 Continuous Optimization

8.8 Noisy Optimization

Problems

References

9 Counting via Monte Carlo

9.1 Counting Problems

9.2 Satisfiability Problem

9.3 The Rare-Event Framework for Counting

9.4 Other Randomized Algorithms for Counting

9.5 MinxEnt and Parametric MinxEnt

9.6 PME for Combinatorial Optimization Problems and Decision Making

9.7 Numerical Results

Problems

References

Appendix

A.1 Cholesky Square Root Method

A.2 Exact Sampling from a Conditional Bernoulli Distribution

A.3 Exponential Families

A.4 Sensitivity Analysis

A.5 A Simple CE Algorithm for Optimizing the Peaks Function

A.6 Discrete-time Kalman Filter

A.7 Bernoulli Disruption Problem

A.8 Complexity of Stochastic Programming Problems

Problems

References

Abbreviations and Acronyms

List of Symbols

Index

THE WILEY BICENTENNIAL-KNOWLEDGE FOR GENERATIONS

ach generation has its unique needs and aspirations. When Charles Wiley first opened his small printing shop in lower Manhattan in 1807, it was a generation of boundless potential searching for an identity. And we were there, helping to define a new American literary tradition. Over half a century later, in the midst of the Second Industrial Revolution, it was a generation focused on building the future. Once again, we were there, supplying the critical scientific, technical, and engineering knowledge that helped frame the world. Throughout the 20th Century, and into the new millennium, nations began to reach out beyond their own borders and a new international community was born. Wiley was there, expanding its operations around the world to enable a global exchange of ideas, opinions, and know-how.

For 200 years, Wiley has been an integral part of each generation's journey, enabling the flow of information and understanding necessary to meet their needs and fulfill their aspirations. Today, bold new technologies are changing the way we live and learn. Wiley will be there, providing you the must-have knowledge you need to imagine new worlds, new possibilities, and new opportunities.

Generations come and go, but you can always count on Wiley to provide you the knowledge you need, when and where you need it!

Copyright © 2008 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic format. For information about Wiley products, visit our web site at www.wiley.com.

Wiley Bicentennial Logo: Richard J. Pacifico

Library of Congress Cataloging-in-Publication Data:

Rubinstein, Reuven Y.Simulation and the monte carlo method. -2nd ed./Reuven Y. Rubinstein.Dirk P. Kroese.p. cm. -(Wiley series in probability and statistics)Includes index.ISBN 978-0-470-17794-5 (cloth: acid-free paper)1. Monte Carlo method. 2. Digital computer simulation. I. Kroese, Dirk P.II. Title.QA298.R8 2008518'.282-dc222007029068

To my friends and colleagues Søren Asmussen and Peter Glynn

-RYR

In memory of my parents Albert and Anna Kroese

-DPK

PREFACE

Since the publication in 1981 of Simulation and the Monte Carlo Method, dramatic changes have taken place in the entire field of Monte Carlo simulation. This long-awaited second edition gives a fully updated and comprehensive account of the major topics in Monte Carlo simulation.

The book is based on an undergraduate course on Monte Carlo methods given at the Israel Institute of Technology (Technion) and the University of Queensland for the past five years. It is aimed at a broad audience of students in engineering, physical and life sciences, statistics, computer science and mathematics, as well as anyone interested in using Monte Carlo simulation in his or her study or work. Our aim is to provide an accessible introduction to modem Monte Carlo methods, focusing on the main concepts while providing a sound foundation for problem solving. For this reason, most ideas are introduced and explained via concrete examples, algorithms, and experiments.

Although we assume that the reader has some basic mathematical knowledge, such as gained from an elementary course in probability and statistics, we nevertheless review the basic concepts of probability, Markov processes, and convex optimization in Chapter 1.

In a typical stochastic simulation, randomness is introduced into simulation models via independent uniformly distributed random variables. These random variables are then used as building blocks to simulate more general stochastic systems. Chapter 2 deals with the generation of such random numbers, random variables, and stochastic processes.

Many real-world complex systems can be modeled as discrete-event systems. Examples of discrete-event systems include traffic systems, flexible manufacturing systems, computer communications systems, inventory systems, production lines, coherent lifetime systems, PERT networks, and flow networks. The behavior of such systems is identified via a sequence of discrete events, which causes the system to change from one state to another. We discuss how to model such systems on a computer in Chapter 3.

Chapter 4 treats the statistical analysis of the output data from static and dynamic models. The main difference is that the former do not evolve in time, while the latter do. For the latter, we distinguish between finite-horizon and steady-state simulation. Two popular methods for estimating steady-state performance measures -the batch means and regenerative methods -are discussed as well.

Chapter 5 deals with variance reduction techniques in Monte Carlo simulation, such as antithetic and common random numbers, control random variables, conditional Monte Carlo, stratified sampling, and importance sampling. The last is the most widely used variance reduction technique. Using importance sampling, one can often achieve substantial (sometimes dramatic) variance reduction, in particular when estimating rare-event probabilities. While dealing with importance sampling we present two alternative approaches, called the variance minimization and cross-entropy methods. In addition, this chapter contains two new importance sampling-based methods, called the transform likelihood ratio method and the screening method for variance reduction. The former presents a simple, convenient, and unifying way of constructing efficient IS estimators, while the latter ensures lowering of the dimensionality of the importance sampling density. This is accomplished by identifying (screening out) the most important (bottleneck) parameters to be used in the importance sampling distribution. As a result, the accuracy of the importance sampling estimator increases substantially.

We present a case study for a high-dimensional complex electric power system and show that without screening the importance sampling estimator, containing hundreds of likelihood ratio terms, would be quite unstable and thus would fail to work. In contrast, when using screening, one obtains an accurate low-dimensional importance sampling estimator.

Chapter 6 gives a concise treatment of the generic Markov chain Monte Carlo (MCMC) method for approximately generating samples from an arbitrary distribution. We discuss the classic Metropolis-Hastings algorithm and the Gibbs sampler. In the former, one simulates a Markov chain such that its stationary distribution coincides with the target distribution, while in the latter, the underlying Markov chain is constructed on the basis of a sequence of conditional distributions. We also deal with applications of MCMC in Bayesian statistics and explain how MCMC is used to sample from the Boltzmann distribution for the Ising and Potts models, which are extensively used in statistical mechanics. Moreover, we show how MCMC is used in the simulated annealing method to find the global minimum of a multiextremal function. Finally, we show that both the Metropolis-Hastings and Gibbs samplers can be viewed as special cases of a general MCMC algorithm and then present two more modifications, namely, the slice and reversible jump samplers.

Chapter 7 focuses on sensitivity analysis and Monte Carlo optimization of simulated systems. Because of their complexity, the performance evaluation of discrete-event systems is usually studied by simulation, and it is often associated with the estimation of the performance function with respect to some controllable parameters. Sensitivity analysis is concerned with evaluating sensitivities (gradients, Hessians, etc.) of the performance function with respect to system parameters. It provides guidance to operational decisions and plays an important role in selecting system parameters that optimize the performance measures. Monte Carlo optimization deals with solving stochastic programs, that is, optimization problems where the objective function and some of the constraints are unknown and need to be obtained via simulation. We deal with sensitivity analysis and optimization of both static and dynamic models. We introduce the celebrated score function method for sensitivity analysis, and two alternative methods for Monte Carlo optimization, the socalled stochastic approximation and stochastic counterpart methods. In particular, in the latter method, we show how, using a single simulation experiment, one can approximate quite accurately the true unknown optimal solution of the original deterministic program.

Chapter 8 deals with the cross-entropy (CE) method, which was introduced by the first author in 1997 as an adaptive algorithm for rare-event estimation using a CE minimization technique. It was soon realized that the underlying ideas had a much wider range of application than just in rare event simulation; they could be readily adapted to tackle quite general combinatorial and multiextremal optimization problems, including many problems associated with learning algorithms and neural computation. We provide a gradual introduction to the CE method and show its elegance and versatility. In particular, we present a general CE algorithm for the estimation of rare-event probabilities and then slightly modify it for solving combinatorial optimization problems. We discuss applications of the CE method to several combinatorial optimization problems, such as the max-cut problem and the traveling salesman problem, and provide supportive numerical results on its effectiveness. Due to its versatility, tractability, and simplicity, the CE method has great potential for a diverse range of new applications, for example in the fields of computational biology, DNA sequence alignment, graph theory, and scheduling. During the past five to six years at least 100 papers have been written on the theory and applications of CE. For more details, see the Web site www.cemethod.org; the book by R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation and Machine Learning (Springer, 2004); or Wikipedia under the name cross-entropy method.

Finally, Chapter 9 deals with difficult counting problems, which occur frequently in many important problems in science, engineering, and mathematics. We show how these problems can be viewed as particular instances of estimation problems and thus can be solved efficiently via Monte Carlo techniques, such as importance sampling and MCMC. We also show how to resolve the "degeneracy" in the likelihood ratio, which typically occurs in high-dimensional counting problems, by introducing a particular modification of the classic MinxEnt method called parametric MinxEnt.

A wide range of problems is provided at the end of each chapter. More difficult sections and problems are marked with an asterisk (*). Additional material, including a brief introduction to exponential families, a discussion on the computational complexity of stochastic programming problems, and sample Matlab programs, is given in the Appendix. This book is accompanied by a detailed solutions manual.

REUVEN RUBINSTEIN AND DIRK KROESE

Haifa and BrisbaneJuly, 2007

ACKNOWLEDGMENTS

We thank all who contributed to this book. Robert Smith and Zelda Zabinski read and provided useful suggestions on Chapter 6. Alex Shapiro kindly provided a detailed account of the complexity of stochastic programming problems (Section A.8). We are grateful to the many undergraduate and graduate students at the Technion and the University of Queensland who helped make this book possible and whose valuable ideas and experiments were extremely encouraging and motivating: Yohai Gat, Uri Dubin, Rostislav Man, Leonid Margolin, Levon Kikinian, Ido Leichter, Andrey Dolgin, Dmitry Lifshitz, Sho Nariai, Ben Roberts, Asrul Sani, Gareth Evans, Grethe Casson, Leesa Wockner, Nick Miller, and Chung Chan. We are especially indebted to Thomas Taimre and Zdravko Botev, who conscientiously worked through the whole manuscript, tried and solved all the exercises and provided exceptional feedback. This book was supported by the Australian Research Council under Grants DP056631 and DP055895.

RYR, DPK