Estimation of Spectral Gap for Markov Chains
Acta Mathematica Sinica, English Series
HOME| ABOUT JOURNAL | EDITORIAL BOARD | FOR AUTHORS| SUBSCRIPTIONS| ADVERTISEMENT| CONTACT US
 
Acta Mathematica Sinica,
Chinese Series
 
   
   
Adv Search »  
Acta Mathematica Sinica, English Series  1996, Vol. 12 Issue (4): 337-360    DOI: 10.1007/BF02106789
articles Current Issue | Next Issue | Archive | Adv Search  |   
Estimation of Spectral Gap for Markov Chains
Chen Mufa
Department of Mathematics, Beijing Normal University, 100875, Beijing, China
 Download: PDF (273 KB)   HTML (0 KB)   Export: BibTeX | EndNote (RIS)      Supporting Info
Abstract The study of the convergent rate (spectral gap) in the L2-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[7] for the estimate of the convergent rate and as a continuation of[4],[5],[7-9],[23] and[24], 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[10]. 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[4] is also extended in the paper.
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Chen Mufa
Key wordsMarkov chains   Spectral gap   Couplings     
Received: 1995-12-27;
Fund: Research supported in part by NSFC, Qin Shi Sci & Tech. Foundation and the State Education Commission of China
Cite this article:   
Chen Mufa. Estimation of Spectral Gap for Markov Chains[J]. Acta Mathematica Sinica, English Series, 1996, 12(4): 337-360.
URL:  
http://www.actamath.com/Jwk_sxxb_en//EN/10.1007/BF02106789      or     http://www.actamath.com/Jwk_sxxb_en//EN/Y1996/V12/I4/337
 
[1] 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.
[2] Chen M F. Exponential L2-convergence and L2-spectral gap for Markov processes.Acta Math Sin New Ser, 1991,7(1): 19-37.
[3] Chen M F. From Markov Chains to Non-Equilibrium Particle Systems. Singapore: World Scientific, 1992.
[4] 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.
[5] Chen M F. Optimal Markovian couplings and applicationsj.Acta Math Sin New Ser, 1994,10(3): 260-275.
[6] 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.
[7] 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.
[8] Chen M F, Wang F Y. Estimation of the first eigenvalue of second order elliptic operators.J Funct Anal, 1995,131(2): 345-363.
[9] Chen M F, Wang F Y. Estimates of logarithmic Sobolev constant—An improvement of Bakry-Emery criterion. to appear in J Funct Anal, 1994.
[10] Chen M F, Wang F Y. Estimation of spectral gap for elliptic operators. to appear in Trans Amer Math Soc, 1995.
[11] 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.
[12] Diaconis, Stroock. Geometric bounds for eigenvalues of Markov chains.Ann Appl Prob, 1991,1(1): 36-61.
[13] Iscoe I, McDonald D. Asymptotics of exit times for Markov jump processes (I).Ann Prob, 1994,22(1): 372-397.
[14] Jerrum M R, Sinclair A J. Approximating the permanent.SIAM J, Comput, 1989,18: 1149-1178.
[15] Lawler G F, Sokal A D. Bounds on the L2 spectrum for Markov chain and Markov processes: a generalization of Cheeger's inequality.Trans Amer Math Soc, 1988,309: 557-580.
[16] Liggett T M. Exponential L2 convergence of attractive reversible nearest particle systems.Ann Probab, 1989,17: 403-432.
[17] Sinclair A J, Jerrum M R. Approximate counting, uniform generation, and rapidly mixing Markov chains.Inform and Comput, 1989,82: 93-133.
[18] 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.
[19] Sullivan W G. The L2 spectral gap of certain positive recurrent Markov chains and jump processes.Z Wahrs, 1984,67: 387-398.
[20] Tweedie R L. Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov Processes.J Appl Prob, 1981,18: 122-130.
[21] Van Doorn E. Stochastic Monotonicity and Queueing Applications of Birth-Death Processes. Lecture Notes in Statistics 4, Springer, 1981.
[22] 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.
[23] Wang F Y. Application of coupling method to the Neumann eigenvalue problem.Prob Th Rel Fields, 1994,98: 299-306.
[24] Wang F Y. Spectral gap for diffusion processes on non-compact manifolds.Chin Sci Bull, 1995,40(14): 1145-1149.
[25] Zeifman A I. Some estimates of the rate of convergence for birth and death processes.J Appl Prob, 1991,28: 268-277.
No Similar of article
  Copyright 2012 © Editorial Office of Acta Mathematica Sinica
京ICP备05002806号-7