What are Monte Carlo Methods?:
Monte Carlo methods are numerical methods that use random numbers to compute quantities of interest. This is normally done by creating a random variable whose expected value is the desired quantity. One then simulates and tabulates the random variable and uses its sample mean and variance to construct probabilistic estimates.
Purpose of the Course:
This course presents the fundamentals of the Monte Carlo method, or as it was originally known, the "method of statistical sampling." This course is meant to take mathematically and computationally mature students and given them a very comprehensive introduction to Monte Carlo methods. The material in this course focuses on:
Developing the mathematical background required for understanding and developing Monte Carlo methods. This is primarily probability theory, statistics, the theory of stochastic processes, and connections with functional analysis.
Examining Monte Carlo methods from the point-of-view of numerical methods and computing. It should be recalled that Monte Carlo methods developed considerably at the down of the age of electronic computing, and they have blossomed since as potent computational techniques.
Reflecting on Monte Carlo methods through specific applications. There are few areas of science and technology where Monte Carlo methods are not used, and understanding how they are used in applications, with an eye on cross-domain fertilization, is a very important way to motivate and reinforce interest in Monte Carlo Methods.
By combining the theoretical background, with the computational approach firmly anchored in applications, the Monte Carlo method can be used to solve many problems that traditional deterministic methods cannot. In addition, there are a wide number of areas where both Monte Carlo and deterministic methods can be used, where the Monte Carlo approach offers a very attractive alternative. Thus, Monte Carlo methods themselves are a fruitful source of research problems, and when combined with deterministic methods have the promise to provide many improved numerical methods.
Secondary Purpose of the Course:
The hope is that the process of teaching this course will produce a set of course notes that can be crafted into a good, intermediate to advanced textbook on Monte Carlo methods. Thus, I expect to ask some things of the students that are going to be a bit out of the norm for students in a typical applied mathematics class.
Course Poster:
Please click here to download a PDF version of a poster announcing this class. Note, the background image on this poster is related to Monte Carlo methods as follows. When one wishes to know how uniform a random number generator is, one computes a quantity called the discrepancy. The background image is the local discrepancy of a particular quasirandom sequence produced by Dr. Karl Entacher of Universität Salzburg.
Book References:
Unfortunately, there is no good, comprehensive Monte Carlo textbook. In fact, the hope is that the material used to teach this course will become such a comprehensive Monte Carlo Methods textbook. However, there are good books that are general references for Monte Carlo:
J. M. Hammersley and D. C. Handscomb, Monte Carlo Methods, Chapman and Hall, London & New York, 1964.
This book is my favorite, as it is short, and provides a very readable overview of Monte Carlo as it stood in 1964. Remarkably, the theoretical foundations remain rather similar, the main differences are that the applications are much more sophisticated today. Thus, much of the first part of the course will be based on this text. Unfortunately, it is out of print, and no longer available. However, a PDF version of the book can be downloaded here.
M. H. Kalos and P. A. Whitlock, Monte Carlo Methods, Volume I: Basics, Wiley-Interscience Publications, John Wiley and Sons, New York, 1986.
Kalos and Whitlock is a nice companion to Hammersley and Handscomb. It covers much of the same basic material, but it also has more up-to-date applications, including Green's Function Monte Carlo. I know both of the authors well, and have asked them on many occasions when further volumes will be coming out. Since this volume is almost 20 years old, I think it is safe to assume there will be no other volumes. This further motivates the need for a new Monte Carlo textbook.
R. Y. Rubenstein, Simulation and the Monte Carlo Method, Wiley Series in Probability and Mathematical Statistics, John Wiley and Sons, New York, 1981.
This book, while old, covers many of the statistical aspects of Monte Carlo, and focuses on industrial optimizations.
K. K. Sabelfeld, Monte Carlo Methods in Boundary Value Problems, Springer-Verlag, Berlin, Heidelberg, New York, 1991.
This book is a very comprehensive treatment for Monte Carlo methods applied to boundary-value problems associated with integral equations and partial differential equations. It is a translation, from the Russian, and can be somewhat difficult, as the mathematical terminology and general mathematical context is very Soviet. However, this is a great book, and Karl Sabelfeld is a collaborator and friend.
M. Freidlin, Functional Integration and Partial Differential Equations, Annals of Mathematical Studies #109, Princeton University Press, Princeton, NJ, 1985.
Another translation from the Russian. However, this book is a very comprehensive research monograph on the probabilistic representation of partial differential equations. While somewhat Soviet in style, this book is encyclopedic in its nature, and has a keen mathematical elegance to it.
D. E. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, Third Edition, Addison Wesley, Reading, MA, 1998.
The first section, pages 1-193, is a comprehensive introduction to random number generation, and statistical and theoretical testing of random numbers. This is holy scripture in the random number generation literature, and we will be spending a significant part of the course on uniform and nonuniform random number generation.
K. L. Chung, Markov Chains with Stationary Transition Probabilities, Second Edition, Springer-Verlag, Berlin, New York, Heidelberg, 1967.
This book is the standard reference for the mathematical theory of Markov chains. In addition to this book, Kai Lai Chung has written many very good textbooks on probability theory, stochastic processes, and the relationship between partial differential equations and probability.
B. A. Berg, Markov Chain Monte Carlo Simulations and Their Statistical Analysis, World Scientific Publishers, Singapore, 2004.
This book is a good introduction to Markov Chain Monte Carlo (MCMC), especially as applied to Statistical Physics. Also, the author is a colleague and friend. Note, we currently do not have a module in the course on MCMC scheduled. However, time permitting, we should try to cover this subject.
L. Devroye, Nonuniform Variate Generation, Springer-Verlag, Berlin, Heidelberg, New York, 1986.
This is the standard reference on the production of nonuniform random numbers. The assumptions are that "easy" distributions, like U[0,1), are readily available, and this book deals with the myriad number of ways to transform the easy random numbers into anything else you might want. Luc Devroye has posted this book on the web here, and we have made the book available as a single PDF document here.
W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes, Cambridge University Press, Cambridge, New York, Port Chester, Melbourne, Sydney, 1992.
This is a standard "cookbook" of numerical procedures, and the authors have made the various books, Numerical Recipes in C, Numerical Recipes in Fortran 77 and Numerical Recipes in Fortran 90 available online. The books are divided up into numerous PDF files, one per book section where each chapter has many sections. A good link for these is here.
M. Kac, Some Stochastic Problems in Physics and Mathematics, Colloquium Lectures in the Pure and Applied Sciences, Field Research Laboratory, Socony Mobil Oil Company, Inc., 1956.
These notes were transcribed from notes and recordings made by a participant in the lecture series presented at the Socony Mobil Oil Field Research Laboratory in 1956 by Mark Kac in Dallas, TX. These lectures were the second in the "Colloquium Lectures in the Pure and Applied Sciences" series. These notes are very rare, and there may not be a hard bound copy of these notes anywhere outside the US. Many of the topics that appear in the Lezioni Fermiane, and other of Mark Kac's more famous work appears here. This is, for example, the first place that Kac's stochastic version telegrapher's equation is written up. A PDF file with these notes can be found here.
M. Kac, Integration in Function Space and some of Its Applications, Lezioni Fermiane, Accademia Nazionale dei Lincei, Scuola Normale Superiore, Pisa, Italy, 1980.
This book has a very nice introduction to functional integration and its relationship to partial differential equations via the Feynman-Kac formula. In addition, it provides introductory material on probability and measure theory as they relate to the theory of Brownian motion. The book is no longer in print, but a PDF version of the book can be downloaded here.
Research Paper References:
Review Papers
W. F. Bauer, "The Monte Carlo Method," Journal of the Society for Industrial and Applied Mathematics, 6(4): 438-451, 1958. This is a review paper that provides an interesting perspective from 1958. This paper can be found here.
J. H. Halton, "A Retrospective and Prospective Survey of the Monte Carlo Method," SIAM Review, 12(1): 1-63, 1970. This paper is a very comprehensive review of Monte Carlo methods in 1970. Of particular interest is the thorough job done on linear algebra. This paper can be found here.
Monte Carlo Linear Algebra
G. E. Forsythe and R. A. Leibler, "Matrix Inversion by a Monte Carlo Method," Mathematical Tables and Other Aids to Computation, 4(31): 127-9, 1950. This paper presents the Ulam and von Neumann method for solving a linear system, which was never published in the open literature by the originators of the method. The journal Mathematical Tables and Other Aids to Computation is still published by the American Mathematical Society as Mathematics of Computation. This paper can be found here.
J. H. Curtiss, "Monte Carlo Methods for the Iteration of Linear Operators," Journal of Mathematics and Physics, 32: 209-232, 1953. This paper gives a good overview of Monte Carlo methods for iterating linear operators. These methods can be used for various fundamental problems in numerical linear algebra as well as the solution of problems amenable to solution via Picard iteration. This paper can be found here.
J. H. Curtiss, "A Theoretical Comparison of the Efficiencies of Two Classical Methods and a Monte Carlo Method for Computing one Component of the Solution of a Set of Linear Algebraic Equations," in H. A. Meyer, editor, Symposium on Monte Carlo Methods, pp. 191-233. Wiley, New York, 1954. This paper is a comprehensive comparison of deterministic to Monte Carlo methods for solving linear equations. These results are dated, but the paper is strong both theoretically and experimentally, and begs for a modern revision. This paper can be found here.
J. H. Halton, "A Retrospective and Prospective Survey of the Monte Carlo Method," SIAM Review, 12(1): 1-63, 1970. This paper is a very comprehensive review of Monte Carlo methods in 1970. Of particular interest is the thorough job done on linear algebra. This paper can be found here.
W. R. Wasow, "A Note on the Inversion of Matrices by Random Walks," Mathematical Tables and Other Aids to Computation, 6(38): 78-81, 1952. This paper presents Wasow's variance reduction enhancement to the Ulam and von Neumann method for solving a linear system. The journal Mathematical Tables and Other Aids to Computation is still published by the American Mathematical Society as Mathematics of Computation. This paper can be found here.
Monte Carlo for Partial Differential and Integral Equations
R. Courant, K. Friedrichs, and H. Lewy, "Über die Partiellen Differenzengleichungen der Mathematischen Physik," Mathematische Annalen, 100: 32-74, 1928. This paper proves many fundamental properties of the solutions of elliptic, parabolic, and hyperbolic partial differential equations by rigorously analyzing their difference equations. Of particular importance to students of Monte Carlo methods is that they discuss the solution of the difference approximations for elliptic and parabolic equations through probabilistic methods. It should be a great source of pride to students of Monte Carlo methods that the seminal paper on the numerical analysis of finite difference equations for partial differential equations presents Monte Carlo solutions of the same! This paper was translated into English as the article "On the Partial Difference Equations of Mathematical Physics," IBM J. Res. Develop., 11: 215–234, 1967. The English translation as it appeared in the IBM Journal of Research and Development in 1967 can be found here, although I am sure many of you can read it in the original German.
M. E. Muller, "Some Continuous Monte Carlo Methods for the Dirichlet Problem," The Annals of Mathematical Statistics, 27(3): 569-589, 1956. This paper presents the Ulam and von Neumann method for solving a linear system, which was never published in the open literature by the originators of the method. This paper can be found here.
M. Kac, "Can one hear the shape of a drum?" The American Mathematical Monthly, 73: 1-23, 1966. This is a classic exposition on the question of whether complete knowledge of the spectrum of the Laplacian for a domain in two-dimensions completely determines its shape. The answer is no, and was not solved by this paper. However, this paper uses many techniques to answer it, partially. For our purposes, it uses stochastic techniques related to probabilistic representations of solutions to elliptic PDEs. This paper is famous as it was the basis of Kac's being awarded the The Mathematical Association of America's (MAA) Chauvenet Prize. The Chauvenet Prize is awarded to the author of an outstanding expository article on a mathematical topic by a member of the MAA. The paper can be found here.
M. Kac, "A Stochastic Model Related to the Telegrapher's Equation" Rocky Mountain Journal of Mathematics, 4(3): 497-509, 1974. This paper is a reprint of a section of Kac's notes that appeared in the Magnolia Petroleum Company Colloquium Lectures in Pure and Applied Sciences, no. 2, October, 1956. This paper gives the derivation of a stochastic process which leads to the telegrapher's equation. The paper starts with the wave equation, and adds a stochastic component to it which converts the equation from purely hyperbolic to the weakly but unmistakably parabolic telegrapher's equation. The paper can be found here.
H. P. McKean, Jr., "Application of Brownian Motion to the Equation of Kolmogorov-Petrovskii-Piskunov" Communications on Pure and Applied Mathematics, XXVIII: 323-331, 1975. This paper presents the branching Brownian motion representation to the solution of the KPP equation. This theory forms the basis for more general Monte Carlo approaches to nonlinear problems. The paper can be found here.
Stochastic Processes:
M. Kac, "Random Walk and the Theory of Brownian Motion," The American Mathematical Monthly, 54(7): 369-391, 1947. This paper is by Mark Kac of the Feynman-Kac formula. It deals with the relationship with Brownian motion, which is a continuous stochastic process, and random walk on discrete grids. The connections are made using exact mathematical treatment of the discrete random walks and using rather simple mathematical ideas to show how deep these connections are. Mark Kac is one of the best mathematical expositors, and this early paper of his is certainly noteworthy in this regard. It can be found here.
Quasi-Monte Carlo Methods:
R. E. Caflisch, "Monte Carlo and Quasi-Monte Carlo Methods," Acta Numerica, 7: 1-49, 1998. This paper gives a nice introduction to quasi-Monte Carlo methods. In addition, it provides a very simple, and hence easy to follow proof of the Koksma-Hlawka inequality. It can be found here.
Lecture Notes:
Lecture notes for the class can be downloaded at the following page.
Meeting Times/Places:
Thursdays (Lecture): 8:15-10:00, HG G26.1
Tuesdays (Discussion and Lecture Makeup): 13:15-14:00, HG G26.5, this class
period will meet only when announced
Prerequisites:
This course is open to upper-level undergraduates and graduate students in Mathematics and Computer Science (Informatik) at ETH. It is also appropriate for graduate students in Physics or Engineering that are using Monte Carlo methods in their work. The course attempts to be self contained, but starts from the assumption that all the students have a basic undergraduate continuous mathematics background. This should include the Calculus, Linear Algebra, Ordinary and Partial Differential Equations, and Advanced Calculus. While not necessary, it might be good to know some Functional Analysis and Numerical Analysis. Students should also be able to compute.
Instructor:
Michael Mascagni, Ph.D.
Gastprofessor, Seminar für Angewandte Mathematik
Eidgenössische Technische Hochschule
CH-8092 Zürich, Switzerland
E-mail: mascagni@math.ethz.ch
Office: HG G68.1
Telephone: +41.(0)44.632.8587, but e-mail me, don't call
AND
Professor of Computer Science
Courtesy Professor of Mathematics and Chemical Engineering
Faculty Associate, School of Computational Science
Florida State University
Tallahassee, FL 32306-4530
E-mail: mascagni@fsu.edu
Office: Dirac Science Library 430/Love 172
Telephone: +1.850.644.3290
For the curious, here are links to a brief biography of the Professor, and the Professor's home page.
Course Assistant (and a Student in the Class as Well):
Christian Perret, SAM/ETHZ, e-mail: cperret@math.ethz.ch
Office Hours:
I am an early bird, and hence I get in around 6:30 each morning. I eat lunch at home, and usually leave for the day at 17:00. Feel free to drop in, but it is almost always best to e-mail to set up an appointment.
Warning and Encouragement:
The students are warned that by taking this course they are implicitly submitting themselves in the role of instructional "Guinea Pigs." As such, your constant input is not only permitted, but strongly encouraged. Feel free to speak up in class, to visit me in my office with your opinions and criticisms, or to e-mail me with ideas on how to improve this class. Also, if something is not clear to you in class, it is very likely unclear to others. So, students are encouraged to interrupt the lectures and ask questions and to come to see me out of class for clarification.
Grading Policy:
The grade for this class will be based on a project, and an oral examination. The project will be selected by the student with the approval of the instructor, and will be the equivalent of a substantial term paper at the end. The examination will be over material selected from the course by the student with the consent of the instructor.
Outline of the Course:
A tentative outline of the course can be found here.
Extra Material, Look Here for Recent Additions: