Nonasymptotic upper bounds on the probability of the ε-atypical set for Markov chains

For a stationary, irreducible and aperiodic Markov chain with finite alphabet A, starting symbol X₀=σ, transition probability matrix P, stationary distribution π, support S(π,P)={(j,k):π_jP_k|j>0} and for a function f such that M=ΔE_πPf(X₁,X₂)<+∞ it is known that limsup_l→∞ 1/l log₂ μ(|M-1/l Σ>_i=1^lf(X_i-1,X_i)|≥ε)≤-inf_{(q,Q)∈Γ(e)} D(Q||P), where Γ_ε={(q,Q):|E_π,Pf(X₁,X_2q,Qf(X₁,X₂)|≥ε Qq=q,S(q,Q)⊂S(π,P)}. In this paper we demonstrate that inf_{(q,Q)∈Γ(e)} D(Q||P)≥ 1/(2ln2)[sup_n≥1:Kn>0{K_n/(1+K_n)}ε/(max_j,k:P(k|j)>0|f(j,k)|]² where K_n=(1-|A|max_j,k|P_k|jⁿ-π_k)/n). Under the conditions stated, the set over which the sup is taken is nonempty and therefore the sup exists and is positive; it is also shown that the sup is attained at a finite value of n. A nonasymptotic version of this result is also given based on the method of Markov types.