In this paper we consider the problem of estimating the spectral gap of a reversible Markov chain in terms of geometric quantities associated with the underlying graph. This quantity provides a bound on the rate of convergence of a Markov chain towards its stationary distribution. We give a critical and systematic treatment of this subject, summarizing and comparing the results of the two main approaches in the literature, algebraic and functional. The usefulness and drawbacks of these bounds are also discussed here

Geometric approaches to the estimation of the spectral gap of reversible Markov chains

INGRASSIA, Salvatore
1993-01-01

Abstract

In this paper we consider the problem of estimating the spectral gap of a reversible Markov chain in terms of geometric quantities associated with the underlying graph. This quantity provides a bound on the rate of convergence of a Markov chain towards its stationary distribution. We give a critical and systematic treatment of this subject, summarizing and comparing the results of the two main approaches in the literature, algebraic and functional. The usefulness and drawbacks of these bounds are also discussed here
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/904
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact