From the archives
A Lower-bound for the Maximin Redundancy in Pattern Processes
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: Entropy
Date: October, 2009
PageStart: 634
PageEnd: 642
Authors: Aurélien Garivier
Abstract: We show that the maximin average redundancy in pattern coding is
eventually larger than 1.84 (n/log n)1/3 for messages of length n. This improves recent
results on pattern redundancy, although it does not fill the gap between known lower- and
upper-bounds. The pattern of a string is obtained by replacing each symbol by the index of
its first occurrence. The problem of pattern coding is of interest because strongly
universal codes have been proved to exist for patterns while universal message coding is
impossible for memoryless sources on an infinite alphabet. The proof uses fine combinatorial
results on partitions with small summands.
Direct link: available on Entropy
Issue: 4
Volume: 11
Keywords:
