Random Walks on Finite Groups: an Application of Group Representations
Playing cards, a set of fifty-two cards with four suits and thirteen numbers, appear every-
where in ourdaily lives. In particular, theyare commonly used ongambling tables in casinos.
Before every game, the dealer needs to shuffle those cards to put them into a random order so
that the game is fair. (Is it really the case in casinos?) One may wonder whether a shuffling
technique is really efficient or not, i.e. whether it can turn the deck into a random configu-
ration in a small number of rounds. Mathematically, this can be interpreted as a problem of
random walks on the symmetric group of 52 elements S_{52} and we aim to determine how fast
the random walk becomes (uniformly) random. This paper aims to explain an important
application of group representations to this type of problems; in particular, techniques from
group representations can provide a (roughly) accurate approximation.
There will be six chapters in this paper. Chapter 1 is an introduction to problems of random
walks. Chapter 2 and 3 discuss group representations in general, and a key lemma for
application is discussed at the end of Chapter 3. Chapter 4 is an application to the easiest
random walk one can encounter. Chapter 5 focuses on discussing properties distinctive to
symmetric groups, and Chapter 6 discusses a card-shuffling example in details. Contents in
Chapter 5 are mostly from the second chapter of [Sag01]; the key result in Chapter 6 along
with the rest of the paper are mostly from [Dia88] with a few exceptions. This paper is
written in a self-explanatory way, so anyone with necessary background of linear algebra,
group theory, and probability will be able to follow the entirety of it.
where in ourdaily lives. In particular, theyare commonly used ongambling tables in casinos.
Before every game, the dealer needs to shuffle those cards to put them into a random order so
that the game is fair. (Is it really the case in casinos?) One may wonder whether a shuffling
technique is really efficient or not, i.e. whether it can turn the deck into a random configu-
ration in a small number of rounds. Mathematically, this can be interpreted as a problem of
random walks on the symmetric group of 52 elements S_{52} and we aim to determine how fast
the random walk becomes (uniformly) random. This paper aims to explain an important
application of group representations to this type of problems; in particular, techniques from
group representations can provide a (roughly) accurate approximation.
There will be six chapters in this paper. Chapter 1 is an introduction to problems of random
walks. Chapter 2 and 3 discuss group representations in general, and a key lemma for
application is discussed at the end of Chapter 3. Chapter 4 is an application to the easiest
random walk one can encounter. Chapter 5 focuses on discussing properties distinctive to
symmetric groups, and Chapter 6 discusses a card-shuffling example in details. Contents in
Chapter 5 are mostly from the second chapter of [Sag01]; the key result in Chapter 6 along
with the rest of the paper are mostly from [Dia88] with a few exceptions. This paper is
written in a self-explanatory way, so anyone with necessary background of linear algebra,
group theory, and probability will be able to follow the entirety of it.
