From card shuffling to random walks on chambers of hyperplane arrangements.

摘要

I have surveyed basic properties of card shuffling techniques as well as generalized theory of random walks on chambers of hyperplane arrangements based on the works of P. Diaconis and his coauthors. Chapter one starts with examples of shuffling techniques and gives their distributions as probability measures on symmetric group. Main theorems proven in chapter one give estimates of total variation distance as a measure of required number of shuffles. Chapter two contains definition of random walk on chambers of hyperplane arrangements and proves theorems about upper bounds for total variation distance.