Analysis of Top To Random Shuffles
- 1 June 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (2) , 135-155
- https://doi.org/10.1017/s0963548300000158
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.Keywords
This publication has 10 references indexed in Scilit:
- Trailing the Dovetail Shuffle to its LairThe Annals of Applied Probability, 1992
- On the matrix occurring in a linear search problemJournal of Applied Probability, 1991
- Strong Stationary Times Via a New Form of DualityThe Annals of Probability, 1990
- The action of $S_n$ on the components of the Hodge decomposition of Hochschild homology.The Michigan Mathematical Journal, 1990
- A decomposition of Solomon's descent algebraAdvances in Mathematics, 1989
- A hodge-type decomposition for commutative algebra cohomologyJournal of Pure and Applied Algebra, 1987
- Shuffling Cards and Stopping TimesThe American Mathematical Monthly, 1986
- Shuffling Cards and Stopping TimesThe American Mathematical Monthly, 1986
- Shuffles of permutations and the Kronecker productGraphs and Combinatorics, 1985
- A Mackey formula in the group ring of a Coxeter groupJournal of Algebra, 1976