Asymptotic Recurrence and Waiting Times for Stationary Processes

Let $${\text{X = }}\left\{ {X_n ;n \in \mathbb{Z}} \right\}$$ be a discrete-valued stationary ergodic process distributed according to P and let x=(..., x −1, x 0, x 1,...) denote a realization from X. We investigate the asymptotic behavior of the recurrence time R n defined as the first time that the initial n-block $$x_1^n = (x_1 ,x_2 , \ldots ,x_n )$$ reappears in the past of x. We identify an associated random walk, $$ - \log P(X_1^n )$$ on the same probability space as X, and we prove a strong approximation theorem between log R n and $$ - \log P(X_1^n )$$ . From this we deduce an almost sure invariance principle for log R n. As a byproduct of our analysis we get unified proofs for several recent results that were previously established using methods from ergodic theory, the theory of Poisson approximation and the analysis of random trees. Similar results are proved for the waiting time W n defined as the first time until the initial n-block from one realization first appears in an independent realization generated by the same (or by a different) process.