Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-27T23:39:41.607Z Has data issue: false hasContentIssue false
  • English
  • Français

Perturbed Markov chains

Part of: Markov processes Limit theorems

Published online by Cambridge University Press:  14 July 2016

Eilon Solan  and
Nicolas Vieille
Eilon Solan*
Affiliation:
Northwestern University and Tel Aviv University
Nicolas Vieille*
Affiliation:
HEC, Jouy-en-Josas
*
∗ Postal address: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel.
∗∗ Postal address: Département Finance et Economie, HEC, 1, rue de la Libération, 78 351 Jouy-en-Josas, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study irreducible time-homogenous Markov chains with finite state space in discrete time. We obtain results on the sensitivity of the stationary distribution and other statistical quantities with respect to perturbations of the transition matrix. We define a new closeness relation between transition matrices, and use graph-theoretic techniques, in contrast with the matrix analysis techniques previously used.

Keywords

Markov chainsstationary distributionexit distributionconductancesensitivity analysisperturbation theorystability of a Markov chain

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60F10: Large deviations
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 1 , March 2003 , pp. 107 - 122
Copyright
Copyright © Applied Probability Trust 2003 

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] Catoni, O. (1999). Simulated annealing algorithms and Markov chains with rare transitions. In Séminaire de Probabilités XXXIII (Lecture Notes in Math. 1709), eds Ledoux, M., Yor, M., Azéma, J. and Emery, M., Springer, Berlin, pp. 69–119.CrossRefGoogle Scholar
[2] Cho, G. E., and Meyer, C. D. (2000). Markov chain sensitivity measured by mean first passage times. Linear Algebra Appl. 316, 21–28.CrossRefGoogle Scholar
[3] Freidlin, M., and Wentzell, A. (1984). Random Perturbations of Dynamical Systems. Springer, Berlin.Google Scholar
[4] Hunter, J. J. (1986). Stationary distributions of perturbed Markov chains. Linear Algebra Appl. 82, 201–214.Google Scholar
[5] Jerrum, M., and Sinclair, A. (1989). Approximating the permanent. SIAM J. Comput. 18, 1149–1178.Google Scholar
[6] Kemeny, J. G., and Snell, J. L. (1960). Finite Markov Chains. Van Nostrand, New York.Google Scholar
[7] Kirkland, S. J., Neumann, M., and Shader, B. L. (1998). Application of Paz's inequality to perturbation bounds for Markov chains. Linear Algebra Appl. 268, 183–196.Google Scholar
[8] Lasserre, J. B. (1994). Formula for singular perturbations of Markov chains. J. Appl. Prob. 31, 829–833.Google Scholar
[9] Lovasz, L., and Kannan, R. (1999). Faster mixing via average conductance. In Annual ACM Symp. Theory Comput. (Atlanta, GA), ACM, New York, pp. 282–287.Google Scholar
[10] Lovasz, L., and Simonovits, M. (1990). The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In 31st Annual Symp. Foundations Comput. Sci. (St. Louis, MO), Vol. I, II, IEEE Compututer Society Press, Los Alamitos, CA, pp. 346–354.Google Scholar
[11] Meyer, C. D. (1975). The role of the group generalized inverse in the theory of Markov chains. SIAM Rev. 17, 443–464.Google Scholar
[12] O’Cinneide, C. A. (1993). Entrywise perturbation theory and error analysis for Markov chains. Numerische Math. 65, 109–120.Google Scholar
[13] Schweizer, P. J. (1968). Perturbation theory and finite Markov chains. J. Appl. Prob. 5, 401–413.Google Scholar
[14] Seneta, E. (1988) Perturbation of the stationary distribution measured by ergodicity coefficients. Adv. Appl. Prob. 20, 228–230.Google Scholar
[15] Seneta, E. (1993). Sensitivity of finite Markov chains under perturbations. Statist. Prob. Lett. 17, 163–168.CrossRefGoogle Scholar
[16] Solan, E., and Vieille, N. (2002). Correlated equilibrium in stochastic games. Games Econom. Behavior 38, 362–399.Google Scholar
[17] Vieille, N. (2000). Small perturbations and stochastic games. Israel J. Math. 119, 127–142.CrossRefGoogle Scholar