首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Markov chain mixing time on cycles
Authors:Balázs Gerencsér
Institution:
  • Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary
  • Abstract:Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n2) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.
    Keywords:Markov chain  Mixing time  Cycle  Non-reversible
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号