Journal
STOCHASTIC PROCESSES AND THEIR APPLICATIONS
Volume 121, Issue 11, Pages 2553-2570Publisher
ELSEVIER
DOI: 10.1016/j.spa.2011.07.007
Keywords
Markov chain; Mixing time; Cycle; Non-reversible
Categories
Funding
- Hungarian-American Fulbright Commission
Ask authors/readers for more resources
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 Omega(n(2)) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle. (C) 2011 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available