Upcrossing inequalities for stationary sequences and applications

For arrays (Si,j)1≤i≤j of random variables that are stationary in an appropriate sense, we show that the fluctuations of the process (S1,n)n=1∞ can be bounded in terms of a measure of the “mean subadditivity” of the process (Si,j)1≤i≤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.