This thesis studies the mixing times for three random walk models. Specifically these are the random walks on the alternating group, the group of signed permutations and the complete monomial group. The details for the models are given below:

*The random walk on the alternating group:* We investigate the properties
of a random walk on the alternating group $A_n$ generated by 3-cycles of the
form $(i, n − 1, n)$ and $(i, n, n − 1)$. We call this the transpose top-2
with random shuffle. We find the spectrum of the transition matrix of this
shuffle. We obtain the sharp mixing time by proving the total variation
cutoff phenomenon at $(n − 3/2)\log (n)$ for this shuffle.

*The random walk on the group of signed permutations:* We consider a random
walk on the hyperoctahedral group Bn generated by the signed permutations of
the form $(i, n)$ and $(−i, n)$ for $1 \leq i \leq n$. We call this the flip-transpose top
with random shuffle on $B_n$. We find the spectrum of the transition probability
matrix for this shuffle. We prove that this shuffle exhibits the total variation
cutoff phenomenon with cutoff time $n \log (n)$. Furthermore, we show that a similar
random walk on the demihyperoctahedral group $D_n$ generated by the identity signed
permutation and the signed permutations of the form $(i, n)$ and $(−i, n)$ for
$1 \leq i < n$ also has a cutoff at $(n − 1/2)\log (n)$.

*The random walk on the complete monomial group:* Let $G_1 \subseteq \cdots \subseteq G_n \subseteq \cdots$
be a sequence of finite groups with $|G_1| > 2$. We study the properties of a random
walk on the complete monomial group $G_n \wr S_n$ (wreath product of $G_n$ with $S_n$)
generated by the elements of the form $(e,\dots, e, g; id)$ and $(e,\dots, e, g^{−1},
e,\dots, e, g; (i, n))$ for $g \in G_n$, $1 \leq i < n$. We call this the warp-transpose
top with random shuffle on $G_n \wr S_n$. We find the spectrum of the transition probability
matrix for this shuffle. We prove that the mixing time for this shuffle is of order
$n \log (n) + (1/2) n \log(|G_n| − 1)$. We also show that this shuffle satisfies cutoff
phenomenon with cutoff time $n \log (n)$ if $|G_n| = o( n^\delta )$ for all $\delta > 0$.

- All seminars.
- Seminars for 2020

Last updated: 15 Jul 2024