In this article I will give a brief overview of some connections of card shuffling with other parts of mathematics, and give some pointers to the literature for interested readers.

One model of how real people shuffle cards is the riffle shuffle. A 2-riffle shuffle is defined as follows. Cut the deck roughly at the center: more precisely, the chance of cutting the deck at position k is [(n || k)/(2ⁿ)]. This gives two piles, the first of size k and the second of size n-k. Then to mix the piles, at each time one drops a card from a packet chosen with probability proportional to its pile size. So if at some time the first packet has size 3 and the second has size 5, the next card comes from the first packet with probability 3/8 and from the second packet with probability 5/8. When this process is completed, one obtains a somewhat random ordering of the cards. A natural question is: how many iterations of this process are necessary for a deck of n cards to be well mixed. The answer is approximately 3/2 log₂(n) or when n = 52 roughly 7, a result which appeared on page 1 of the New York Times. This theorem was first proved by Aldous for large n, and then for more general n by David Bayer and Persi Diaconis in their very readable article ''Trailing the dovetail shuffle to its lair'', in Annals of Applied Probability, Volume 2, 1992, pages 294-313.

In the remainder of this article I will sketch the relevance of this and related results to several parts of parts of mathematics: Markov chain theory, dynamical systems, Lie theory, symmetric function theory, and random matrix theory.

Let us begin with Markov chain theory. A Markov chain on a finite state space X can be though of as a matrix K(x,y) where x,y are elements in X, and K(x,y) gives the probability of moving from x to y. Many Markov chains converge to a long term stationary distribution p, which is to say that the chance started from x that a chain will be at y after k steps should be roughly p(y) when k is large. For instance in the card shuffling example, the stationary distribution is the uniform distribution which assigns weight [1/n!] to all permutations. The central question of Markov chain theory is: how large need k be so that after k steps the chance of being at y is close to p(y), for all y? A tremendous amount of mathematics is related to this question-especially linear algebra and the study of eigenvalues of symmetric matrices. For the riffle shuffle we said k should be around 3/2 log₂(n). This is an important example for two reasons: first, one can actually write down an exact formula for the chance of being at a permutation y after k iterations of the riffle shuffle; this is VERY rare in Markov chain theory. Second, the eigenvalues of the matrix K(x,y) are real in this case, which again is surprising since K is not a symmetric matrix. In fact this second observation led to the development of the theory of random walks on chambers of hyperplane arrangements, by Bidigare, Hanlon and Rockmore, in Volume 99 of the Duke Math Journal; see also the references in Diaconis' plenary survey talk in Volume 1 of the 1998 International Congress of Mathematicians.

Next let us point out connections with dynamical systems. Consider the map x ® 2x of the unit interval [0,1]. Suppose n points are dropped uniformly at random in this interval, and then the map x ® 2x is applied. Thus the order of the n points in the interval have been permuted in some way, so one has a random permutation on n symbols. It is not hard to show that the permutation obtained this way has exactly the same distribution as that of a 2-riffle shuffle. Thus the two subjects of dynamical systems and Markov chains are related. This has been usefully exploited by Steve Lalley (Annals of Probability 24).

Next we point out connections with Lie theory. Historically these arose by studying the cycles of random permutations (for instance how many cards stay in their original positions after a 2 riffle shuffle). Diaconis, McGrath, and Pitman showed that questions about cycles of permutations are equivalent to questions about the factorization of random polynomials over finite fields. For instance the chance that after a 2-riffle shuffle there are no cards in their original position is the same as the chance that a random degree n polynomial over the field of 2 elements has no linear factors. My contribution to the subject was twofold: first, to realize that the work of Diaconis, McGrath, and Pitman could be stated in more algebraic (Lie theoretical terms) and second, to use this observation to analyze other methods of card shuffling, such as interspering shuffles with cuts. Some of these methods of shuffling are entirely new, and permit a clean elegant analysis by means of Lie theory. For details see my papers in J. Algebra (Volumes 224, 231, 243) and the references therein.

Next we describe some connections with symmetric function theory. This is a wonderful part of combinatorics in which there has recently been a large amount of interest (good surveys are Sagan's book ''The Symmetric Group'' and Stanley's ''Enumerative Combinatorics, Volume 2''). An enormous amount of mathematics (representation theory, algebraic geometry) can be encoded in the calculus of symmetric functions. The first person to connect symmetric functions with riffle shuffles was Richard Stanley (Annals of Combinatorics 5), who related them to Schur functions. This theme was further developed by me (Journal of Algebraic Combinatorics 16) , who showed how symmetric functions could be used to suggest and analyze other shuffling methods.

Finally let me point out some connections with random matrix theory. Recently Baik, Deift, and Johansson showed that the distribution of the length of the longest increasing subsequence in a random permutation is asymptotically the same as the distribution of the largest eigenvalue of certain random Hermitian matrices; they both follow what is called the Tracy-Widom law. This marvellous connection between random permutations and random matrices result has led to literally hundreds of papers in the past few years. Two surveys (already outdated!) are Aldous and Diaconis (Bulletin of the American Math. Society 36) and Deift (Notices of the American Math. Society 47). There are now several approaches to this result, the most remarkable of which is due to Okounkov in his seminal paper ''Random matrices and random permutations''. One of the proofs is due to Johansson and uses a theory of ''discrete orthogonal polynomial ensembles'' which is a discrete analog of random matrix theory. The point for us is that one of his ensembles, the Charlier ensemble, turns out to be closely related to riffle shuffling. In fact the 3/2log₂(n) result already yields interesting results about the Charlier ensemble. Johansson's work can be translated into saying that 5/6log₂(n) iterations of a 2-riffle shuffle suffice to randomize the longest increasing subsequence of a random permutation, which is sharper than the bounds 3/2log₂(n) which follows from the work of Bayer and Diaconis. In any case, the point we wish to make is that card shuffling is also close to the heart of the subject of random matrices as well. For further details and references, see the article ''A card shuffling analysis of deformations of Plancherel measure of the symmetric group'' on my pitt website. For background on random matrices, including their physical importance, see Mehta's classic ''Random matrices, second edition''.

We have only described some of the occurrences of card shuffling in mathematics. Two more in depth surveys of riffle shuffling are an article by Brad Mann (Journal of Undergraduate Math and its Applications, Volume 15) and a forthcoming survey by Persi Diaconis (Groups, Combinatorics, and Geometry: 2001); neither of these discusses random matrices but that is quite recent.