We present an alternative proof of the so-called First Visit Time Lemma (FVTL), originally presented by Cooper and Frieze in its first formulation in Cooper and Frieze (2005), and then used and refined in a list of papers by Cooper, Frieze and coauthors. We work in the original setting, considering a growing sequence of irreducible Markov chains on n states. We assume that the chain is rapidly mixing and with a stationary measure with no entry being either too small nor too large. Under these assumptions, the FVTL shows the exponential decay of the distribution of the hitting time of a given state x-for the chain started at stationarity-up to a small multiplicative correction. While the proof by Cooper and Frieze is based on tools from complex analysis, and it requires an additional assumption on a generating function, we present a completely probabilistic proof, relying on the theory of quasi-stationary distributions and on strong-stationary times arguments. In addition, under the same set of assumptions, we provide some quantitative control on the Doob's transform of the chain on the complement of the state x.

Manzo, F., Quattropani, M., Scoppola, E. (2021). A probabilistic proof of Cooper and Frieze's First Visit Time Lemma. ALEA, 18(2), 1739-1758 [10.30757/ALEA.v18-64].

A probabilistic proof of Cooper and Frieze's First Visit Time Lemma

Scoppola, Elisabetta
2021-01-01

Abstract

We present an alternative proof of the so-called First Visit Time Lemma (FVTL), originally presented by Cooper and Frieze in its first formulation in Cooper and Frieze (2005), and then used and refined in a list of papers by Cooper, Frieze and coauthors. We work in the original setting, considering a growing sequence of irreducible Markov chains on n states. We assume that the chain is rapidly mixing and with a stationary measure with no entry being either too small nor too large. Under these assumptions, the FVTL shows the exponential decay of the distribution of the hitting time of a given state x-for the chain started at stationarity-up to a small multiplicative correction. While the proof by Cooper and Frieze is based on tools from complex analysis, and it requires an additional assumption on a generating function, we present a completely probabilistic proof, relying on the theory of quasi-stationary distributions and on strong-stationary times arguments. In addition, under the same set of assumptions, we provide some quantitative control on the Doob's transform of the chain on the complement of the state x.
2021
Manzo, F., Quattropani, M., Scoppola, E. (2021). A probabilistic proof of Cooper and Frieze's First Visit Time Lemma. ALEA, 18(2), 1739-1758 [10.30757/ALEA.v18-64].
File in questo prodotto:
File Dimensione Formato  
A_probabilistic_proof_of_Cooper_and_Friezes_First.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 236.35 kB
Formato Adobe PDF
236.35 kB Adobe PDF Visualizza/Apri

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/11590/407264
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact