Markov chain mixing time on cycles
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 Î© ( n 2 ) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.
Volume (Year): 121 (2011)
Issue (Month): 11 (November)
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/505572/description#description|
|Order Information:|| Postal: http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
When requesting a correction, please mention this item's handle: RePEc:eee:spapps:v:121:y:2011:i:11:p:2553-2570. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.