Non-Asymptotic upper bounds on the probability of the ∈-atypical set for markov chains

Abstract

The non-asymptotic upper bounds on the probability of the ε-atypical set for Markov chains were investigated. Under the stated conditions, the set over which the sup is taken is nonempty and therefore the sup exists and is positive. It was shown that the sup attained a finite value of n, and a non-asymptotic version of this result was also studied based on the method of Markov types. The sliding window Lempel-Ziv algorithm was found to be of independent interest since it suggests that the rates of decay may be larger when the Markov chain's probability of transition matrix is such that the columns of Pn converge fast to the stationary distribution π as n grows.