cnrs   Université de Toulouse

Table of contents for this issue | Previous article | Next article
Persi Diaconis; Laurent Miclo
On the spectral analysis of second-order Markov chains
Annales de la faculté des sciences de Toulouse Sér. 6, 22 no. 3 (2013), p. 573-621, doi: 10.5802/afst.1383
Article PDF | Reviews MR 3113027 | Zbl 06299049

Résumé - Abstract

Second order Markov chains which are trajectorially reversible are considered. Contrary to the reversibility notion for usual Markov chains, no symmetry property can be deduced for the corresponding transition operators. Nevertheless and even if they are not diagonalizable in general, we study some features of their spectral decompositions and in particular the behavior of the spectral gap under appropriate perturbations is investigated. Our quantitative and qualitative results confirm that the resort to second order Markov chains is an interesting option to improve the speed of convergence to equilibrium.


[1] Alon (N.), Benjamini (I.), Lubetzky (E.), and Sodin (S.).— Non-backtracking random walks mix faster, Commun. Contemp. Math., 9(4), p. 585-603 (2007).  MR 2348845 |  Zbl 1140.60301
[2] Bacallado (S.) and Pande (V.).— Bayesian analysis of higher-order, reversible, Markov chains, Preprint, Chemistry Dept., Stanford University (2009).
[3] Diaconis (P.), Holmes (S.), and Neal (R. M.).— Analysis of a nonreversible Markov chain sampler, Ann. Appl. Probab., 10(3), p. 726-752 (2000).  MR 1789978 |  Zbl 1083.60516
[4] Fill (J. A.).— Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab., 1(1), p. 62-87, 1991.  MR 1097464 |  Zbl 0726.60069
[5] Gade (K.) and Overton (M. L.).— Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler, Adv. in Appl. Math., 38(3), p. 382-403 (2007).  MR 2301703 |  Zbl 1156.60058
[6] Horn (R. A.) and Johnson (C. R.).— Matrix analysis, Cambridge University Press, Cambridge (1990). Corrected reprint of the 1985 original.  MR 1084815 |  Zbl 0576.15001
[7] Kato (T.).— Perturbation theory for linear operators, Classics in Mathematics. Springer-Verlag, Berlin (1995). Reprint of the 1980 edition.  MR 1335452 |  Zbl 0836.47009
[8] Lee (A.).— Centro-Hermitian and skew-centro-Hermitian matrices, Linear Algebra Appl., 29, p. 205-210 (1980).  MR 562760 |  Zbl 0435.15019
[9] Maxwell (M.) and Woodroofe (M.).— Central limit theorems for additive functionals of Markov chains, Ann. Probab., 28(2), p. 713-724 (2000).  MR 1782272 |  Zbl 1044.60014
[10] Neal (R. M.).— Improving asymptotic variance of MCMC estimators: Non-reversible chains are better, Technical Report No. 0406, Dept. of Statistics, University of Toronto (2004).
[11] Peskun (P. H.).— Optimum Monte-Carlo sampling using Markov chains, Biometrika, 60, p. 607-612 (1973).  MR 362823 |  Zbl 0271.62041
[12] Pressman (I. S.).— Matrices with multiple symmetry properties: applications of centro-Hermitian and per-Hermitian matrices, Linear Algebra Appl., 284(1-3), p. 239-258, 1998, ILAS Symposium on Fast Algorithms for Control, Signals and Image Processing (Winnipeg, MB, 1997).  MR 1655140 |  Zbl 0957.15019
[13] Saloff-Coste (L.).— Lectures on finite Markov chains, In Lectures on probability theory and statistics (Saint-Flour, 1996), volume 1665 of Lecture Notes in Math., p. 301-413. Springer, Berlin (1997).  MR 1490046 |  Zbl 0885.60061
[14] Weaver (J. R.).— Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors, Amer. Math. Monthly, 92(10), p. 711-717 (1985).  MR 820054 |  Zbl 0619.15021
Search for an article
Search within the site