Random and Quasirandom Simulation: Lectures from 2007


The videos for most of the lectures are available at http://gse.uml.edu/apreso/propp. Clicking on the appropriate lecture-date will bring up an audio track, a video track, and a document-camera-and-laptop-image track.

If you have trouble opening any of these videos or documents, please let me know. (Unfortunately, no video track was created for the Sept. 24, Oct. 1, and Oct. 10 lectures. Also, if you have a Mac, you will not be able to access any of the video tracks --- only the audio and document-camera-and-laptop-image tracks.)

Most of my lecture notes are embedded in Mathematica notebooks, along with Mathematica code that implements the algorithms under discussion. If you can't open the notebooks, or can't run the code, on account of not having Mathematica, fear not! Wolfram Research has just announced a new service that makes it possible to share Mathematica notebooks with anyone, whether or not they have Mathematica: "Using the new Publish for Player site, you can now convert your interactive notebooks for use with the free Mathematica Player." I haven't taken the time to do this, but if any of you want me to, let me know!

To view a section of a a Mathematica notebook, double-click on the bracket to the right of the caption. To close the section, select the appropriate bracket and double-click on it.

Lecture #1: Random and Quasirandom Simulation. [Word document Lec01-2007.doc] [Mathematica notebook Lec01-2007.nb] [Rotor-router applet] [Picture of a large rotor-router blob]

Lecture #2: Absorbing Markov Chains. [Word document Lec02-2007.doc] [Mathematica notebook Lec02-2007.nb]

Lecture #3: Absorbing Markov Chains and Ergodic Markov Chains (with a review of basic probability theory). [Word document Lec03-2007.doc] [Mathematica notebook Lec03-2007.nb]

Lecture #4: Ergodic Markov Chains and Chip-Firing for Absorbing Markov Chains. [Mathematica notebook Lec04-2007.nb]

Lecture #5: More on Chip-Firing. [Mathematica notebook Lec05-2007.nb]

Lecture #6: Chip-Firing for Ergodic Markov Chains. One-dimensional Random Walk. Examples of Markov Chains. [Mathematica notebook Lec06-2007.nb]

Lecture #7: Chip-Firing for Ergodic Markov Chains (concluded). More examples of Markov chains. [Mathematica notebook Lec07-2007.nb]

Lecture #8: Sampling from a Specified Distribution. Knowing When to Stop. [Mathematica notebook Lec08-2007.nb]

Lecture #9: Discussion of homework problems. Rotor-Routing. [Word document Lec09-2007.doc]

Lecture #10: Comparison of Chip-Firing and Rotor-Routing. [Mathematica notebook Lec10-2007.nb]

Lecture #11: More on Rotor-Routing and its Variants. [Mathematica notebook Lec11-2007.nb]

Lecture #12: Importance Sampling. Recurrence and Transience. [Mathematica notebook Lec12-2007.nb]

Lecture #13: Brownian motion. Electrical Networks, Spanning Trees, and Random Walk. [Mathematica notebook Lec13-2007.nb]