Mixing of the upper triangular matrix walk

2011/05/23 by Yuval Peres, Peres, Yuval, Allan Sly +1 · 2 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1105.4402

Abstract

We study a natural random walk over the upper triangular matrices, with entries in the field \Z₂, generated by steps which add row i+1 to row i. We show that the mixing time of the lazy random walk is O(n²) which is optimal up to constants. Our proof makes key use of the linear structure of the group and extends to walks on the upper triangular matrices over the fields \Z_q for q prime.

Cited by

• The East model: recent results and new progresses
• Cutoff for random walks on dihedral groups

Related

• The random walk on upper triangular matrices over ℤ/m ℤ
• Upper triangular matrix walk: Cutoff for finitely many columns
• Super-character theory and comparison arguments for a random walk on the upper triangular matrices
• Mixing time of a matrix random walk generated by elementary transvections
• Random walk on unipotent matrix groups