Math 350 - Fall 2012

Section Information

Section	Time	Location	Instructor	Office Hours (Cupples I, Room 17)
1	Mon Wed Fri 1:00PM - 2:00PM	Cupples I, 199	Renato Feres	Tue Thu 12:00PM - 2:00PM

Please include Math 350 in the subject line of any email message that pertains to this course. It will help avoid accidental deletion of your still unread message. My e-mail address is feres@math.wustl.edu.

Topics

Real phenomena are often described mathematically by probabilistic models such as Markov chains, diffusion processes, and other related stochastic processes. This course is an introduction to techniques for the analysis of probabilistic models by use of numerical simulation. Course work will involve both theoretical and computer assignments. Prerequisite: Math 233 and Math 309. Familiarity with basic concepts in probability and statistics at the level of Math 2200 is strongly recommended.

Topics:

Elements of probability;
Generation of random numbers and discrete and continuous random variables;
Statistical analysis of simulated data;
Introduction to Markov chain Monte Carlo methods;
Additional topics as time permits.

Text

Explorations in Monte Carlo Methods by Ronald W. Shonkwiler and Franklin Mendivil, Springer (2009).

Homework and Grading Information

Our plan is to have 11 homework assignments, of which the worst score will be dropped. In addition, there will be one mid-semester term paper, due October 17, and a final project, due no later than December 19. The term paper will consist of a "research proposal" for a topic you will develop in the final project, involving an application of the stochastic methods studied in the course. We will have much more to say about the project in class.

Let H, M, and F be the scores, out of 100 points, of the homework assignments, mid-semester paper and final project, respectively. Then the total score is

S = 0.70H + 0.10M + 0.20*F.

The value of S will be translated into a letter grade of A, B, C, D, F (with plus and minus shadings to be decided later) in a way that is not stricter than the following table:

Numerical Range	Letter Grade
[90,100]	A-, A, A+
[75,90)	B-, B, B+
[60-75)	C-, C, C+
[50-60)	D
[0,50)	NCR (F)

Course plan

Week	Chapter/Section	Assignments and reading
Aug 29 - Aug 31 8/29 8/31	Chapter 1	Do Assignment 00 on getting started with Matlab. (It won't be collected and is not for grade.) Read pages 1 to 9 of the textbook. Try to understand and execute the simple programs on pages 4, 6, and 9.
Sept 03 - Sept 07 9/3 (Labor Day) 9/5 9/7	Chapter 1	This write-up has a list of useful Matlab functions related to random numbers and histograms: Random Numbers in Matlab. Homework 1 due 9/07 Solutions (9/14)
Sept 10 - Sept 14 9/10 9/12 9/14	Chapter 1/2	Homework 2 due 9/14 Solutions (9/21)
Sept 19 - Sept 23 9/17 9/19 9/21	Chapter 2	Lecture notes on random variables. Homework 3 due 9/21 Solutions (9/28)
Sept 24 - Sept 28 9/24 9/26 9/28 Homework: 9/28	Chapter 2	Homework 4 due 9/28 Solutions (10/05)
Oct 01 - Oct 05 10/1 10/3 10/5 Homework: 10/05	Chapter 2/3	Homework 5 due 10/05 Solutions (10/17)
Oct 8 - Oct 12 10/8 10/10 10/12 Homework: 10/12	Chapter 3	Homework 6 due 10/12 Solutions (10/17)
Oct 15 - Oct 19 10/15 10/17 MID-SEMESTER PAPER 10/19 (Fall break)	Chapter 3
Oct 22 - Oct 26 10/22 10/24 10/26 Homework: 10/26	Chapter 3	Homework 7 due 10/31 Solutions (11/05)
Oct 29 - Nov 02 10/29 10/31 11/02 (no class today)	Chapter 3	Homework 8 due 11/12 Solutions (11/12)
Nov 05 - Nov 9 11/5 11/7 11/9 Homework: 11/9	Chapter 4	Homework 9 due 11/19 Solutions (11/19)
Nov 12 - Nov 16 11/12 11/14 11/16 Homework: 11/19	Chapter 4
Nov 19 - Nov 23 11/19 11/21 (Thanksgiving) 11/23 (Thanksgiving)	Chapter 5	Homework 10 due 11/19 Solutions (11/30) Ising model animation, courtesy of Will Gooding.
Nov 26 - Nov 30 11/26 11/28 11/30 Homework: 11/30	Chapter 5	Homework 11 due 12/07 Solutions (12/07)
Dec 03 - Dec 07 12/3 12/5 12/7 Homework: 12/07	Chapter 5
December 19 FINAL PROJECT DUE

End of the semester paper and research project

Here is a selection of papers on MCMC from which we may take for class discussion. I found them through a random search on-line. If you do your own search you will find a large number of tutorials, lecture notes, as well as videos of lectures on the topic. There is also a large number of texts on MCMC that you can find at the Olin library (they are typically at a more advanced level than our textbook, but you don't need to understand everything in order to find useful information even in the most advanced texts.)

Take a look at some of the below links and other sources as you think about your research project. If any of the links is not accessible to you, do an on-line search with the titles and authors, and you will likely find alternative working links. Wikipedia is also a very good source of information.

The Markov Chain Monte Carlo Revolution by Persi Diaconis.
The Evolution of Markov Chain Monte Carlo Methods by Matthew Richey.
Markov Chain Monte Carlo Method and Its Application by Stephen P. Brooks.
An Introduction to MCMC for Machine Learning by C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jordan.

It is completely open to you what kind of project to undertake, both in theme and form. Here are some possibilities:

An exposition based on a research paper you found. Your work would then contain some background information about the subject, a description of the problem and how the Monte Carlo methods we learned in class or other methods you found on your own can be used, and a computer simulation work to illustrate the subject. I envision a paper about 10 pages long including graphs, but it could be shorter or longer than that.
Although we are not emphasizing statistical applications in this course, much of the use of MCMC is in the analysis of data. Your work could revolve around some real, as opposed to simulated, data.
Possible subjects can come from the sciences, engineering, games, arts, etc. Depending on the subject, an ordinary research paper format may not be most appropriate. For example, you mind be interested in exploring the possibilities of Monte Carlo methods for music composition, in which case you can present the result of your research as a recording, or as a concert to the class at the end of the semester. There are also interesting possibilities for exploration in the visual arts.
Your project could consist of writing a tutorial on some specialized software for MCMC or other methods, explaining how to use the sofware and illustrating the use with a simple but representative example. There are good open source programs out there such as OpenBugs, R.
The paper does not have to involve only techniques we discuss in class. It could be centered around explaining and illustrating a particular technique. Some examples I have in mind are Bayesian networks, hidden Markov models, stochastic differential equations, stochastic petri nets, etc.
I will add here more information and ideas as they come, including ideas you may come up with that could interest some of your classmates.

Students' projects

Below are some of the final projects developed by the students in the Fall of 2012 (posted with their permissions).

Monte Carlo Simulation of Alzheimer's Disease in the United States: 2010-2060 by Michael Blech.
Simulating Tennis Matches Using Markov Model by Yuval Calev and Nabil Salem.
Application of Monte Carlo Markov Chains to Batting Order Optimization by Evan Engel.
Simulated Annealing by Nathan Germer. Here is a movie demonstration.
Traveling Salespeson Problem and its Application for the Optimum Scheduling by Jinsoo Han.
Ultimate Frisbee by Joshua Levin.
An exploration of HMMs through doodles by Joshua Little.
Discussion of Monte Carlo Simulation in Option Pricing by Y Laurent Liu and Tianyi Shi.
A Gibbs Sampler Method for Maze Generation by Brian Lynch.
Simulated Annealing and the Knapsack Problem by Benjamin Misch.
Iterated Random Functions and Fractal Images by Alex Norton.
Applications of Random Mazes and Graphs Generated via Markov Chain Monte Carlo Methods by Robert Ramirez.
MCMC Applications in Google PageRank by Katie Sauer.
The Use of Single Position Observations in Evaluating Mixing Times of Card Shuffles by Drew Sinha.
A Brief Introduction to Seismic Tomography Through A Few Simulation Experiments by Bowei Zhao.

Mathematics software

Homework assignments will often contain questions requiring the use of mathematical software. The textbook uses Matlab and this is the sofware I am most familiar with. Other programs such as Mathematica, Maple, R, etc., would also work fine, but I may not be able to provide assistance in using them. GNU Octave works essentially identically to Matlab and is free to download. R is also free, and it would be in some respects ideal for the course, so you are encouraged to try it.

Matlab is installed in most PCs in the computer lab at Eads, and I believe in the engineering computers. (Presently, I do not know if it is available at the business school computers.) I do not assume that you are already familiar with it.

Here are some links to information about the free software mentioned above:

GNU Octave. Graphics in Octave are rendered using gnuplot or Grace. It took me a little tinkering to get Octave and gnuplot to work together using information available online (but I'm not very computer savvy.)
An excellent alternative to Matlab is R. It is very easy to install in most plataforms, and it works very much like Matlab, although the commands of some functions can be different. It is especially good for statistics and probability programming, and I thought initial to use it as the default choice for the course. I decided against it as the textbook uses Matlab.
Yet another free program that works very much like Matlab (with very similar syntax and command names) is Scilab. It is very easy to install. (I've only installed these programs on Macs, but on PCs running on Windows or Linux it should be just as easy.)

Renato Feres
feres@math.wustl.edu
Cupples I, Room 17
(314) 935 - 6752 (office phone)

Department of Mathematics
Washington University
Campus Box 1146
Saint Louis
Missouri, 63130 USA.

Last Updated: August 10, 2012

Math 350 - Fall 2012

S = 0.70*H + 0.10*M + 0.20*F.

S = 0.70H + 0.10M + 0.20*F.