Other Pages Ravi's Web Page

Math 8843 - Convergence of Markov Chains Instructor : Ravi Montenegro Office : Skiles 258 Office Hours : MW 1-2:30pm (tentative) Office Phone : 404-894-1833 Email : ravi_montenegro@uml.edu Syllabus: PDF file Presentation topics See web sites in the "Online Notes" section below for various topics. Dana Randall's page mentions some possibilities. Feel free to ask about other areas that you may be interested in. Here are a few more ideas related to topics we discussed: Modified log-Sobolev (see Prasad's paper on Modified log-Sobolev) Log-Sobolev (Houdre has a paper on using spectral gap and conductance function to bound log-sobolev, here) Evolving Sets (see papers of Ben Morris for applications) Card Shuffling Mixing times of biased card shuffling (see here at arXiv) Lower bounds on mixing time of Rudvalis Shuffle (see here at Electronic Communications in Probability) Mixing time for the Thorp shuffle (see Ben Morris' web page, this uses Evolving sets to study shuffling) Walks on Groups (see links in the walks on groups section of the lectures) Online Notes and texts: Dana Randall's course notes (for those who did not take her course, I will cover the theory that she covered but skip the nice applications, so you might want to wait to read things until I've covered the relevant theory) Alistair Sinclair's course notes Eric Vigoda's course notes Mark Jerrum's notes (see "Lecture notes") Aldous and Fill book Other places for possible presentation topics: David Wilson's page: papers on coupling and coupling from the past Lazlo Lovasz's page: the most recent volume algorithms Lectures: (subject to change as the term progresses) Introduction AS1 and AS2: Markov chain basics. (Thm 2.1 in EV2 contains a proof of Fundamental Theorem) Lecture 4: Variation distance and mixing time. Analytic methods of bounding mixing time Lecture 5: L_p distances and the spectral decomposition. Lecture 6: Mixing time of the simple random walk on a cycle. Lecture 7: Exponential decay and lower bounding mixing time. Lecture 8: Dirichlet forms and comparison of spectral gap. Lecture 9: Canonical paths. Lectures 10 and 11 were a preview of geometric methods (see below). Lecture 12: Continuous time chains and modified log-Sobolev. Lecture 13: Operator norms and Nash inequalities. Lecture 14: log-Sobolev, tensorization. Homework 1 is now available and is due Monday Oct 4 (in two weeks). Lecture 15: (9/20) Decomposition and some examples. Geometric methods of bounding mixing time Lecture 10: Conductance and the spectral gap. Sam and Teena taught approximating the permanent (Thanks!). Lecture 11 / Combinatorics Seminar: Evolving set and Cheeger bounds on the top and bottom eigenvalues. Lectures 12-15 were on analytic topics (see above). Lecture 16: Evolving sets and distances. Lecture 17: Mixing times and conductance. Lecture 18: Simple random walk on a cycle, new Cheeger Inequality. Lecture 19: Consequences of new Cheeger, Average congestion. Lecture 20: Average Conductance, the Easy Inequality Prover. Lecture 21: Vertex congestion and comparison theorems Volume and Integration of log-concave functions (I have not edited these notes, so they are not recommended for use outside my class.) Note-takers: Please try to type of notes within a few days of class, so that the rest of the class has them available soon. Those who are typing notes can use the Lecture 17 notes as a template, along with the Bibtex reference list. To use this type "latex lecture17.tex", then "bibtex lecture17", then "latex lecture17.tex" twice. Lecture 22: Reduction of volume estimation to uniform sampling. Lecture 23: Introduction to the Ball Walk. Lecture 24: Local Conductance and uniform sampling. Lecture 25: Mixing time of Ball Walk, Localization Lemma. The proofs for the next three lectures are based on this paper on "Blocking Conductance". Lecture 26: Bounding Conductance I Lecture 27: Bounding Conductance II Lecture 28: Bounding Conductance III Start thinking about your presentation. Walks on groups, Cayley graphs and other highly symmetric objects Lecture 29-31: Symmetry Analysis of Reversible Markov Chains (see the paper here). There are numerous minor mistakes in the paper so don't be too surprised if something doesn't seem right.) Lecture 32-34: Strong Uniform Stopping Times and applications Lecture 35: Analysis of Riffle Shuffle Lecture 36: Analysis of Riffle Shuffle II (based largely on Aldous and Diaconis which is accessible online via the GATech library electronic journals, see also Diaconis' survey on shuffling for the latest developments) (see Igor Pak lectures 11-13 for intro to strong uniform stopping times) For more information on walks on groups see: Igor Pak's random walk papers. His early papers do a lot on strong uniform stopping times. His Ph.D. Dissertation "Random Walks on Groups : Strong Uniform Time Approach" is probably the best place to find what can be done with Strong Uniform Times. Laurent Saloff-Coste has many papers on random walks on groups, see in particular "Random walks on finite groups". Martin Hildebrand has some stuff related to walks on groups, although not immediately related to what we looked at. Persi Diaconis is responsible for much of the study of random walks on groups. His book "Group Representations in Probability and Statistics" is a good source, but is out of print. Generalized knapsack and applications See Sinclair's notes for Lectures 16-17 for information on knapsack. The generalized knapsack can be found in Ben Morris' thesis. Mary Cryan's publications include applications to contingency tables and transportation polytopes. Student presentations Week 13 (11/15): Week 14 (11/22): Week 15 (11/29):