IMPORANT LINKS
Homework assignments and solutions
Prof. Propp's lecture notes (including links to lecture-capture videos)
OVERVIEW
This course will cover some fundamental notions from probability theory and Markov chain theory, focussing mostly on discrete-time processes. Students should have taken a first course in probability, and should feel comfortable with linear algebra. Students lacking this background may be admitted on a case-by-case basis. There will be a computational component of the course, so it will be helpful if students have prior experience using computer algebra systems such as Maple, MATLAB, or Mathematica.
The class will be taught from lecture notes to be made available on-line, and from the following on-line materials:
"Markov Chains" by Charles M. Grinstead and J. Laurie Snell (Chapter 11 of their book Introduction to Probability; if you need a review of discrete probability, read Chapter 1, especially section 1.2, and Chapter 6, especially sections 6.1 and 6.2)
"Markov Chains and Mixing Times" by David Levin, Yuval Peres, and Elizabeth Wilmer (a more recent but incomplete version of the book can be found at David Levin's site for the book)
"Random Walk and Electric Networks" by Peter Doyle and Laurie Snell (also available as a printed book)
"The Nature of Computation" by Cris Moore and Stephan Mertens
"The Stochastic Abacus: A New Approach to Discrete Probability" by Arthur Engel
"The Engel algorithm for absorbing Markov chains" by J. Laurie Snell
Although the stochastic abacus is not at all well known, and many of its properties are still the subject of intense research, it was actually developed in the 1970s as a way to teach probability theory to fourth graders! So the fundamentals are quite simple.
This course will serve as an mainstream introduction to (mostly discrete-time) Markov chains with a side-focus on non-random simulation of random processes. Mainstream topics I hope to cover include gambler's ruin, coupon-collecting processes, renewal processes, convergence to stationarity, hitting time, martingales, potential theory, electrical networks, the matrix-tree theorem, Markov Chain Monte Carlo, heat-bath dynamics, Metropolis-Hastings sampling, importance sampling, Poisson processes, and Brownian motion. Topics in non-random (quasi-random) simulation will be centered on the stochastic abacus of Engel (also known as the chip-firing game or the abelian sandpile model) and the rotor-router model, with a side-trip into the computer science notion of derandomization of algorithms and another side-trip into discrepancy theory and Monte Carlo integration. (See my blurb on quasirandomness for a brief introduction to the notion.)
The course is intended to be both theoretical and hands-on; students are expected to carry out projects involving both random and quasirandom simulation. To that end, some lecture-time will be spent assisting students in learning to use Mathematica as a simulation tool. Note that Grinstead and Snell's book comes handily equipped with Mathematica code available for download. You can use Mathematica at many campus locations, such as the the Centers for Learning computer labs on the third floor of Southwick Hall; for a schedule, see http://www.uml.edu/class/Computer_Labs/ed_sched.html For a personal student copy of Mathematica (currently $139.95), go to http://store.wolfram.com/view/app/mathforstudents/. Contact Prof. Propp before buying a copy, since it may be possible for his grant to pay for it. For helpful Mathematica links (including a link to a video tutorial), click here.
GRADING
Grades will be assigned on the basis of homework (50%), a written final project (30%), and the in-class presentation of the final project (30%). (50+30+30=110; the lowest 10% gets dropped.) Each problem on each assignment contributes equally toward your homework grade for the course as a whole. Regular attendance and participation are expected, and can boost a grade that falls on a borderline.