Tree-Indexed Markov Chains in Random Environment and Some of Their Strong Limit Properties

Abstract

In this paper, the authors first introduce the tree-indexed Markov chains in random environment, which takes values on a general state space. Then, they prove the existence of this stochastic process, and develop a class of its equivalent forms. Based on this property, some strong limit theorems including conditional entropy density are studied for the tree-indexed Markov chains in random environment.

Keywords

Random environment / Tree-indexed Markov chains / Strong limit theorem / Conditional entropy density

References

[1] Algoet P H, Cover T M. A sandwich proof of the Shannon-McMillan-Breiman theorem. Ann. Probab., 1988, 16(2): 899-909

[2] Barron A R. The strong ergodic theorem for densities: Generalized Shannon-McMillan-Breiman theorem. Ann. Probab., 1985, 13(4): 1292-1303

[3] Benjamini I, Peres Y. Markov chains indexed by trees. Ann. Probab., 1994, 22(1): 219-243

[4] Berger T, Ye Z. Entropic aspects of random fields on trees. IEEE T. Inform. Theory, 1990, 36(5): 1006-1018

[5] Breiman L. The individual ergodic theorem of information theory. Ann. Math. Statist., 1957, 28(3): 809-811

[6] Chung K L. A note on the ergodic theorem of information theory. Ann. Math. Statist., 1961, 32(2): 612-614

[7] Chung K L. A Course in Probability Theory, 2001 (3rd ed.) Singapore: Elsevier

[8] Cogburn R. The ergodic theory of Markov chains in random environments. Z. Wahrsch. Verw. Gebiete., 1984, 66(1): 109-128

[9] Cogburn R. On direct convergence and periodicity for transition probabilities of Markov chains in random environments. Ann. Probab., 1990, 18(2): 642-654

[10] Cogburn R. On the central limit theorem for Markov chains in random environments. Ann. Probab., 1991, 19(2): 587-604

[11] Dang H, Yang W, Shi Z. The strong law of large numbers and the entropy ergodic theorem for nonhomogeneous bifurcating Markov chains indexed by a binary tree. IEEE T. Inform. Theory, 2015, 61(4): 1640-1648

[12] Delmas J F, Marsalle L. Detection of cellular aging in a Galton-Watson process. Stoch. Proc. Appl., 2010, 120(12): 2495-2519

[13] Dembo A, Mörters A P, Sheffield S. Large deviations of Markov chains indexed by random trees. Ann. I. H. Poincare-Probab. Statist., 2005, 41(6): 971-996

[14] Dong Y, Yang W, Bai J. The strong law of large numbers and the Shannon-McMillan theorem for nonhomogeneous Markov chains indexed by a Cayley tree. Stat. Probabil. Lett., 2011, 81(12): 1883-1890

[15] Guyon J. Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging. Ann Appl Probab, 2007, 17(5–6): 1538-1569

[16] Hu D, Hu X. On Markov chains in space-time random environments. Acta. Math. Sci., 2009, 29B(1): 1-10

[17] Huang H, Yang W. Strong law of large number for Markov chains indexed by an infinite tree with uniformly bounded degree. Sci. China Ser. A., 2008, 51(2): 195-202

[18] Liu W, Ma C, Li Y, Wang S. A strong limit theorem for the average of ternary functions of Markov chains in bi-infinite random environments. Stat. Probabil. Lett., 2015, 100: 12-18

[19] Liu W, Yang W. An extension of Shannon-Mcmillan theorem and some limit properties for nonhomogeneous Markov chains. Stoch. Proc. Appl., 1996, 61(1): 129-145

[20] McMillan B. The basic theorems of information theory. Ann. Math. Statist, 1953, 24: 196-219

[21] Nawrotzki K. Discrete open systems or Markov chains in a random environment, I. J. Inform. Process Cybernet, 1981, 17: 569-599

[22] Nawrotzki K. Discrete open systems or Markov chains in a random environment, II. J. Inform. Process Cybernet, 1982, 18: 83-98

[23] Pemantle R. Automorphism invariant measure on trees. Ann Probab, 1992, 20(3): 1549-1566

[24] Peng W, Yang W, Shi Z. Strong law of large numbers for Markov chains indexed by spherically symmetric trees. Probab. Eng. Inform. Sc., 2015, 29(3): 473-481

[25] Shannon C. A mathematical theory of communication. Bell Syst. Tech. J., 1948, 27: 379-423 623–656

[26] Shi, Z., Wang, Z., Zhong, P., et al., The Generalized Entropy Ergodic Theorem for Nonhomogeneous Bifurcating Markov Chains Indexed by a Binary Tree, Journal of Theoretical Probability, https://doi.org/10.1007/s10959-021-01117-1.

[27] Shi Z, Yang W. The definition of tree-indexed Markov chains in random environment and their existence. Commun. Stat-Theor. M., 2017, 46(16): 7934-7941

[28] Shi Z, Zhong P, Fan Y. The Shannon-McMillan theorem for Markov chains indexed by a Cayley tree in random environment. Probab. Eng. Inform. Sc., 2018, 32: 626-639

[29] Yang J, Yang W G. The generalized entropy ergodic theorem for nonhomogeneous Markov chains indexed by a Cayley tree. Chin Ann Math, Ser. A, 2020, 41(1): 99-114 (In Chinese)

[30] Yang W. Some limit properties for Markov chains indexed by a homogeneous tree. Stat. Probabil. Lett., 2003, 65(3): 241-250

[31] Yang W, Liu W. Strong law of large numbers and Shannon-McMillan theorem for Markov chain fields on trees. IEEE T. Inform. Theory, 2002, 48(1): 313-318

[32] Yang W, Liu W. The asymptotic equipartition property for Mth-order nonhomogeneous Markov information sources. IEEE T. Inform. Theory, 2004, 50(12): 3326-3330

[33] Ye Z, Berger T. Ergodic, regulary and asymptotic equipartition property of random fields on trees. J. Combin. Inform. System Sci., 1996, 21(2): 157-184

[34] Ye Z, Berger T. Information Measures for Discrete Random Fields, 1998, Beijing: Science