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^*

^*Corresponding author for this work

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

11 Citations (Scopus)

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
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
Publication status	Published - Aug 2013
Externally published	Yes

Access to Document

10.1007/s00440-012-0436-1

Cite this

@article{d78dfb61798040b485b8004c9f2f94a1,

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

volume = "156",

pages = "581--591",

journal = "Probability Theory and Related Fields",

issn = "0178-8051",

publisher = "Springer",

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

U2 - 10.1007/s00440-012-0436-1

DO - 10.1007/s00440-012-0436-1

M3 - Article

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

Access to Document

Other files and links

Fingerprint

Cite this