# Abstract:

We lift important results about universally typical sets, typically sampled sets, and empirical entropy estimation in the theory of samplings of discrete ergodic information sources from the usual one-dimensional discrete-time setting to a multidimensional lattice setting. We use techniques of packings and coverings with multidimensional windows to construct sequences of multidimensional array sets which in the limit build the generated samples of any ergodic source of entropy rate below an $h_{0}$ with probability one and whose cardinality grows at most at exponential rate $h_{0}$.

# Keywords:

universal codes, typical sampling sets, entropy estimation, asymptotic equipartition property, ergodic theory

# Classification:

94A24, 62D05, 94A08

# References:

1. I. Bjelaković, T. Krüger, R. Siegmund-Schultze and A. Szkoła: The Shannon-McMillan theorem for ergodic quantum lattice systems. Invent. Math. 155 (2004) (1), 203-222.   CrossRef
2. L. Breiman: The individual ergodic theorem of information theory. Ann. Math. Statist. 28 (1957), 809-811.   CrossRef
3. J. C. Kieffer: A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space. Ann. Probab. 3 (1975), 6, 1031-1037.   CrossRef
4. A. Lempel and J. Ziv: Compression of two-dimensional data. IEEE Trans. Inform. Theory 32 (1986), 1, 2-8.   CrossRef
5. E. Lindenstrauss: Pointwise theorems for amenable groups. Invent. Math. 146 (2001), 2, 259-295.   CrossRef
6. B. McMillan: The basic theorems of information theory. Ann. Math. Statist. 24 (1953), 2, 196-219.   CrossRef
7. D. S. Ornstein and B. Weiss: The Shannon-McMillan-Breiman theorem for a class of amenable groups. Israel J. Math. 44 (1983), 1, 53-60.   CrossRef
8. D. S. Ornstein and B. Weiss: How sampling reveals a process. Ann. Probab. 18 (1990), 3, 905-930.   CrossRef
9. C. E. Shannon: A mathematical theory of communication. Bell Syst. Techn. J. 27 (1948), 1, 379-423, 623-656.   CrossRef
10. K. Schmidt: A probabilistic proof of ergodic decomposition. Sankhya: Indian J. Statist, Ser. A 40 (1978), 1, 10-18.   CrossRef
11. P. Shields: The Ergodic Theory of Discrete Sample Paths. Amer. Math. Soc., Graduate Stud. Math. 13 (1996).   CrossRef
12. T. A. Welch: A technique for high-performance data compression. Computer 17 (1984), 6, 8-19.   CrossRef
13. J. Ziv and A. Lempel: A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory 23 (1977), 3, 337-343.   CrossRef
14. J. Ziv and A. Lempel: Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory 24 (1978), 5, 530-536.   CrossRef