Math 833: Stochastic simulation and Monte Carlo methods

Spring 2017

Meetings: 9:30-10:45am, Tuesdays and Thursdays, Van Vleck B135
Instructor: David Anderson
Office: 617 Van Vleck.
Office Hours: 10:45 - 11:45am on Tuesdays, and by appointment.
E-mail:anderson@math.wisc.edu

This is the course homepage that also serves as the syllabus for the course. Here you will find our weekly schedule, and updates on scheduling matters.

I will use the class email list to send out corrections, announcements, etc.  Please check your wisc.edu email regularly.

Course description

In this topics course we will cover a broad range of topics related to stochastic simulation and Monte Carlo methods.  The current list of topics I plan on covering are the following.
  1. Brief review of probability theory.
  2. Basics of Monte Carlo: the law of large numbers and the central limit theorem.
  3. Simulation of random variables.
  4. Simulation of stochastic processes: discrete and continuous time Markov chains, and SDEs driven by Brownian motions.
  5. Simulation of stochastic models in biochemistry.
  6. Error analysis for SDEs -- numerical analysis.
  7. Variance reduction in Monte Carlo.
  8. Importance sampling.
  9. Derivative estimation (parametric sensitivity analysis).
  10. Multilevel Monte Carlo.
  11. Steady state estimation.
  12. Markov chain Monte Carlo.
  13. (Maybe) Quasi-Monte Carlo.
  14. More TBD -- email me if there is a particular topic you want to hear about!

By the end of the course, you should have a toolbox.  However, you will need to bridge the gap to specific applications.

Prerequisites

A knowledge of probability theory up to an advanced undergraduate level.  Familiarity with Markov chains is helpful, but I will review what we need.  Ability to program in a language suitable for scientific computing, e.g., Matlab, R, Python, C, Fortan, Julia, .....  I will not teach particular computer languages and packages.  I will personally use Matlab, and can help you in that language if need be.

Textbook

There will be no official textbook for the course, as no single book has all the material I want to cover.  Instead, I will lecture based off several sources.  I will post my lecture notes (as much as possible, at least) on our learn@UW website.

Here are some references that you can get for free through our library:
I have also placed a number of texts on reserve at the math library (floor B2 of Van Vleck):

Here are some other useful links for texts on probability theory and stochastic processes:

Evaluation

Course grades will be based on homework (50%) and a course project (50%). 

More on the projects.  Your project must be developed in consultation with me.  The project can be based on (i) a published paper of interest that you delve into (could be either methodological or application driven), or (ii) the application of the topics covered in the course to some aspect of your graduate project (if you have one).   The project will involve both a written report/paper and a presentation to the class (probably lasting for around 15 minutes).  I will consider group projects for larger topics.

Here is a note with some project ideas that will be updated periodically. 

Inclusiveness statement. 

As a diverse group, the Mathematics Department strives to foster an open and supportive community in which to conduct research, to teach, and to learn.  In accordance with these beliefs and section 36.12 of the Wisconsin Statutes, the Mathematics Department affirms that all community members are to be treated with dignity and respect and that discrimination and harassment will not be tolerated.  We further commit ourselves to making the department a supportive, inclusive, and safe environment for all students, faculty, staff, and visitors, regardless of race, religion, national origin, sexual orientation, gender identity, disability, age, pregnancy, or any other aspect of identity.  For more information, refer to http://www.math.wisc.edu/climate.

Daily schedule

I am of the mind that people can not focus for 75 minutes.  Thus, on lecture days I will try to break up the class   into two chunks of approximately 35 minutes each. 

Weekly schedule

Here is a tentative weekly schedule, to be adjusted as we go. I expect that the schedule will undergo dramatic change as the semester proceeds.

Week
 Tuesday
 Thursday
1 1/17 & 1/19
 Introduction to this course.
Review of probability theory.
 Law of large numbers and central limit theorem.
Confidence intervals.
Beginnings of Monte Carlo.
2 1/24 & 1/26
 Estimating quantiles
Generation of non-uniform random variables 		Generation of non-uniform random variables
3 1/31 & 2/2
 Finish acceptance-rejection
Basic variance reduction methods for Monte Carlo: antithetic sampling
 Basic variance reduction methods for Monte Carlo: control variates
4 2/7 & 2/9
 Basic variance reduction methods for Monte Carlo:
stratified sampling and conditioning.
 Crash course on discrete time Markov chains: definitions, simulation, ergodicity.
5 2/14 & 2/16
 Point processes and CTMCs -- slides.
 No class. 
6 2/21 & 23
 Finish generator for CTMCs.
Biochemical processes and simulation:
Gillespie algorithm.
 Classical scaling: LLN for chemical systems.
Exact simulation of models - next reaction method.
7 2/28 & 3/2
 Exact simulation for time-dependent intensity functions.
tau-leaping and variants.
 tau-leaping and variants.
Brownian motion and SDEs
Error analysis of Euler-Maruyama: strong and weak.
8 3/7 & 3/9
 No class. 
Error analysis of Euler-Maruyama: strong and weak.
9 3/14 & 3/16
 Error analysis of Euler-Maruyama:  weak error.
Mean-square error with Euler-Maruyama.
 Richardson extrapolation with Euler-Maruyama.
multi-level Monte Carlo for SDEs: read Giles's 2008 paper.
10 3/28 & 3/30
 Milstein Scheme.
Glynn/Rhee paper: new approach to unbiased estimation for SDEs
 Glynn/Rhee paper: new approach to unbiased estimation for SDEs
Error analysis for tau-leaping: why use the classical scaling?
11 4/4 & 4/6
 strong, L1 and L2, analysis of tau-leaping in the classical scaling
 L2 analysis.
Complexity of different methods for estimation with jump processes (including MLMC)
12 4/11 & 13
 Sensitivity analysis basics: LR, IPA, FD for RVs. Sensitivity analysis basics: LR, IPA, FD for RVs and DTMCs
13 4/18 & 4/20
 Project presentation.
1.  Jim Brunner.
2.  Yu Sun.

Also: sensitivities for biochemical processes -- Likelihood ratios.
 Project presentation.
1.  Brandon Legried.
2.  Adrian Tovar.

Also: sensitivities for biochemical processes -- pathwise differentiation.
14 4/25 & 4/27
 Project presentation.
1.  Muhong Gao
2.  Tianli Wang
3.  David Marsico
4. Kurt Ehlert and Jinsu Kim
 Project presentations.
1.  Yujia Bao
2.  Hans Chaumont
3.  Di Fang and Ke Chen
4.  Thomas Edwards
HW 3 Due.
15 5/2 & 5/4
 Project presentations.
1.  Adrian Lopez
2.  Keith Dsouza and Chris Breeden
3.  Junda Sheng
4.  Liban Mohamed
5. Yeon-Eung Kim
 Project presentation.
1.  Tung Nguyen
2.  Chaojie Yuan and Hanqing Lu
3.  Jason Wang
4. Shuoyang Wang