Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T09:28:06.986Z Has data issue: false hasContentIssue false
  • English
  • Français

On some mixing times for nonreversible finite Markov chains

Part of: Markov processes Stochastic processes

Published online by Cambridge University Press:  22 June 2017

Lu-Jing Huang  and
Yong-Hua Mao
Lu-Jing Huang*
Affiliation:
Beijing Normal University
Yong-Hua Mao*
Affiliation:
Beijing Normal University
*
* Postal address: Laboratory of Mathematics and Complex Systems, Ministry of Education, School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P. R. China.
* Postal address: Laboratory of Mathematics and Complex Systems, Ministry of Education, School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P. R. China.
Get access Rights & Permissions [Opens in a new window]

Abstract

By adding a vorticity matrix to the reversible transition probability matrix, we show that the commute time and average hitting time are smaller than that of the original reversible one. In particular, we give an affirmative answer to a conjecture of Aldous and Fill (2002). Further quantitive properties are also studied for the nonreversible finite Markov chains.

Keywords

Markov chainnonreversiblevorticity matrixmixing time

MSC classification

Primary: 60J27: Continuous-time Markov processes on discrete state spaces
Secondary: 60G20: Generalized stochastic processes
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 2 , June 2017 , pp. 627 - 637
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aldous, D. J. and Fill, J. A. (2002). Reversible Markov Chains and Random Walks on Graphs. Preprint. Available at https://www.stat.berkeley.edu/~aldous/RWG/book.html. Google Scholar
[2] Avrachenkov, K., Cottatellucci, L., Maggi, L. and Mao, Y.-H. (2013). Maximum entropy mixing time of circulant Markov processes. Statist. Prob. Lett. 83, 768–773. Google Scholar
[3] Bierkens, J. (2016). Non-reversible Metropolis-Hastings. Statist. Comput. 26, 1213–1228. Google Scholar
[4] Chen, T.-L. and Hwang, C.-R. (2013). Accelerating reversible Markov chains. Statist. Prob. Lett. 83, 1956–1962. Google Scholar
[5] Cui, H. and Mao, Y.-H. (2010). Eigentime identity for asymmetric finite Markov chains. Front. Math. China 5, 623–634. Google Scholar
[6] Diaconis, P., Holmes, S. and Neal, R. M. (2000). Analysis of a nonreversible Markov chain sampler. Ann. Appl. Prob. 10, 726–752. CrossRefGoogle Scholar
[7] Gaudillière, A. and Landim, C. (2014). A Dirichlet principle for non reversible Markov chains and some recurrence theorems. Prob. Theory Relat. Fields 158, 55–89. Google Scholar
[8] Hwang, C.-R., Hwang-Ma, S.-Y. and Sheu, S. J. (1993). Accelerating Gaussian diffusions. Ann. Appl. Prob. 3, 897–913. Google Scholar
[9] Hwang, C.-R., Hwang-Ma, S.-Y. and Sheu, S.-J. (2005). Accelerating diffusions. Ann. Appl. Prob. 15, 1433–1444. Google Scholar