Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T13:51:17.314Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysis of Top To Random Shuffles

Published online by Cambridge University Press:  12 September 2008

Persi Diaconis ,
James Allen Fill  and
Jim Pitman
Persi Diaconis
Affiliation:
Dept. of Mathematics, Harvard University, Cambridge, MA 02138
James Allen Fill
Affiliation:
Dept. of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218–2689
Jim Pitman
Affiliation:
Dept. of Statistics, University of California, Berkeley, CA 94720
Get access Rights & Permissions [Opens in a new window]

Abstract

A deck of n cards is shuffled by repeatedly taking off the top m cards and inserting them in random positions. We give a closed form expression for the distribution after any number of steps. This is used to give the asymptotics of the approach to stationarity: for m fixed and n large, it takes shuffles to get close to random. The formulae lead to new subalgebras in the group algebra of the symmetric group.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 2 , June 1992 , pp. 135 - 155
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. and Diaconis, P. (1986) Shuffling cards and stopping times. Amer. Math. Monthly 93, 333–348.CrossRefGoogle Scholar
[2]Bayer, D. and Diaconis, P. (1991) Trailing the dovetail shuffle to its lair. Ann. Appl. Prob. 2, 294–313.Google Scholar
[3]Calderbank, A. R., Hanlon, P., Sundaram, S. and Wales, D. (1990) Representations of the symmetric group in deformations of the free Lie algebra. Technical report, Dept. of Math., University of Michigan.Google Scholar
[4]Diaconis, P. and Fill, J. (1990) Strong stationary times via a new form of duality. Ann. Prob. 18, 1483–1522.CrossRefGoogle Scholar
[5]Diaconis, P., Hanlon, P. and Rockmore, D. (1991) The eigenvalues of Markov chains on permutations. Unpublished manuscript.Google Scholar
[6]Feller, W. (1968) An Introduction to Probability Theory and its Applications. Vol. 1, 3rd ed., Wiley, New York.Google Scholar
[7]Garsia, A. (1990) Combinatorics of the free Lie algebra and the symmetric group. In P.R., Rabinowitz, Zehnder, E. (eds.) Analysis, etc. Academic Press, Boston, 309–382.Google Scholar
[8]Garsia, A. and Remmel, J. (1985) Shuffles of permutations and the Kronecker product. Graphs Combin. 1, 217–263.CrossRefGoogle Scholar
[9]Garsia, A. and Reutenauer, C. (1989) A decomposition of Solomon's descent algebra. Adv. Math. 77, 189–262.CrossRefGoogle Scholar
[10]Gerstenhaber, M. and Schack, S. (1987) A Hodge-type decomposition for commutative algebra cohomology. J. Pure Appl. Algebra 48, 229–247.CrossRefGoogle Scholar
[11]Gessel, I. and Reutenauer, C. (1991) Counting permutations with given cycle structure and descent set. Technical Report, Dept. of Mathematics, Brandeis University.Google Scholar
[12]Hanlon, P. (1990) The action of Sn on the components of the Hodge decomposition of Hochschild homology. Michigan Math. J. 37, 105–124.CrossRefGoogle Scholar
[13]Holst, L. (1980) On matrix occupancy, committee, and capture-recapture problems. Scand. J. Statist. 7, 139–146.Google Scholar
[14]Lang, S. (1984) Algebra. Addison-Wesley, Menlo Park, California.Google Scholar
[15]Phatarfod, R. M. (1991) On the matrix occurring in a linear search problem. Jour. Appl. Prob. 28, 336–346.CrossRefGoogle Scholar
[16]Solomon, L. (1976) A Mackey formula in the group ring of a Coxeter group. J. Algebra 41, 255–264.CrossRefGoogle Scholar