Top to random shuffles on colored permutations

A deck of n cards are shuffled by repeatedly taking off the top card, flipping it with probability 1/2, and inserting it back into the deck at a random position. This process can be considered as a Markov chain on the group Bn of signed permutations. We show that the eigenvalues of the transition probability matrix are 0, 1/n, 2/n, ... , (n - 1)/n, 1 and the multiplicity of the eigenvalue i/n is equal to the number of the signed permutation having exactly i fixed points. We show the similar results hold also for the colored permutations. Further, we show that the mixing time of this Markov chain is n log n and exhibits cut off, same as the ordinary 'top to random' shuffles without flipping the cards. The cut off is also analyzed by the strong stationary time as well as the asymptotic formula of the Stirling numbers of the second kind.& COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

A deck of n cards is shuffled by flipping the top card with probability 1/2 and inserting it back randomly. This can be modeled as a Markov chain on signed permutations, with eigenvalues and multiplicities related to fixed points. The same results hold for colored permutations. The mixing time of this Markov chain is n log n, showing cut-off phenomenon, which can be analyzed using strong stationary time and asymptotic formula of Stirling numbers.