Universally Typical Sets for Ergodic Sources of Multidimensional Data

2011/05/02 by Tyll Krueger, Guido Montufar, Krueger, Tyll +8
Computer Science · Mathematics · #62D05 #94A08 #94A24 #Algorithms and Data Compression #Digital Image Processing Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Dynamics and Fractals #cs.IT #math.IT #msc:62D05 #msc:94A08 #msc:94A24

paper · pdf · doi:10.48550/arxiv.1105.0393

15 pages, 1 figure. To appear in Kybernetika. This replacement corrects typos and slightly strengthens the main theorem

openalex publication_date 2011/05/02 · arxiv created 2013/11/12 · arxiv updated 2013/11/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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₀ with probability one and whose cardinality grows at most at exponential rate h₀.

Related

• On typical encodings of multivariate ergodic sources
• Generic points in systems of specification and Banach valued Birkhoff ergodic average
• Sequential Recurrence-Based Multidimensional Universal Source Coding of Lempel-Ziv Type
• Normal numbers with given limits of multiple ergodic averages
• Information Content and Entropy of Finite Patterns from a Combinatorial Perspective