Speeding up Markov chains with deterministic jumps

• 成果类型: Article
• 署名作者: Chatterjee, Sourav; Diaconis, Persi
• 署名单位: Stanford University; Stanford University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-020-01006-4
• 发表日期: 2020
• 页码: 1193-1214
• 关键词: random random-walks; POLYNOMIALS; diffusion; cutoff

摘要

We show that the convergence of finite state space Markov chains to stationarity can often be considerably speeded up by alternating every step of the chain with a deterministic move. Under fairly general conditions, we show that not only do such schemes exist, they are numerous.