Transition shuffling and linear switching systems

Abstract

This dissertation is a continuous work of my master's thesis Random Walks on a Finite Group\cite{Pang}, which addressed a simple kind of shuffling, top-in shuffle. In this dissertation I will use linear switching systems and Markov chains theory, focusing on another type of shuffling, transposition shuffle. In the early twentieth century, Markov, Poincare, and Borel discussed the special instance of the convergence of random walks on finite groups associated with card shuffling. Their underlying group is the symmetric group. An example they consider is a shuffling method called riffle shuffling used by good card players\cite{riffle}. A marvelous introduction of this is given by Persi Diaconis \cite{diaconis} in the bibliography. The problems we consider in this dissertation arose in a probabilistic treatment of card shuffling. However we treat them as stochastic discrete time switching systems. When a deck of $n$ cards is used, the state space has $n!$ elements so that for even small $n$ the problem becomes very difficult to handle. We show that we can reduce the dimension of the state space first to the number of partitions $n$ into non-negative integer parts and then using this we reduce the state space to size $n$. We demonstrate the procedure in this dissertation with a deck of size 6 and 20.