Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T23:41:45.483Z Has data issue: false hasContentIssue false

Geometric inequalities for the eigenvalues of concentrated Markov chains

Published online by Cambridge University Press:  14 July 2016

Olivier François*
Affiliation:
LMC/IMAG
*
∗ Postal address: LMC/IMAG, BP 53, 38041 Grenoble cedex 9, France. Email address: olivier.francois@imag.fr

Abstract

This article describes new estimates for the second largest eigenvalue in absolute value of reversible and ergodic Markov chains on finite state spaces. These estimates apply when the stationary distribution assigns a probability higher than 0.702 to some given state of the chain. Geometric tools are used. The bounds mainly involve the isoperimetric constant of the chain, and hence generalize famous results obtained for the second eigenvalue. Comparison estimates are also established, using the isoperimetric constant of a reference chain. These results apply to the Metropolis-Hastings algorithm in order to solve minimization problems, when the probability of obtaining the solution from the algorithm can be chosen beforehand. For these dynamics, robust bounds are obtained at moderate levels of concentration.

Information

Type
Research Papers
Copyright
Copyright © 2000 by The Applied Probability Trust 

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.)

Article purchase

Temporarily unavailable