|
Abstract : |
? In this work we develop further and apply the strong uniform time approach for study of the random walks on finite groups. This approach was introduced by Aldous and Diaconis in [AD1,2] and later developed by Diaconis and Fill in [DF]. Consider a random walk on a finite group. We introduce a notion of total separation for this walk which can be thought as a new measure of how fast the walk is mixing. We show that the total separation is the mean of the best possible strong uniform time. We prove various bounds on the total separation, find connections with hitting times and establish relations between total separations under several natural operations on walks on groups, such as rescaling of the walk, taking direct and wreath product of groups. In this work the emphasis is given to the study of concrete examples of walks. The successful applications of the method include finding sharp bounds on the total separation for the natural random walks on cube, cyclic group, dihedral group, symmetric group, hyperoctahedral group, Heisenberg group, and others. In several cases we were able to obtain not only sharp bounds, but find the exact value of the total separation. Key words and phrases. Random walk, Markov chain, stopping time, strong uniform time,, |
