Rubinstein Reuven Y. - Simulation and the Monte Carlo Method

Copyright 2017 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, (978) 750-8400, fax (978) 750-4470, 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, (201) 748-6011, fax (201) 748-6008, 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 (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

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

Library of Congress Cataloging-in-Publication Data:

Names: Rubinstein, Reuven Y. | Kroese, Dirk P.

Title: Simulation and the Monte Carlo method.

Description: Third edition / Reuven Rubinstein, Dirk P. Kroese. | Hoboken,
New Jersey: John Wiley & Sons, Inc., [2017] | Series: Wiley series in
probability and statistics | Includes bibliographical references and index.

Identifiers: LCCN 2016020742 (print) | LCCN 2016023293 (ebook) | ISBN
9781118632161 (cloth) | ISBN 9781118632208 (pdf) | ISBN 9781118632383
(epub)

Subjects: LCSH: Monte Carlo method. | Digital computer simulation. |
Mathematical statistics. | Sampling (Statistics) Classification: LCC QA298 .R8 2017 (print) | LCC QA298 (ebook) | DDC
518/.282--dc23

LC record available at https://lccn.loc.gov/2016020742

To the memory of
Reuven Y. Rubinstein (19382012)

Reuven Rubinstein passed away during the writing of this third edition. Reuven was one of the pioneers of Monte Carlo simulation and remained at the forefront of research in this area right up to the end of his life. In 2011 he received the highest honor given by INFORMS Simulation Society: The Lifetime Professional Achievement Award, where his achievements were summarized as follows:

Professor Rubinstein has been a pivotal figure in the theory and practice of simulation as we know it today. His career reflects a high level of creativity and contribution, with a willingness to explore new areas and an amazing ability to suggest surprising new avenues of research and to influence subsequent work.

May his contagious enthusiasm and curiosity live on through his books and the many people whom he inspired.

Dirk P. Kroese

Since the publication in 2008 of the second edition of Simulation and the Monte Carlo Method, significant changes have taken place in the field of Monte Carlo simulation. This third 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 last five years. It is aimed at a broad audience of students in engineering, physical and life sciences, statistics, computer science, mathematics, and simply anyone interested in using Monte Carlo simulation in their study or work. Our aim is to provide an accessible introduction to modern 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 background, such as an elementary course in probability and statistics, we nevertheless review the basic concepts of probability, stochastic processes, information theory, and convex optimization in .

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. 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 that causes the system to change from one state to another. We discuss how to model such systems on a computer in .

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

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. 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 the cross-entropy methods. Special attention is paid to importance sampling algorithms in which paths are generated in a sequential manner. Further improvements of such algorithms are obtained by resampling successful paths, giving rise to sequential importance resampling algorithms. We illustrate their use via a nonlinear filtering example. 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 importance sampling estimators, whereas 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 results, the accuracy of the importance sampling estimator increases substantially.