Geodesic
Universally typical sets for ergodic sources of multidimensional data
Kybernetika, Tome 49 (2013) no. 6, pp. 868-882 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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}$.
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}$.
Classification : 60F15, 62D05, 94A08, 94A17, 94A24
Keywords: universal codes; typical sampling sets; entropy estimation; asymptotic equipartition property; ergodic theory 
@article{KYB_2013_49_6_a2,
     author = {Kr\"uger, Tyll and Mont\'ufar, Guido and Seiler, Ruedi and Siegmund-Schultze, Rainer},
     title = {Universally typical sets for ergodic sources of multidimensional data},
     journal = {Kybernetika},
     pages = {868--882},
     year = {2013},
     volume = {49},
     number = {6},
     mrnumber = {3182645},
     zbl = {1293.94037},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a2/}
}
TY  - JOUR
AU  - Krüger, Tyll
AU  - Montúfar, Guido
AU  - Seiler, Ruedi
AU  - Siegmund-Schultze, Rainer
TI  - Universally typical sets for ergodic sources of multidimensional data
JO  - Kybernetika
PY  - 2013
SP  - 868
EP  - 882
VL  - 49
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a2/
LA  - en
ID  - KYB_2013_49_6_a2
ER  - 
%0 Journal Article
%A Krüger, Tyll
%A Montúfar, Guido
%A Seiler, Ruedi
%A Siegmund-Schultze, Rainer
%T Universally typical sets for ergodic sources of multidimensional data
%J Kybernetika
%D 2013
%P 868-882
%V 49
%N 6
%U http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a2/
%G en
%F KYB_2013_49_6_a2
Krüger, Tyll; Montúfar, Guido; Seiler, Ruedi; Siegmund-Schultze, Rainer. Universally typical sets for ergodic sources of multidimensional data. Kybernetika, Tome 49 (2013) no. 6, pp. 868-882. http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a2/

[1] Bjelaković, I., Krüger, T., Siegmund-Schultze, R., Szkoła, A.: The Shannon-McMillan theorem for ergodic quantum lattice systems. Invent. Math. 155 (2004) (1), 203-222. | DOI | MR | Zbl

[2] Breiman, L.: The individual ergodic theorem of information theory. Ann. Math. Statist. 28 (1957), 809-811. | DOI | MR | Zbl

[3] Kieffer, J. C.: A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space. Ann. Probab. 3 (1975), 6, 1031-1037. | DOI | MR

[4] Lempel, A., Ziv, J.: Compression of two-dimensional data. IEEE Trans. Inform. Theory 32 (1986), 1, 2-8. | DOI

[5] Lindenstrauss, E.: Pointwise theorems for amenable groups. Invent. Math. 146 (2001), 2, 259-295. | DOI | MR | Zbl

[6] McMillan, B.: The basic theorems of information theory. Ann. Math. Statist. 24 (1953), 2, 196-219. | DOI | MR | Zbl

[7] Ornstein, D. S., Weiss, B.: The Shannon-McMillan-Breiman theorem for a class of amenable groups. Israel J. Math. 44 (1983), 1, 53-60. | DOI | MR | Zbl

[8] Ornstein, D. S., Weiss, B.: How sampling reveals a process. Ann. Probab. 18 (1990), 3, 905-930. | DOI | MR | Zbl

[9] Shannon, C. E.: A mathematical theory of communication. Bell Syst. Techn. J. 27 (1948), 1, 379-423, 623-656. | DOI | MR | Zbl

[10] Schmidt, K.: A probabilistic proof of ergodic decomposition. Sankhya: Indian J. Statist, Ser. A 40 (1978), 1, 10-18. | MR | Zbl

[11] Shields, P.: The Ergodic Theory of Discrete Sample Paths. Amer. Math. Soc., Graduate Stud. Math. 13 (1996). | DOI | MR | Zbl

[12] Welch, T. A.: A technique for high-performance data compression. Computer 17 (1984), 6, 8-19. | DOI

[13] Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory 23 (1977), 3, 337-343. | DOI | MR | Zbl

[14] Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory 24 (1978), 5, 530-536. | DOI | MR | Zbl