Kybernetika 49 no. 6, 868-882, 2013

Universally typical sets for ergodic sources of multidimensional data

Tyll Krüger, Guido Montúfar, Ruedi Seiler and Rainer Siegmund-Schultze


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}$.


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


94A24, 62D05, 94A08


  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