In this paper, we are going to study the strong limit theorem for the relative entropy density rates between two finite asymptotically circular Markov chains. Firstly, we prove some lammas on which the main result based. Then, we establish two strong limit theorem for non-homogeneous Markov chains. Finally, we obtain the main result of this paper. As corollaries, we get the strong limit theorem for the relative entropy density rates between two finite non-homogeneous Markov chains. We also prove that the relative entropy density rates between two finite non-homogeneous Markov chains are uniformly integrable under some conditions.

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.