Enumeration and random random walks on finite groups

• 成果类型: Article
• 署名作者: Dou, C; Hildebrand, M
• 署名单位: University of Texas System; University of Texas Austin
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1996
• 页码: 987-1000
• 关键词: graphs

摘要

This paper examines random walks on a finite group G and finds upper bounds on how long it takes typical random walks supported on (log\G\)(a) elements to get close to uniformly distributed on G. For certain groups, a cutoff phenomenon is shown to exist for these typical random walks. A variation of the upper bound lemma of Diaconis and Shahshahani and some counting arguments related to a group equation are used to get the upper bound. A further example which uses this variation is discussed.