A lower-bound for the maximin redundancy in pattern coding
Summary: 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.
- On lower bounds for the redundancy of optimal codes
- On the redundancy of optimal codes with limited word length
- Bounds on the redundancy of Huffman codes (Corresp.)
- Methods of constructing lower bounds for redundancy of universal coding
- A simple upper bound on the redundancy of Huffman codes
- Tight Bounds on the Redundancy of Huffman Codes\hbox{ H }\hbox{ H }
- Tight bounds on the redundancy of Huffman codes
- Tight upper bounds on the redundancy of Huffman codes
- Bounds on the redundancy of binary alphabetical codes
- Optimal universal coding with respect to the maximal individual relative redundancy criterion
- A general minimax result for relative entropy
- A lower bound on compression of unknown alphabets
- A Mathematical Theory of Communication
- A unified approach to weak universal source coding
- AN ASYMPTOTIC FORMULA IN THE THEORY OF PARTITIONS
- On the MDL principle for i.i.d. sources with large alphabets
- Redundancy rates for renewal and other processes
- Speaking of Infinity
- Universal coding, information, prediction, and estimation
- Universal Compression of Memoryless Sources Over Unknown Alphabets
- Universal Lossless Compression With Unknown Alphabets—The Average Case
- Universal noiseless coding
- Universal redundancy rates do not exist
This page was built for publication: A lower-bound for the maximin redundancy in pattern coding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845432)
