On random random walk

• 成果类型: Article
• 署名作者: Roichman, Y
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1996
• 页码: 1001-1011
• 关键词: graphs

摘要

We estimate the expected mixing time of a random walk on a finite group supported by a random polylogarithmic set of elements. Following the spectral approach of Broder and Shamir, we present an alternative proof of the Dou-Hildebrand estimate and show that it holds almost surely. Good bounds on diameters follow from these results.