Math 391 — Mixing Times for Markov Chains — Spring 2008

Instructor: Shannon Starr, 1017 Hylan Building,

  • Date/Time/Location
  • Homework
  • Computer Lab
  • Grading Formula
  • Office hours
  • Course Description
  • Prerequisites
  • Textbook

    • Date/Time/Location There are two sections. You can attend either one, depending on which is convenient for your schedule.

    The purpose of the weekly meetings is to discuss questions you come across during your readings, and to make sure that everybody understands the key points in the text. But ultimately, it is the students' responsibility to read the textbook. This is an independent study course, after all.

    Homework There will be homework assignments due once every 2 weeks. Generally, they will be handed out and collected in class. We take a liberal view of extensions for late homeworks. If you need an extra day or two that is fine. But do not take more than a week, otherwise you eat into your time for the next homework. We will occasionally build on past homeworks, too. So you should not delay too much. Also, we may hand out solutions to some of the harder problems.

    Here are the homework assignments:



    You are encouraged to discuss problems with other students and with me, in office hours. But you must write up your solutions yourself. (Word-for-word copying of each other's homework sets is not acceptable.)

    Note: We will not post solutions online. If you want solutions, go to class.

    Computer Lab We have a 50 minute computer lab once per week. The regular lab hour is



    This computer lab is generally open to students: just swipe your student ID card to enter. We will post summaries of the computer labs, here, for students who cannot attend the regular computer lab. (We start with Lab 3. Labs 1 and 2 were just to get acquainted with Matlab.)


    Occasionally, we will also require you to turn in your data for a computer lab, to check that everyone is doing the right work. So everyone might benefit from reading the summaries, regularly.

    Grading Formula Everyone who participates should get a good grade, whether this is A, A- or B+. You should participate frequently, and if you are falling behind, or do not understand some topic, you should contact me (or one of your friends) to get some help. Also, please do not habitually skip class. If you have to be absent more than once, please let me know, and let me know why. If somebody is not doing well, I will contact that person to let them know they are not performing up to the expected standards. I would rather that a student simply drop out (if they are not working for the class) than to have to give a lower grade.

    Office Hours

    I encourage you to contact me by email. I read my email frequently and you will usually get a reply within one day.

    Use office hours to your benefit. If you are having trouble with anything we discussed in class, feel free to ask us. Also, of course, feel free to ask questions about the homework. But, first, please attempt the problem yourself. Tell us where you got stuck and what you are having difficulty with, rather than just asking for the solution.

    Course Description Here is the announcement for this class:

    Besides this announcement, I would like to say that my motivation for teaching this class (which is ``extra'' in the sense that it does not generate any teaching credit for me, although it generates a lot of satisfaction due to the interaction with some great students) is that I attended a short workshop on teaching this class several years ago at MSRI, which was also supported by the MAA, and was organized by David Levin, Yuval Peres and Elizabeth Wilmer, whose book we are using. If you want to see it, here is the webpage at MSRI for that workshop:

    Prerequisites A basic course on probability such as Math 201 or Stats 201. In addition a basic course on Real Analysis would be useful, because we make frequent use of inequalities. Furthermore, we will use matrix analysis (finding eigenvalues and eigenvectors) and sometimes complex numbers to analyze Markov chains.

    Text The textbook we are using is ``Mixing Times for Markov Chains" by David Levin, Yuval Peres and Elizabeth Wilmer. This textbook is currrently in progess. But it seems complete enough to run a successful independent studies course. It can be downloaded, one chapter at a time, from David Levin's website:'



    Also, for doing Matlab, it will be useful if you are familiar with Kermit Sigmon's ``Matlab Primer". It is available here:

    Back to Shannon Starr's webpage.

    Shannon Starr
    1017 Hylan Building
    Department of Mathematics
    University of Rochester
    Rochester, NY 14627
    Phone: (585) 275-9427
    Fax: (585) 273-4655