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].
|Titolo:||A probabilistic proof of Cooper and Frieze's First Visit Time Lemma|
|Data di pubblicazione:||2021|
|Citazione:||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].|
|Appare nelle tipologie:||1.1 Articolo in rivista|
File in questo prodotto:
|A_probabilistic_proof_of_Cooper_and_Friezes_First.pdf||Documento in Pre-print||Nessuna Nota||DRM non definito||Open Access Visualizza/Apri|