Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 14 (2009) > Paper 49 open journal systems 


Merging for time inhomogeneous finite Markov chains, Part I: Singular values and stability

Laurent Saloff-Coste, Cornell University
Jessica V Zuniga, Stanford University


Abstract
We develop singular value techniques in the context of time inhomogeneous finite Markov chains with the goal of obtaining quantitative results concerning the asymptotic behavior of such chains. We introduce the notion of c-stability which can be viewed as a generalization of the case when a time inhomogeneous chain admits an invariant measure. We describe a number of examples where these techniques yield quantitative results concerning the merging of the distributions of the time inhomogeneous chain started at two arbitrary points.


Full text: PDF

Pages: 1456-1494

Published on: July 2, 2009
Bibliography
  1. Aldous, David. Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243--297, Lecture Notes in Math., 986, Springer, Berlin, 1983. MR0770418 (86j:60156)
  2. Cohen, Joel E. Ergodicity of age structure in populations with Markovian vital rates. III. Finite-state moments and growth rate. An illustration. Advances in Appl. Probability 9 (1977), no. 3, 462--475. MR0465278 (57 #5183)
  3. D'Aristotile, Anthony; Diaconis, Persi; Freedman, David. On merging of probabilities. SankhyāSer. A 50 (1988), no. 3, 363--380. MR1065549 (91h:60004)
  4. Del Moral, P.; Ledoux, M.; Miclo, L. On contraction properties of Markov kernels. Probab. Theory Related Fields 126 (2003), no. 3, 395--420. MR1992499 (2004d:60202)
  5. Diaconis, Persi. Group representations in probability and statistics.Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069 (90a:60001)
  6. Diaconis, P.; Shahshahani, M.. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159--179. MR0626813 (82h:60024)
  7. Diaconis, Persi; Saloff-Coste, Laurent. Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 (1993), no. 3, 696--730. MR1233621 (94i:60074)
  8. Diaconis, P.; Saloff-Coste, L. Nash inequalities for finite Markov chains. J. Theoret. Probab. 9 (1996), no. 2, 459--510. MR1385408 (97d:60114)
  9. Diaconis, P.; Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 (1996), no. 3, 695--750. MR1410112 (97k:60176)
  10. Diaconis, P.; Saloff-Coste, L. What do we know about the Metropolis algorithm?27th Annual ACM Symposium on the Theory of Computing (STOC'95) (Las Vegas, NV). J. Comput. System Sci. 57 (1998), no. 1, 20--36. MR1649805 (2000b:68094)
  11. Douc, R.; Moulines, E.; Rosenthal, Jeffrey S. Quantitative bounds on convergence of time-inhomogeneous Markov chains. Ann. Appl. Probab. 14 (2004), no. 4, 1643--1665. MR2099647 (2005i:60146)
  12. Fill, James Allen. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1 (1991), no. 1, 62--87. MR1097464 (92h:60104)
  13. Ganapathy, M. Robust mixing time. Proceedings of RANDOM'06.
  14. Hajnal, J. The ergodic properties of non-homogeneous finite Markov chains. Proc. Cambridge Philos. Soc. 52 (1956), 67--77. MR0073874 (17,501c)
  15. Horn, Roger A.; Johnson, Charles R. Topics in matrix analysis.Cambridge University Press, Cambridge, 1991. viii+607 pp. ISBN: 0-521-30587-X MR1091716 (92e:15003)
  16. Iosifescu, Marius. Finite Markov processes and their applications.Wiley Series in Probability and Mathematical Statistics.John Wiley & Sons, Ltd., Chichester; Editura Tehnică, Bucharest, 1980. 295 pp. ISBN: 0-471-27677-4 MR0587116 (82c:60123)
  17. Morris, B.; Peres, Yuval. Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields 133 (2005), no. 2, 245--266. MR2198701 (2007a:60042)
  18. Mossel, E.; Peres, Y.; Sinclair, A. Shuffling by semi-random transpositions. 45th Symposium on Foundations of Comp. Sci. (2004) arXiv:math.PR/0404438
  19. Păun, Udrea. Ergodic theorems for finite Markov chains. Math. Rep. (Bucur.) 3(53) (2001), no. 4, 383--390 (2002). MR1990903 (2004d:60189)
  20. Ringrose, J.R. Compact non-self-adjoint operators. London: Van Nostrand Reinhold Math. Studies 1971
  21. Saloff-Coste, Laurent. Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301--413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. MR1490046 (99b:60119)
  22. Saloff-Coste, Laurent. Random walks on finite groups. Probability on discrete structures, 263--346, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023654 (2004k:60133)
  23. Saloff-Coste, L.; Zúñiga, J. Convergence of some time inhomogeneous Markov chains via spectral techniques. Stochastic Process. Appl. 117 (2007), no. 8, 961--979. MR2340874 (2008k:60168)
  24. Saloff-Coste, L.; Zúñiga, J. Refined estimates for some basic random walks on the symmetric and alternating groups. Latin American Journal of Probability and Mathematical Statistics (ALEA) 4 359-392 (2008).
  25. Saloff-Coste, L.; Zúñiga, J. Merging of time inhomogeneous Markov chains, part II: Nash and log-Sobolev inequalities
  26. Saloff-Coste, L.; Zúñiga, J. Time inhomogeneous Markov chains with wave like behavior.
  27. Seneta, E. On strong ergodicity of inhomogeneous products of finite stochastic matrices. Studia Math. 46 (1973), 241--247. MR0332843 (48 #11168)
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489