Estimation of Spectral Gap for Markov Chains
Department of Mathematics, Beijing Normal University, 100875, Beijing, China
Abstract The study of the convergent rate (spectral gap) in the L 2-sense is motivated from several different fields: probability, statistics, mathematical physics, computer science and so on and it is now an active research topic. Based on a new approach (the coupling technique) introduced in for the estimate of the convergent rate and as a continuation of,,[7-9], and, this paper studies the estimate of the rate for time-continuous Markov chains. Two variational formulas for the rate are presented here for the first time for birth-death processes. For diffusions, similar results are presented in an accompany paper. The new formulas enable us to recover or improve the main known results. The connection between the sharp estimate and the corresponding eigenfunction is explored and illustrated by various examples. A previous result on optimal Markovian couplings is also extended in the paper.
Key words： Markov chains
Fund: Research supported in part by NSFC, Qin Shi Sci & Tech. Foundation and the State Education Commission of China
Aldous D J, Brown M. Inequalities for rate events in time-reversible Markov chains. IMS Lecture Notes-Monograpg Series 1993,
22, Stochastic Inequalities, 1-16.
Chen M F. Exponential
L 2-convergence and L 2-spectral gap for Markov processes. Acta Math Sin New Ser, 1991, 7(1): 19-37.
Chen M F. From Markov Chains to Non-Equilibrium Particle Systems. Singapore: World Scientific, 1992.
Chen M F. Optimal couplings and application to Riemannian geometry. to appear in Prob Theory and Math Stat. Vol.1, Edited by B Grigelionis
et al. 1993. VPS/TEV, 1994.
Chen M F. Optimal Markovian couplings and applicationsj.
Acta Math Sin New Ser, 1994, 10(3): 260-275.
Chen M F. On ergodic region of Schlögl's model. In Proc Intern Conf on Dirichlet Forms & Stoch Proc Edited by Z M Ma, M Röckner and J A Yan, Walter de Gruyter, 1995.
Chen M F, Wang F Y. Application of coupling method to the first eigenvalue on manifold.
Sci Sin (A), 1993, 23(11) (Chinese Edition): 1130-1140, 1994, 37(1) (English Edition): 1-14.
Chen M F, Wang F Y. Estimation of the first eigenvalue of second order elliptic operators.
J Funct Anal, 1995, 131(2): 345-363.
Chen M F, Wang F Y. Estimates of logarithmic Sobolev constant—An improvement of Bakry-Emery criterion. to appear in J Funct Anal, 1994.
Chen M F, Wang F Y. Estimation of spectral gap for elliptic operators. to appear in Trans Amer Math Soc, 1995.
Deuschel J D, Stroock D W. Hypercontractivity and spectral gap of symmetric diffusion with applications to the stochastic Ising models.
J Funct Anal, 1990, 92: 30-48.
Diaconis, Stroock. Geometric bounds for eigenvalues of Markov chains.
Ann Appl Prob, 1991, 1(1): 36-61.
Iscoe I, McDonald D. Asymptotics of exit times for Markov jump processes (
I). Ann Prob, 1994, 22(1): 372-397.
Jerrum M R, Sinclair A J. Approximating the permanent.
SIAM J, Comput, 1989, 18: 1149-1178.
Lawler G F, Sokal A D. Bounds on the
L 2 spectrum for Markov chain and Markov processes: a generalization of Cheeger's inequality. Trans Amer Math Soc, 1988, 309: 557-580.
Liggett T M. Exponential
L 2 convergence of attractive reversible nearest particle systems. Ann Probab, 1989, 17: 403-432.
Sinclair A J, Jerrum M R. Approximate counting, uniform generation, and rapidly mixing Markov chains.
Inform and Comput, 1989, 82: 93-133.
Sokal A D, Thomas L E. Absence of mass gap for a class of stochastic contour models.
J Statis Phys, 1988, 51(5/6): 907-947.
Sullivan W G. The
L 2 spectral gap of certain positive recurrent Markov chains and jump processes. Z Wahrs, 1984, 67: 387-398.
Tweedie R L. Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov Processes.
J Appl Prob, 1981, 18: 122-130.
Van Doorn E. Stochastic Monotonicity and Queueing Applications of Birth-Death Processes. Lecture Notes in Statistics 4, Springer, 1981.
Van Doorn E. Conditions for exponential ergodicity and bounds for the decay parameter of a birth-death process.
Adv Appl Prob, 1985, 17: 514-530.
Wang F Y. Application of coupling method to the Neumann eigenvalue problem.
Prob Th Rel Fields, 1994, 98: 299-306.
Wang F Y. Spectral gap for diffusion processes on non-compact manifolds.
Chin Sci Bull, 1995, 40(14): 1145-1149.
Zeifman A I. Some estimates of the rate of convergence for birth and death processes.
J Appl Prob, 1991, 28: 268-277.