Notebooks

## Recurrence Times of Stochastic Processes (also Hitting, Waiting, and First-Passage Times)

08 Dec 2018 11:37

The recurrence time of a state or a finite trajectory is simply how long one must wait to revisit the state, or re-traverse that trajectory. One can learn a lot about a stochastic process by understanding its recurrence times. For instance, Mark Kac proved a very beautiful theorem which says that, for a stationary, discrete-valued stochastic process, the expected recurrence time of a finite trajectory is just the reciprocal of the probability of encountering the trajectory in the first place. This suggests a very simple way to estimate the probability distribution of trajectories. Similarly, one can use the recurrence times to estimate the entropy rate.

Vague, Kac-inspired question: Clearly, if you had a function which gave you the expected recurrence time of an arbitrary finite trajectory, you'd have a function which also gave you all the finite-dimensional marginal distributions of the generating process. But how does one express the higher moments of the recurrence times (the variance, for starters), and might there be some way of trading off knowing more about the higher moments of shorter trajectories for knowing more first moment of longer trajectories? (Getting first moments of long trajectories from first moments of short ones would seem to imply some sort of [conditional] independence.)

Recommended:
• Mark Kac, "On the Notion of Recurrence in Discrete Stochastic Processes", Bulletin of the American Mathematical Society 53 (1947): 1002--1010 [Reprinted in Kac's Probability, Number Theory, and Statistical Physics: Selected Papers, pp. 231--239]
• Benjamin Weiss, Single Orbit Dynamics [Includes a really excellent chapter on recurrence times, the asymptotic equipartition property of entropy (Shannon-MacMillan-Breiman theorem) and data compression]
• Miguel Abadi, Nicolas Vergne, "Sharp error terms for return time statistics under mixing conditions", Journal of Theoretical Probability 22 (2009): 18--37, arxiv:0812.1016
• Eduardo G. Altmann and Holger Kantz, "Recurrence time analysis, long-term correlations, and extreme events", PRE 71 (2005): 056106
• Roberto Artuso, Cesar Manchein, "Instability statistics and mixing rates", arxiv:0906.0791
• Frank Aurzada, Hanna Doering, Marcel Ortgiese, Michael Scheutzow, "Moments of recurrence times for Markov chains", arxiv:1104.1884
• Luis Baez-Duarte, "On the spatial mean of the Poincare cycle", math.PR/0505625
• M. S. Baptista, E. J. Ngamga, Paulo R. F. Pinto, Margarida Brito, J. Kurths, "Kolmogorov-Sinai entropy from recurrence times", arxiv:0908.3401
• J.-R. Chazottes and F. Redig, "Testing the irreversibility of a Gibbsian process via hitting and return times", math-ph/0503071
• J.-R. Chazottes and E. Uglade, "Entropy estimation and fluctuations of Hitting and Recurrence Times for Gibbsian sources", math.DS/0401093
• Remy Chicheportiche, Anirban Chakraborti, "A model-free characterization of recurrences in stationary time series", arxiv:1302.3704
• Victor H. De La Pena and Ming Yang, "Bounding the first passage time on an average", Statistics and Probability Letters 67 (2004): 1--7
• Peter G. Doyle, Jean Steiner, "Commuting time geometry of ergodic Markov chains", arxiv:1107.2612
• Nikos Frantzikinakis, Randall McCutcheon, "Ergodic Theoy: Recurrence", arxiv:0705.0033
• Stefano Galatolo and Dong Han Kim, "The dynamical Borel-Cantelli lemma and the waiting time problems", math.DS/0610213
• N. Hadyn, J. Luevano, G. Mantica and S. Vaienti, "Multifractal properties of return time statistics," nlin.CD/0108050
• Siddharth Jain, Rakesh Kumar Bansal, "On Large Deviation Property of Recurrence Times", ISIT 2013, arxiv:1303.1093
• Oliver Johnson, "A Central Limit Theorem for non-overlapping return times", math.PR/0506165
• Ioannis Kontoyiannis
• Raphael Lefevere, Mauro Mariani, Lorenzo Zambotti, "Large deviations for renewal processes", arxiv:1009.2659
• Yuval Peres and Paul Shields, "Two new Markov order estimators", math.ST/0506080 [One estimator is based on recurrence times]
• Paulo R. F. Pinto, M. S. Baptista, Isabel S. Labouriau, "Density of first Poincaré returns, periodic orbits, and Kolmogorov-Sinai entropy", arxiv:0908.4575
• Amr Sadek and Nikolaos Limnios, "Nonparametric estimation of reliability and survival function for continuous-time finite Markov processes", Journal of Statistical Planning and Inference 133 (2005): 1--21
• Sidney Redner, A Guide to First-Passage Processes [Author's website, with full text of reviews and errata]
• B. Saussol, S. Troubetzkoy and S. Vaienti, "Recurrence, dimensions and Lyapunov exponents," math.DS/0109197
• David Wallace, "Recurrence Theorems: a unified account", arxiv:1306.3925
• Abraham J. Wyner, "More on recurrence and waiting times", Annals of Applied Probability 9 (1999): 780--796