Spectral Analysis of Generalized Top to Random Shuffles
Abstract
A deck of n cards containing mu less than n different kinds of card is shuffled by taking the top card
and inserting it at a random
position. A spectral decomposition of the transition matrix of the associated Markov process similar to the one
derived by Diaconis et al. in the case mu=n is shown to hold. Its relation to "top m to random" shuffles is
interpreted as a standard change of basis used in polynomial interpolation. We give a closed form formula for
the multiplicity of all eigenvalues of the transition matrix.
This is joined work with S. Tracogna.
