A lower bound on compression of unknown alphabets

DOI10.1016/j.tcs.2004.10.038zbMath1070.68037OpenAlexW2127887726MaRDI QIDQ1770393

Alon Orlitsky, Narayana P. Santhanam, Nikola Jevtić

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.038

zbMATH Keywords

PatternsSaddle point approximationsHayman's theoremLarge and unknown alphabetsUniversal compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (1)

A lower-bound for the maximin redundancy in pattern coding

Cites Work

• Unnamed Item
• Universal sequential coding of single messages
• A game of prediction with expert advice
• On asymptotics of certain recurrences arising in universal coding
• Special issue: Average-case analysis of algorithms
• Multi-alphabet universal coding of memoryless sources
• Always Good Turing: Asymptotically Optimal Probability Estimation
• A Generalisation of Stirling's Formula.
• Precise Minimax Redundancy and Regret
• Speaking of Infinity
• Universal Compression of Memoryless Sources Over Unknown Alphabets
• One-way communication and error-correcting codes
• Universal Lossless Compression With Unknown Alphabets—The Average Case
• The performance of universal encoding
• Universal codeword sets and representations of the integers
• A unified approach to weak universal source coding
• Universal Portfolios
• Asymptotic minimax regret for data compression, gambling, and prediction
• Universal codes for finite sequences of integers drawn from a monotone distribution
• A decision-theoretic extension of stochastic complexity and its applications to learning
• Fisher information and stochastic complexity
• Universal portfolios with side information

This page was built for publication: A lower bound on compression of unknown alphabets