Upcrossing inequalities for stationary sequences and applications

Abstract

For arrays $(S_{i,j}{)}_{1\le i\le j}$ of random variables that are stationary in an appropriate sense, we show that the fluctuations of the process $(S_{1,n}{)}_{n=1}^{\infty }$ can be bounded in terms of a measure of the ``mean subadditivity'' of the process $(S_{i,j}{)}_{1\le i\le j}$. We derive universal upcrossing inequalities with exponential decay for Kingman's subadditive ergodic theorem, the Shannon--MacMillan--Breiman theorem and for the convergence of the Kolmogorov complexity of a stationary sample.

Published in at http://dx.doi.org/10.1214/09-AOP460 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (12)

• Local stability of ergodic averages
• Oscillation and the mean ergodic theorem for uniformly convex Banach spaces
• On the close interaction between algorithmic randomness and constructive/computable measure theory
• Randomness and initial segment complexity for probability measures
• Universal Coding and Prediction on Ergodic Martin-Löf Random Points
• Algorithmic randomness and stochastic selection function
• Algorithmic analogies to kamae-Weiss theorem on normal numbers
• Multiple Recurrence and Algorithmic Randomness
• Fluctuation bounds for ergodic averages of amenable groups on uniformly convex Banach spaces
• Quantitative ergodic theorems for actions of groups of polynomial growth
• Weak randomness and Kamae's theorem on normal numbers
• Ornstein Isomorphism and Algorithmic Randomness