The Markov approximation of the sequences of \(N\)-valued random variables and a class of small deviation theorems. (Q1877526)

The authors consider the sample divergence \[ h(P\mid Q)=\lim \sup _n n^{-1}\text{ln}(p_n(Y_n)/q_n(Y_n)) \] where \(Y_n\) is a random \(P\)-distributed message of length \(n\geq 1\) over a finite alphabet \(S\), \(p_n\) is the density of an \(n\)-restricted probability measure \(P\) with respect to the counting measure and \(q_n\) is similarly the density of an \(n\)-restricted Markov measure \(Q\). The authors prove a class of small deviation theorems for a class of functions \(Y_n\) using the sample divergence and an extension of a theorem of Shannon and McMillan to nonhomogeneous Markov information sources \(Y_{\infty }\).