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

*21 Aug 2012 15:48*

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 ["Let $X$ be a measure space and $T:X\to X$ a measurable transformation. For any measurable $E\subseteq X$ and $x\in E$, the possibly infinite return time is (x):=\inf\{n>0: T^n x\in E\}$. If $T$ is an ergodic tranformation of the probability space $X$, and $\mu(E)>0$, then a theorem of M. Kac states that $\int_E n_E d\mu=1$. We generalize this to any invertible measure preserving transformation $T$ on a finite measure space $X$, by proving independently, and nearly trivially that for any measurable $E\subseteq X$ one has $\int_E n_E d\mu=\mu(I_E)$, where $ is the smallest invariant set containing $E$. In particular this also provides a simpler proof of Poincar\'{e}'s recurrence theorem."]
- 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
- 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