Mixing of the upper triangular matrix walk

Yuval Peres; Allan Sly

doi:10.1007/s00440-012-0436-1

Mixing of the upper triangular matrix walk

Yuval Peres, Allan Sly

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	581-591
Number of pages	11
Journal	Probability Theory and Related Fields
Volume	156
Issue number	3-4
DOIs	https://doi.org/10.1007/s00440-012-0436-1
State	Published - Aug 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Analysis
Statistics and Probability
Statistics, Probability and Uncertainty

Keywords

Mixing time
Random walks on groups

Access to Document

10.1007/s00440-012-0436-1

Cite this

@article{dcbd0ab7f71247dca900015b6fa3d043,

title = "Mixing of the upper triangular matrix walk",

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.",

keywords = "Mixing time, Random walks on groups",

author = "Yuval Peres and Allan Sly",

year = "2013",

month = aug,

doi = "10.1007/s00440-012-0436-1",

language = "English (US)",

volume = "156",

pages = "581--591",

journal = "Probability Theory and Related Fields",

issn = "0178-8051",

publisher = "Springer New York",

number = "3-4",

}

TY - JOUR

T1 - Mixing of the upper triangular matrix walk

AU - Peres, Yuval

AU - Sly, Allan

PY - 2013/8

Y1 - 2013/8

N2 - 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.

AB - 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.

KW - Mixing time

KW - Random walks on groups

UR - http://www.scopus.com/inward/record.url?scp=84880608311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880608311&partnerID=8YFLogxK

U2 - 10.1007/s00440-012-0436-1

DO - 10.1007/s00440-012-0436-1

M3 - Article

AN - SCOPUS:84880608311

SN - 0178-8051

VL - 156

SP - 581

EP - 591

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

IS - 3-4

ER -

Mixing of the upper triangular matrix walk

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this