Mixing of the upper triangular matrix walk |
| |
Authors: | Yuval Peres Allan Sly |
| |
Affiliation: | 1. Microsoft Research, One Microsoft Way, Redmond, WA, 98052-6399, USA 2. Berkeley Department of Statistics, University of California, 367 Evans Hall, Berkeley, CA, 94720, USA
|
| |
Abstract: | We study a natural random walk over the upper triangular matrices, with entries in the field ${mathbb{Z}_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 ${mathbb{Z}_q}$ for q prime. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|