Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions

Details Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions

2012-02-22

arxiv.org/abs/1202.4797v1

Mathematics

Probability

Scientific paper

This paper explores the mixing time of the random transposition walk on permutations with one-sided interval restrictions. In particular, we're interested in the notion of cutoff, a phenomenon which occurs when mixing occurs in a window of order smaller than the mixing time. One of the main tools of the paper is the diagonalization obtained by Hanlon; the use of the spectral information is inspired by the famous paper of Diaconis and Shahshahani on the mixing time of the random transposition walk on the entire symmetric group. The diagonalization allows us to prove chi-squared cutoff for a broad class of one-sided restriction matrices. Furthermore, under an extra condition, the walk also undergoes total variation cutoff. Finally, a large collection of examples which undergo chi-squared cutoff but in which total variation mixing occurs substantially earlier and without cutoff is produced. These results resolve a conjecture of Diaconis and Hanlon from Section 5 of Hanlon's paper.

Affiliated with

Also associated with

No associations

Rating

Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cutoff for the Transposition Walk on Permutations with One-Sided Restrictions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-413666