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

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", 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