Universally typical sets for ergodic sources of multidimensional data

Tyll Krüger; Guido F. Montúfar; Ruedi Seiler; Rainer Siegmund-Schultze

Kybernetika (2013)

  • Volume: 49, Issue: 6, page 868-882
  • ISSN: 0023-5954

Abstract

top
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 .

How to cite

top

Krüger, Tyll, et al. "Universally typical sets for ergodic sources of multidimensional data." Kybernetika 49.6 (2013): 868-882. <http://eudml.org/doc/260778>.

@article{Krüger2013,
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\}$.},
author = {Krüger, Tyll, Montúfar, Guido F., Seiler, Ruedi, Siegmund-Schultze, Rainer},
journal = {Kybernetika},
keywords = {universal codes; typical sampling sets; entropy estimation; asymptotic equipartition property; ergodic theory; universal coding; ergodic theory; asymptotic equipartition property},
language = {eng},
number = {6},
pages = {868-882},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Universally typical sets for ergodic sources of multidimensional data},
url = {http://eudml.org/doc/260778},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Krüger, Tyll
AU - Montúfar, Guido F.
AU - Seiler, Ruedi
AU - Siegmund-Schultze, Rainer
TI - Universally typical sets for ergodic sources of multidimensional data
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 6
SP - 868
EP - 882
AB - 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}$.
LA - eng
KW - universal codes; typical sampling sets; entropy estimation; asymptotic equipartition property; ergodic theory; universal coding; ergodic theory; asymptotic equipartition property
UR - http://eudml.org/doc/260778
ER -

References

top
  1. Bjelaković, I., Krüger, T., Siegmund-Schultze, R., Szkoła, A., 10.1007/s00222-003-0318-3, Invent. Math. 155 (2004) (1), 203-222. Zbl1092.81043MR2025304DOI10.1007/s00222-003-0318-3
  2. Breiman, L., 10.1214/aoms/1177706899, Ann. Math. Statist. 28 (1957), 809-811. Zbl0092.34001MR0092710DOI10.1214/aoms/1177706899
  3. Kieffer, J. C., 10.1214/aop/1176996230, Ann. Probab. 3 (1975), 6, 1031-1037. MR0393422DOI10.1214/aop/1176996230
  4. Lempel, A., Ziv, J., 10.1109/TIT.1986.1057132, IEEE Trans. Inform. Theory 32 (1986), 1, 2-8. DOI10.1109/TIT.1986.1057132
  5. Lindenstrauss, E., 10.1007/s002220100162, Invent. Math. 146 (2001), 2, 259-295. Zbl1038.37004MR1865397DOI10.1007/s002220100162
  6. McMillan, B., 10.1214/aoms/1177729028, Ann. Math. Statist. 24 (1953), 2, 196-219. Zbl0050.35501MR0055621DOI10.1214/aoms/1177729028
  7. Ornstein, D. S., Weiss, B., 10.1007/BF02763171, Israel J. Math. 44 (1983), 1, 53-60. Zbl0516.28020MR0693654DOI10.1007/BF02763171
  8. Ornstein, D. S., Weiss, B., 10.1214/aop/1176990729, Ann. Probab. 18 (1990), 3, 905-930. Zbl0709.60036MR1062052DOI10.1214/aop/1176990729
  9. Shannon, C. E., 10.1002/j.1538-7305.1948.tb01338.x, Bell Syst. Techn. J. 27 (1948), 1, 379-423, 623-656. Zbl1154.94303MR0026286DOI10.1002/j.1538-7305.1948.tb01338.x
  10. Schmidt, K., A probabilistic proof of ergodic decomposition., Sankhya: Indian J. Statist, Ser. A 40 (1978), 1, 10-18. Zbl0412.60004MR0545459
  11. Shields, P., 10.1090/gsm/013, Amer. Math. Soc., Graduate Stud. Math. 13 (1996). Zbl0879.28031MR1400225DOI10.1090/gsm/013
  12. Welch, T. A., 10.1109/MC.1984.1659158, Computer 17 (1984), 6, 8-19. DOI10.1109/MC.1984.1659158
  13. Ziv, J., Lempel, A., 10.1109/TIT.1977.1055714, IEEE Trans. Inform. Theory 23 (1977), 3, 337-343. Zbl0379.94010MR0530215DOI10.1109/TIT.1977.1055714
  14. Ziv, J., Lempel, A., 10.1109/TIT.1978.1055934, IEEE Trans. Inform. Theory 24 (1978), 5, 530-536. Zbl0392.94004MR0507465DOI10.1109/TIT.1978.1055934

NotesEmbed ?

top

You must be logged in to post comments.