In this talk, I will describe some results obtained during the
last ten years in joint work with Persi Diaconis. I will focus on
simple examples of random walk on the finite symmetric group S(n).
These examples can be interpreted as strange ways to shuffle cards.
As the walk proceeds, the position of the walker becomes closer
and closer to be uniformly distributed (the deck of cards becomes more and
more ``random''). Based on this interpretation the following basic
question emerges: After how many steps is the walker position close to be
a uniform random position? For instance, consider the three permutations
(1,2), (1,2,...,n) and (n,n-1,...,1). If each s_i is one of these three
permutations, each chosen with probability 1/3, how large should n be
for the product s_1s_2.....s_n to be, to good approximation,
an element of S(n) chosen uniformly at random?
R E F R E S H M E N T S
4:00 To 4:25 PM
Kenneth W. Anderson
Memorial Reading Room
