Markov chains and Semigroup Representations
Time and place
1 PM on Thursday, March 4th, 2010; NAC 6113
Benjamin Steinberg (Carleton University, Ottawa)
Abstract
In a famous paper Bayer and Diaconis computed mixing times for riffle shuffling a deck of $n$ cards. In particular, they suggested 7 shuffles as being appropriate for a deck of 52 cards. The representation theory of the symmetric group plays a key role in their analysis. Other shuffling models, such as top-to-random, can also be analyzed as symmetric group random walks. However, over the last decade --- beginning with work of Bidigare, Hanlon and Rockmore on hyperplane chamber walks, followed by work of Diaconis and Brown, further work of Brown, and most recently by work of Bjorner --- an alternative approach to a large class of Markov chains has emerged based on the representation theory of a particularly transparent class of semigroups. This gives a uniform approach to a variety of Markov chains that yields results almost as sharp as case-by-case analysis using group representation theory. Diaconis, in his ICM lecture, asked just how far the semigroup approach can be pushed.
In this talk we survey these results and indicate, to some
extent, an answer to Diaconis's question by considering random
walks on a more general class of semigroups. A typical
example that cannot be analyzed via previous semigroup methods is
the following. Imagine you have a deck of cards and on the
back of each card it says Hoyle.' Players might try to
mark a particular card, say the ace of spades, by rotating it so
that the wordHoyle' is upside down. To avoid this kind
of cheating the dealer should rotate the top half of the deck 180
degrees before riffle shuffling. Our methods easily yield the
spectrum of this Markov chain. Sharp convergence results are
work in progress.
Some of this work is joint with Diaconis.
