×
Diaconis, P.; Saloff-Coste, L.

Nash inequalities for finite Markov chains. (English) Zbl 0870.60064

J. Theor. Probab. 9, No. 2, 459-510 (1996).
Summary: This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds on \(\ell_2\)-norms in terms of Dirichlet forms and \(\ell_1\)-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.

Cited in 1 Review
Cited in 53 Documents

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J45 Probabilistic potential theory

Keywords:

Markov chains; infinite graphs; Nash inequalities; Markov kernels; Poincaré inequalities; Dirichlet forms
PDFBibTeX XMLCite
\textit{P. Diaconis} and \textit{L. Saloff-Coste}, J. Theor. Probab. 9, No. 2, 459--510 (1996; Zbl 0870.60064)
Full Text: DOI

References:

[1] Bakry, D., Coulhon, T., Ledoux, M., and Saloff-Coste, L. (1995). Sobolev inequalities in disguise. Université Paul Sabtier, Toulouse.Stat. et. Prob., Preprint. · Zbl 0857.26006
[2] Carlen, E., Kusuoka, S., and Stroock, D. (1987). Upper bounds for symmetric Markov transition functions.Ann. Inst. H. Poincaré, Prob. Stat. 23, 245–287. · Zbl 0634.60066
[3] Chung, F., Diaconis, P., and Graham, R. (1987). A random walk problem arising in random number generation.Ann. Prob. 15, 1148–1165. · Zbl 0622.60016 · doi:10.1214/aop/1176992088
[4] Coulhon, T., and Saloff-Coste, L. (1990a). Puissance d’un opérateur regularisant.Ann. Inst. H. Poincaré, Prob. Stat. 26, 419–436. · Zbl 0709.47042
[5] Coulhon, T., and Saloff-Coste, L. (1990b). Marches aléatoires non-symétriques sur les groupes unimodulaires.C. R. Acad. Sci. Paris, Série I,310, 627–630. · Zbl 0748.60008
[6] Coulhon, T., and Saloff-Coste, L. (1993). Isopérimétrie sur les groupes et les variétés.Rev. Mat. Iberoamericana,9, 293–314. · Zbl 0782.53066
[7] Diaconis, P. (1982).Applications of Non-Commutative Fourier Analysis to Probability Problems. Springer L.N.M.1362, 51–100.
[8] Diaconis, P. (1986).Group Representations in Probability and Statistics. IMS, Hayward.
[9] Diaconis, P., and Saloff-Coste, L. (1933a). Comparison theorems for reversible Markov chains.Ann. Appl. Prob. 3, 696–730. · Zbl 0799.60058 · doi:10.1214/aoap/1177005359
[10] Diaconis, P., and Saloff-Coste, L. (1993b). Comparison techniques for random walk on finite groups.Ann. Prob. 21, 2131–2156. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[11] Diaconis, P., and Saloff-Coste, L. (1994a). Moderate growth and random walk on finite groups.Geom. and Funct. Anal. 4, 1–34. · Zbl 0795.60005 · doi:10.1007/BF01898359
[12] Diaconis, P., and Saloff-Coste, L. (1995). An application of Harnack inequalities to random walk on nilpotent quotients. Actes du Colloque en l’honneur de J. P. Kahane.J. Fourier Anal. Appl. (special Kahane issue) 189–208. · Zbl 0889.60008
[13] Diaconis, P., and Saloff-Coste, L. (1992). Logarithmic Sobolev inequalities and finite Markov chains.Annals Apol. Prob. (to appear). · Zbl 0867.60043
[14] Diaconis, P., and Saloff-Coste, L. (1994c). Geometric bounds on character ratios and symmetric functions. Manuscript. · Zbl 0795.60005
[15] Diaconis, P., and Shashahani, M. (1981). Generating a random permutation with random transpositions.Z. Wahrsch. Verw. Geb. 57, 159–179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[16] Diaconis, P., and Stroock, D. (1991). Geometric bounds for eigenvalues for Markov chains.Ann. Appl. Prob. 1, 36–61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[17] Diaconis, P., and Sturmfels, B. (1993). Algebraic algorithms for sampling from conditional distributions.Ann. Stat. (to appear). · Zbl 0952.62088
[18] Dyer, M., and Frieze, A. (1991). Computing the volume of convex bodies: a case where randomness proveably helps. In Bollobàs, B. (ed.),Probabilistic Combinatorics and Its Applications, Proc. Symp. Appl. Math. 44, 123–170. · Zbl 0754.68052
[19] Fabes, E. (1993). Gaussian upper bounds on fundamental solutions of parabolic equations: the method of Nash. InDirichlet Forms, L.N.M. Springer, p. 163. · Zbl 0818.35036
[20] Feller, W. (1968).An Introduction to Probability Theory and Its Applications, Vol. I, Third Edition J. Wiley and Sons. · Zbl 0155.23101
[21] Fill, J. (1991). Eigenvalue bounds on convergence to stationarity for nonreveresible Markov chains with an application to the exclusion process.Ann. Appl. Prob. 1, 62–87. · Zbl 0726.60069 · doi:10.1214/aoap/1177005981
[22] Gohberg, I., and Krein, I. (1969). Introduction to the theory of linear non-selfadjoint operators. Providence.Amer. Math. Soc. · Zbl 0181.13503
[23] Hildebrand, M. (1992). Generating random elements in SL n (F q ) by random transvections.J. Alg. Combinatorics 1, 133–150. · Zbl 0766.60089 · doi:10.1023/A:1022472220105
[24] Horn, R., and Johnson, C. (1990).Topics in Matrix Analysis. Cambridge University Press. · Zbl 0729.15001
[25] Jerrum, M., and Sinclair, A. (1989). Approximating the permanent.SIAM J. Comp. 18, 1149–1178. · Zbl 0723.05107 · doi:10.1137/0218077
[26] Lawler, G., and Sokal, A. (1988). Bounds on theL 2 spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality.Trans. Amer. Math. Soc. 309, 557–580. · Zbl 0716.60073
[27] Lovasz, L., and Simonovits, M. (1990). Random walks in a convex body and an improved volume algorithm.Random Struct. and Algo. 4, 359–412. · Zbl 0788.60087 · doi:10.1002/rsa.3240040402
[28] Mihail, E. (1989). Combinatorial aspects of expanders. Ph.D. dissertation, Department Computer Sciences, Harvard University.
[29] Nash, J. (1958). Continuity of solutions of parabolic and elliptic equations.Amer. J. Math. 80, 931–954. · Zbl 0096.06902 · doi:10.2307/2372841
[30] Marshall, A., and Olkin, I. (1979).Inequalities: The Theory of Majorization and Its Applications. Academic Press, New York. · Zbl 0437.26007
[31] Robinson, D. (1991).Elliptic Operators on Lie Groups. Oxford University Press. · Zbl 0764.47025
[32] Sinclair, A., and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains.Inform. and Comput. 82, 93–133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[33] Sinclair, A. (1993).Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhäuser, Boston. · Zbl 0780.68096
[34] Stein, E., and Weiss, G. (1971).Introduction to Fourier Analysis on Euclidean Spaces. Princeton University Press. · Zbl 0232.42007
[35] Varopoulos, N. (1984). Une généralisation du théorème de Hardy-Littlewood-Sobolev pour les espaces de Dirichlet.C. R. Acad. Sc. Paris, Série I,299, 651–654. · Zbl 0566.31006
[36] Varopoulos, N. (1985). Isoperimetric inequalities and Markov chains.J. Funct. Anal. 63, 215–239. · Zbl 0573.60059 · doi:10.1016/0022-1236(85)90086-2
[37] Varopoulos, N., Saloff-Coste, L., and Coulhon, T. (1993).Analysis and Geometry on Groups. Cambridge University Press. · Zbl 1179.22009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.