Math 450 - Topics in Applied Mathematics

Random Processes

Spring 2007

Note: You can see me outside the set office hours, but contact me in advance to be sure I'm in.

General Information

Topics. This is an introductory course on stochastic processes that takes a computational approach to the subject, with an emphasis on developing operational skills in modelling random phenomena.

Here are some of the topics we plan to cover:

• Random number generators and statistical tests of randomness;
• Review of basic probability theory: main probability distributions, law of large numbers, central limit theorem, etc.
• Discrete and continuous-time Markov chains with finite number of states;
• Rudiments of Markov Chain Monte Carlo (MCMC) methods.
• Brownian motion and Ito calculus;
• Rudiments of stochastic ODEs and diffusion;
• Assorted applications from physics, mathematical biology, mathematical finance, etc.

Prerequisites. Math 449 or permission of instructor.

Text. There is no single textbook that covers the above topics in the way we plan to approach them. A large part of the theory can be found in the text: Markov Chains, by J.R. Norris. (Cambridge University Press, 1998.) I haven't placed an order for it with the campus bookstore, but I recommend that you buy it. (The paperback edition should cost around $35.) I plan to assign readings from this text and supplement it with notes to be handed out in class, as well as other reading material given on-line. (A list of web sites will be added to the bottom of this page.)

Homework. There will be (roughly) weekly homework assignments. You are encouraged to collaborate on them. Please return your solutions to the instructor by the end of class. Late homeworks will not be accepted. The homework will be judged for correctness and clarity. When the problem requires a computed solution, it must be accompanied by a correct, well-documented computer program which will be judged for its understandability. The homework problems will be posted on the lesson schedule at least a week in advance of its due date. They will also be announced in class.

Essay. You will also write a 5 to 15 typed pages essay about a topic of your choice in any area of the natural or social sciences, engineering, arts, or pure math, whose method of analysis relies on probabilistic modelling. You should have a preliminary write-up ready by the middle of the semester, and a final draft by the end of the semester. The final version will contain an exposition of the topic, with enough background information to convey the nature and interest of the subject to someone not familiar with it, and a numerical case study. You may choose to work individually or do a joint project with one or more classmates.

Computing. Students are encouraged to use MATLAB. It is available on the computers in the Arts and Sciences Computing Center. It does not take that much time to learn to use and program in Matlab for the needs of this course, if you do not have previous experience. Look for Matlab tutorials on-line. Here are two: tutorial 1 and tutorial 2.

Grades. Your grade will be calculated on the basis of homework assignments, the preliminary draft of your essay, and the final article. Each will contribute to the final score according to the following percentages: HW 70%, Prel. Draft 10%, and Final Art. 20%. Students taking the Cr/NCr or P/F options will need a grade of D or better to pass.

Lesson Schedule

The topic of the day, new assignments and solutions, supplementary reading material, as well as occasional news, will be posted below. I will post from time to time lecture notes supplementing the main text. This is a tentative schedule. It will be updated and modified as the course progresses. (For now, most links are inactive.)

January

• 01/17 Lecture Notes 01 - Introduction to probability modeling; Matlab
• 01/19 HW #01, due Friday, 01/26 (Solutions)
• 01/22 Lecture Notes 02 - Probability spaces
• 01/24 Lecture Notes 02
• 01/26 HW #02, due Friday, 02/02 (Solutions)
• 01/29 Lecture Notes 03 - Simulation of standard distributions
• 01/31 Lecture Notes 03

February

• 02/02 HW #03, due Friday, 02/09 (Solutions)
• 02/05 Lecture Notes 03
• 02/07 Lecture Notes 03
• 02/09 HW #04, due Friday, 02/16 (Solutions)
• 02/12 Textbook - section 1.1
• 02/14 Textbook - sections 1.2, 1.3
• 02/16 HW #05, due Friday, 02/23 (Solutions); Textbook - sections 1.4, 1.5
• 02/19 Textbook - sections 1.5, 1.6
• 02/21 Textbook - section 1.6
• 02/23 HW #06, due Friday, 03/02 (Solutions)
• 02/26 Textbook - section 1.7
• 02/28 First draft of essay due.

March

• 03/02 HW #07, due Friday, 03/09 (Solutions)
• 03/05 Notes on card shuffling
• 03/07 Some Matlab programs for Markov chains
• 03/09 HW #08, due Friday, 03/23 (Solutions)
• 03/12 - Spring Break
• 03/14 - Spring Break
• 03/16 - Spring Break
• 03/19 Notes on continuous-time Markov chains. This is needed for HW # 8
• 03/21 Notes and section 2.6 of textbook.
• 03/23 HW #09, due Friday, 03/30 (Solutions) Section 2.8 textbook (mainly theorem 2.8.2.
• 03/26 Sections 3.1-3.4 of textbook.
• 03/28 Sections 3.5-3.6
• 03/30 HW #10, due Friday, 04/06 (Solutions)

April

• 04/02 Notes on stochastic Petri nets.
• 04/04 Notes on stochastic differential equations by Desmond J. Higham.
• 04/06 HW #11, due Friday, 04/13 (Solutions)
• 04/09 Wiener process, section 4.4 of Norris text
• 04/11 Wiener process and stochastic integrals
• 04/13 HW #12, due Monday, 04/23 (Solutions)
• 04/16 Notes on Ito calculus
• 04/18 Stochastic differentials and Ito's formula
• 04/20 Ito calculus and stochastic ODEs
• 04/23 Homework 12 due.
• 04/25 Stochastic ODEs and diffusion
• 04/27 Diffusion processes
• 04/30 - Final draft of essay.

References and sources of project topics

This is a list of bibliographical references. You may want to browse some of these books for inspiration as you try to decide which project topic to choose. More references may be added throughout the course. Of course, you do not have to restrict your choice to what is listed here.

• Computer science, randomized algorithms, combinatorics, MCMC
  1. Finite Markov Chains and Algorithmic Applications, by Olle Haagstrom. London Mathematical Society, Student Texts 52, Cambridge University Press, 2002.
  2. Randomized Algorithms, by R. Motwani and P. Raghavan. Cambridge University Press, 1995.
  3. Algorithms for Random Generation and Counting - A Markov Chain Approach, by Alistair Sinclair. Birkhauser, 1993.
  4. Probability and Computing, by Michael Mitzenmacher and Eli Upfal. Cambridge University Press, 2005.
• Random walks on graphs, electrical networks, discrete harmonic functions
  1. Random Walks and Electrical Networks, by P. Doyle and J.L. Snell. Carus Mathematical Monograph no. 22, Mathematical Association of America, 1984. (Available on-line for free download.)
  2. Uniform Random Spanning Trees, by Robin Pemantle, in Topics in Contemporary Probability and Applications, Ed. J.L. Snell, CRC Press, 1995.
• Games
  1. Some New Games for your Computer, by Rick Durrett, in Topics in Contemporary Probability and Applications, Ed. J.L. Snell, CRC Press, 1995.
  2. Cellular Automata with Errors: Problems for Students of Probability, by Andrei Toom, in Topics in Contemporary Probability and Applications, Ed. J.L. Snell, CRC Press, 1995.
  3. How Many Times Should You Shuffle a Deck of Cards?, by Brad Mann, in Topics in Contemporary Probability and Applications, Ed. J.L. Snell, CRC Press, 1995.
• Random graphs
  1. Random Graphs in Ecology, by Joel E. Cohen, in Topics in Contemporary Probability and Applications, Ed. J.L. Snell, CRC Press, 1995.
  2. A Matrix Perturbation View of the Small World Phenomenon, by D.J. Higham. SIAM J. Matrix Anal. Appl. 2003, Vol. 25, No. 2, pp. 429-444 (available on-line.)
  3. Random Graphs, by B. Bollobas. Academic Press, 1985.
• Chemistry, molecular biology, general biology
  1. Stochastic Modelling for Systems Biology, by Darren J. Wilkinson. CRC, Mathematical and Computational Biology Series, 2006.
  2. Random Walks in Biology, by Howard C. Berg. Princeton U. Press, 1993.
  3. Computational Cell Biology, by C.P. Fall, E.S. Marland, J.M. Wagner, J.J. Tyson (editors). IAM volume 20 - Mathematical Biology, Springer-Verlag, 2002 (corrected third print, 2005).
  4. Branching processes in biology, by M. Kimmel and D.E. Axelrod. Springer, 2202.
  5. Evolutionary dynamics - exploring the equations of life, by M.A. Nowak. Belknap/Harvard, 2006.
• Physics, engineering.
  1. Stochastic Tools in Mathematics and Science, by A.J. Chorin and O.H. Hald. Springer, 2006.
  2. Theory and Applications of Stochastic Differential Equations, by Z. Schuss. John Wiley, 1980.
  3. Stochastic Differential Equations in Science and Engineering, by D. Henderson and P. Plaschko. World Scientific, 2006.
• Mathematical Finance
1. Black-Scholes Option Valuation for Scientific Computing Students, by Desmond J. Higham, January, 2004. (Available on-line for free download.)
2. An Introduction to Financial Option Valuation, by D.J. Higham. Cambridge University Press, 2004
• Operations research, management science, queueing processes
  1. Stochastic Modeling - Analysis and Simulation, by B.L. Nelson. Dover, 1995.
  2. An Introduction to Stochastic Processes, by Edward P.C. Kao. Duxbury Press, 1996.
• Probabilistic methods for music theory and analysis of music signals
  1. Music and Probability, by David Temperley. MIT Press, 2007.
  2. Bayesian Methods for Music Signal Analysis, by A. Taylan Cemgil. (Look for PDF file on the web.)
• Various applications
  1. Topics in Contemporary Probability and its Applications, Ed. J. Laurie Snell. CRC Press, 1995.
  2. Markov Chains - Gibbs Fields, Monte Carlo Simulation, and Queues, by Pierre Bremaud. Springer-Verlag, 1999.
  3. Numerical Solution of Stochastic Differential Equations, by P.E. Kloeden and E. Platen. Applications of Mathematics, volume 23, Springer-Verlag, 1994.
  4. Lectures on Contemporary Probability, by G.F. Lawler and L.N. Coyle. American Math. Society and Institute for Advanced Study, 1999.