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

24 Nov 2007 00:21

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]

Eduardo G. Altmann and Holger Kantz, "Recurrence time analysis, long-term correlations, and extreme events", PRE 71 (2005): 056106
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."]
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
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
Oliver Johnson, "A Central Limit Theorem for non-overlapping return times", math.PR/0506165
Ioannis Kontoyiannis
Yuval Peres and Paul Shields, "Two new Markov order estimators", math.ST/0506080 [One estimator is based on recurrence times]
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