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

*29 Mar 2015 22:00*

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.)

See also: Ergodic Theory; Estimating Entropies and Informations; Information Theory; Friedrich Nietzsche; Stochastic Processes; Time Series

- 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]

- To read:
- Miguel Abadi, Nicolas Vergne, "Sharp error terms for return time statistics under mixing conditions", 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
- 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
- Abraham J. Wyner, "More on recurrence and waiting times",
Annals of Applied Probability
**9**(1999): 780--796