IT IS IMPORTANT TO REGULARLY CHECK THIS SITE FOR
POSSIBLE NEWS.
How long does it take for an aperiodic irreducible Markov chain to come close
to stationarity? This interesting theoretical question
has become increasingly important with the entrance of
advanced MCMC algorithms on powerful computers.
Since Markov chains are such diverse objects, one usually has to
focus on special cases or classes of special cases.
One important such class is Markov chains on the symmetric group,
so called card shuffling chains.
These will be our main focus during the course.
After an introduction of the topic, giving the basic
definitions and results, the course will evolve around a
number of special cases.
Rougly the material can be divided into four main parts:
- Coupling, strong stationary times and ad-hoc lower bounds.
Here we come across top-to-random shuffling, random transpositions,
transposing neighbors, overhand shuffling and riffle shuffling.
- Wilson's technique for lower bounds. This will allow us to
sharpen the analysis of transposing neighbors and overhand shuffling.
We will also study the move-to-front rule and the Rudvalis shuffle
and far-going generalizations thereof.
- Advanced L2-techniques, leading up to the fundament
of Nash and log-Sobolev techniques.
As a special case we will study random walk on the hypercube.
- The Thorp shuffle. This long standing open problem
was recently solved by Ben Morris,who gives an upper bound
of order log4n, via a sophisticated use
of entropy techniques.
We will study his paper in detail.
- May 27: The lecture notes now finally contain
all the material of the course! Comments are most welcome.
- May 18: List of presentations updated:
- May 15: Urban, Path coupling and Glauber dynamics
- May 18: Stefan, Threshold for the riffle shuffle
- May 20: Krzysztof, MCMC in phylogeny
- May 28: Janeli, Shuffling chromosomes.
- May 29: Emilio, Mixing time of a biased shuffle
- June 1: Oscar, More on Glauber dynamics
- May 8: Some more lecture notes.
- May 4: New lecture notes.
- April 3: More lecture notes today.
- April 2: Schedule for May ready. See below.
- April 1: New update of lecture notes, almost covering up
to Monday March 30.
- March 27: Lecture notes updated. Now I am ahead of the lectures again!
- March 25: Suggested articles for examination seminars
have appeared below.
- March 23: More lecture notes, now covering all lectures up to
and including Monday March 23.
- March 20: Lecture notes extended.
- March 16: New extension of the lecture notes.
- March 5: The lecture notes file was extended today.
- March 2: Lecture on Tuesday March 3 cancelled. We meet again
on Friday March 6.
- March 2: Lecture notes available here.
So far only a few pages are finished, and in a preliminary form.
It is my ambition that the growth of this file will
keep pace with the progression of the course.
We meet in
MVL 14 on Mondays 13.15-15.00, Thursdays 10.00-11.45 and
Fridays 13.15-15.00.
This also goes for weeks 19-22, except, of course, May 21 and 22
(Kristi himmelfärdsdag + klämdag). For compensation, I have also
booked Wednesday May 20, 10.00-11.45 (in MVL 15!) and
Monday June 1, 13.15-15.00.
Lecture notes.
My ambition is that this file will keep pace with the lectures,
but I make no promises in this respect.
Of course, comments and corrections are most welcome.
In any case, my lecture notes are based on a number of
sources. These are all available electronically,
via the author's homepages, Chalmers Library or both.
The references are:
- D. Aldous, Random walks on finite groups and rapidly mixing Markov
chains, Seminaire de Probailites, Lecture notes in Math. 986 (1983), 243-297.
- D. Aldous and P. Diaconis, Shuffling cards and stoppping times,
Amer. Math Monthly 93 (1986), 333-348.
- D. Aldous and J. Fill, Reversible Markov chains and random
walks on graphs, Chapters 2-5 and 8 of draft book found at
www.stat.berkeley.edu/~aldous/RWG/book.html.
- O. Angel, Y. Peres and D. B. Wilson, Card shuffling and diophantine
approximation, Ann. Appl. Probab. 18 (2008), 1215-1231.
- J. Jonasson, Biased random-to-top shuffling, Ann. Appl. Probab. 16 (2006),
1034-1058.
- J. Jonasson, The overhand shuffle mixes in
order n2logn steps, Ann. Appl. Probab. 16 (2006),
231-243.
- P. Matthews, A strong uniform time for random transpositions,
J. Theoret. Probab. 4 (1988), 411-423.
- B. Morris, Improved mixing time for the Thorp shuffle and
L-reversal chain, to appear in Ann. Probab.
- R. Pemantle, Randomization time for the overhand shuffle,
J. Theoret. Probab. 2 (1989), 37-49.
- D. B. Wilson, Mixing time of the Rudvalis shuffle, Electron. Commun.
Probab. 8 (2003), 77-85.
- D. B. Wilson, Mixing times of lozenge tiling and card shuffling Markov
chains, Ann. Appl. Probab. 14 (2004), 274-325.
The student who wants to graduate from the course and recieve
7.5 hp, will read some extra material related to
the course and give a lecture about it.
I have the following papers to suggest for extra material,
but you may also suggest a topic of your own.
- D. Aldous and J. Fill,'' Reversible Markov chains and random walks
on graphs,'' draft book at www.stat.berkeley.edu/~aldous/RWG/book.html,
Chapter 4 on relations between different mixing citeria.
- D. Bayer and P. Diaconis, Trailing the dove-tail shuffle
to its lair, Ann. Appl. Probab. 2 (1992), 294-313,
preliminarily reserved by Stefan.
- I. Benjamini, N. Berger, C. Hoffman and E. Mossel,
Mixing times of the biased card shuffling and
the asymmetric exclusion process,
Trans. Amer. Math. Soc. 357 (2005), no. 8, 3013--3029, reserved by Emilio.
- P. Diaconis and L. Saloff-Coste, Comparison techniques for random
walk on finite groups. Ann. Probab. 21 (1993), 2131--2156.
- P. Diaconis and L. Saloff-Coste, Comparison theorems for reversible
Markov chains, Ann. Appl. Probab. 3 (1993), 696--730.
- R. Durrett, Shuffling chromosomes. J. Theoret. Probab. 16 (2003),
no. 3, 725--750, reserved by Janeli/Urban.
- O. H\"aggstr\"om and J. Jonasson, Rates of Convergence for
Lamplighter Processes, Stochastic Processes and their Applications
67 (1997), 227-249.
- B. Morris, Improved mixing time for the Thorp shuffle and
L-reversal chain, to appear in Ann. Probab., second part on
$L$-reversals.
- B. Morris and Y. Peres, Evolving sets, mixing and heat kernel bounds,
Probab. Th. Rel. Fields 133 (2005), 245-266.
- E. Mossel, Y. Peres, A. Sinclair, Shuffling by semi-random transpositions
Proceedings of the 45th Annual IEEE Symposium on Foundations of
Computer Science (FOCS'04) October 17 - 19, 2004, Rome,
Italy, 572--581, IEEE (2004). (See Elchanan Mossel's homepage.)