Cutoff phenomenon for the warp-transpose top with random shuffle

Abstract: Let

{G_{n}}_{1}^{i n f t y}

be a sequence of non-trivial finite groups. In this paper, we study the properties of a random walk on the complete monomial group

G_{n} w r S_{n}

generated by the elements of the form

(e x t e, d o t s, e x t e, g; e x t i d)

and

(e x t e, d o t s, e x t e, g^{- 1}, e x t e, d o t s, e x t e, g; (i, n))

for

g i n G_{n},; 1 l e q i < n

. We call this the warp-transpose top with random shuffle on

G_{n} w r S_{n}

. We find the spectrum of the transition probability matrix for this shuffle. We prove that the mixing time for this shuffle is

O l e f t (n l o g n + f r a c 12 n l o g (| G_{n} | - 1) i g h t)

. We show that this shuffle exhibits

e l l^{2}

-cutoff at

n l o g n + f r a c 12 n l o g (| G_{n} | - 1)

and total variation cutoff at

n l o g n

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Cutoff phenomenon for the warp-transpose top with random shuffle