×

A probabilistic proof of Cooper & Frieze’s “First Visit Time Lemma”. (English) Zbl 1482.60099

Summary: 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 [C. Cooper and A. Frieze, SIAM J. Discrete Math. 18, No. 4, 728–740 (2005; Zbl 1075.05079)], 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\).

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J28 Applications of continuous-time Markov processes on discrete state spaces

Citations:

Zbl 1075.05079
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Abdullah, M. The cover time of random walks on graphs. ArXiv Mathematics e-prints (2012). PhD thesis. arXiv: 1202.5569.
[2] Abdullah, M., Cooper, C., and Frieze, A. Cover time of a random graph with given degree sequence. Discrete Math., 312 (21), 3146-3163 (2012). MR2957935. · Zbl 1252.05207
[3] Aldous, D. Probability approximations via the Poisson clumping heuristic, volume 77 of Applied Mathematical Sciences. Springer-Verlag, New York (1989). ISBN 0-387-96899-7. MR969362. · Zbl 0679.60013
[4] Aldous, D. and Diaconis, P. Shuffling cards and stopping times. Amer. Math. Monthly, 93 (5), 333-348 (1986). MR841111. · Zbl 0603.60006
[5] Aldous, D. and Diaconis, P. Strong uniform times and finite random walks. Adv. in Appl. Math., 8 (1), 69-97 (1987a). MR876954. · Zbl 0631.60065
[6] Aldous, D. and Diaconis, P. Strong uniform times and finite random walks. Adv. in Appl. Math., 8 (1), 69-97 (1987b). MR876954. · Zbl 0631.60065
[7] Aldous, D. and Fill, J. A. Reversible Markov Chains and Random Walks on Graphs (2002). Unfin-ished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/ aldous/RWG/ book.html.
[8] Aldous, D. J. Markov chains with almost exponential hitting times. Stochastic Process. Appl., 13 (3), 305-310 (1982). MR671039. · Zbl 0491.60077
[9] Aldous, D. J. and Brown, M. Inequalities for rare events in time-reversible Markov chains. I. In Stochastic inequalities (Seattle, WA, 1991), volume 22 of IMS Lecture Notes Monogr. Ser., pp. 1-16. Inst. Math. Statist., Hayward, CA (1992). MR1228050.
[10] Aldous, D. J. and Brown, M. Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl., 44 (1), 15-25 (1993). MR1198660. · Zbl 0812.60054
[11] Bianchi, A. and Gaudillière, A. Metastable states, quasi-stationary distributions and soft measures. Stochastic Process. Appl., 126 (6), 1622-1680 (2016). MR3483732. · Zbl 1348.82060
[12] Bianchi, A., Gaudillière, A., and Milanesi, P. On soft capacities, quasi-stationary distributions and the pathwise approach to metastability. J. Stat. Phys., 181 (3), 1052-1086 (2020). MR4160921. · Zbl 1466.60151
[13] Bovier, A. and den Hollander, F. Metastability. A potential-theoretic approach, volume 351 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sci-ences].
[14] Springer, Cham (2015). ISBN 978-3-319-24775-5; 978-3-319-24777-9. MR3445787.
[15] Caputo, P. and Quattropani, M. Stationary distribution and cover time of sparse directed configu-ration models. Probab. Theory Related Fields, 178 (3-4), 1011-1066 (2020). MR4168393. · Zbl 1451.05130
[16] Collet, P., Martínez, S., and San Martín, J. Quasi-stationary distributions. Markov chains, diffusions and dynamical systems. Probability and its Applications (New York). Springer, Heidelberg (2013). ISBN 978-3-642-33130-5; 978-3-642-33131-2. MR2986807. · Zbl 1261.60002
[17] Cooper, C. and Frieze, A. The cover time of random regular graphs. SIAM J. Discrete Math., 18 (4), 728-740 (2005). MR2157821. · Zbl 1075.05079
[18] Cooper, C. and Frieze, A. The cover time of sparse random graphs. Random Structures Algorithms, 30 (1-2), 1-16 (2007a). MR2283218. · Zbl 1113.05089
[19] Cooper, C. and Frieze, A. The cover time of the preferential attachment graph. J. Combin. Theory Ser. B, 97 (2), 269-290 (2007b). MR2290325. · Zbl 1114.05095
[20] Cooper, C. and Frieze, A. The cover time of the giant component of a random graph. Random Structures Algorithms, 32 (4), 401-439 (2008). MR2422388. · Zbl 1157.05045
[21] Cooper, C. and Frieze, A. Stationary distribution and cover time of random walks on random digraphs. J. Combin. Theory Ser. B, 102 (2), 329-362 (2012). MR2885424. · Zbl 1239.05167
[22] Cooper, C., Frieze, A., and Lubetzky, E. Cover time of a random graph with a degree sequence II: Allowing vertices of degree two. Random Structures Algorithms, 45 (4), 627-674 (2014). MR3275701. · Zbl 1320.05109
[23] Cooper, C., Frieze, A., and Radzik, T. Multiple random walks in random regular graphs. SIAM J. Discrete Math., 23 (4), 1738-1761 (2009/10). MR2570201. · Zbl 1207.05179
[24] Cooper, C., Frieze, A., and Radzik, T. The cover times of random walks on random uniform hypergraphs. Theoret. Comput. Sci., 509, 51-69 (2013). MR3123458. · Zbl 1417.05190
[25] Darroch, J. N. and Seneta, E. On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J. Appl. Probability, 2, 88-100 (1965). MR179842. · Zbl 0134.34704
[26] Diaconis, P. and Fill, J. A. Strong stationary times via a new form of duality. Ann. Probab., 18 (4), 1483-1522 (1990). MR1071805. · Zbl 0723.60083
[27] Diaconis, P. and Miclo, L. On times to quasi-stationarity for birth and death processes. J. Theoret. Probab., 22 (3), 558-586 (2009). MR2530103. · Zbl 1186.60086
[28] Diaconis, P. and Miclo, L. On quantitative convergence to quasi-stationarity. Ann. Fac. Sci. Toulouse Math. (6), 24 (4), 973-1016 (2015). MR3434264. · Zbl 1335.60142
[29] Fernandez, R., Manzo, F., Nardi, F. R., and Scoppola, E. Asymptotically exponential hitting times and metastability: a pathwise approach without reversibility. Electron. J. Probab., 20, Paper No. 122, 37 (2015). MR3425542. · Zbl 1329.60269
[30] Fernandez, R., Manzo, F., Nardi, F. R., Scoppola, E., and Sohier, J. Conditioned, quasi-stationary, restricted measures and escape from metastable states. Ann. Appl. Probab., 26 (2), 760-793 (2016). MR3476624. · Zbl 1339.60110
[31] Keilson, J. Markov chain models-rarity and exponentiality, volume 28 of Applied Mathematical Sciences. Springer-Verlag, New York-Berlin (1979). ISBN 0-387-90405-0. MR528293. · Zbl 0411.60068
[32] Levin, D. A. and Peres, Y. Markov chains and mixing times. American Mathematical Society, Providence, RI, second edition (2017). ISBN 978-1-4704-2962-1. MR3726904.
[33] Manzo, F. and Scoppola, E. Exact results on the first hitting via conditional strong quasi-stationary times and applications to metastability. J. Stat. Phys., 174 (6), 1239-1262 (2019). MR3934697. · Zbl 1420.82019
[34] Miclo, L. On absorption times and Dirichlet eigenvalues. ESAIM Probab. Stat., 14, 117-150 (2010). MR2654550. · Zbl 1222.60050
[35] Miclo, L. An absorbing eigentime identity. Markov Process. Related Fields, 21 (2), 249-262 (2015). MR3442821. · Zbl 1328.60179
[36] Miclo, L. On metastability. Technical Report 20-1128, Toulouse School of Economics (TSE) (2020). URL https://EconPapers.repec.org/RePEc:tse:wpaper:124582.
[37] Olivieri, E. and Vares, M. E. Large deviations and metastability, volume 100 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2005). ISBN 0-521-59163-5. MR2123364.
[38] Pitman, J. and Tang, W. Tree formulas, mean first passage times and Kemeny’s constant of a Markov chain. Bernoulli, 24 (3), 1942-1972 (2018). MR3757519. · Zbl 1462.60101
[39] Pollett, P. K. Quasi-stationary distributions: a bibliography (2008). Available at http://www.maths.uq.edu.au/∼pkp/papers/qsds/qsds.pdf.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.