Mixing of the upper triangular matrix walk

Yuval Peres, Allan Sly

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We study a natural random walk over the upper triangular matrices, with entries in the field ℤ2, 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 2) 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 ℤq for q prime.

Original languageEnglish (US)
Pages (from-to)581-591
Number of pages11
JournalProbability Theory and Related Fields
Volume156
Issue number3-4
DOIs
StatePublished - Aug 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Mixing time
  • Random walks on groups

Fingerprint Dive into the research topics of 'Mixing of the upper triangular matrix walk'. Together they form a unique fingerprint.

  • Cite this