Analytic Information Theory

Michael Drmota is Professor for Discrete Mathematics at TU Wien. His research activities range from analytic combinatorics over discrete random structures to number theory. He has published several books, including 'Random Trees' (2009), and about 200 research articles. He was President of the Austrian Mathematical Society from 2010 to 2013, and has been Corresponding Member of the Austrian Academy of Sciences since 2013. Wojciech Szpankowski is the Saul Rosen Distinguished Professor of Computer Science at Purdue University where he teaches and conducts research in analysis of algorithms, information theory, analytic combinatorics, random structures, and machine learning for classical and quantum data. He has received the Inaugural Arden L. Bement Jr. Award (2015) and the Flajolet Lecture Prize (2020), among others. In 2021, he was elected to the Academia Europaea. In 2008, he launched the interdisciplinary Institute for Science of Information, and in 2010, he became the Director of the NSF Science and Technology Center for Science of Information.

Part I. Known Sources: 1. Preliminaries; 2. Shannon and Huffman FV codes; 3. Tunstall and Khodak VF codes; 4. Divide-and-conquer VF codes; 5. Khodak VV codes; 6. Non-prefix one-to-one codes; 7. Advanced data structures: tree compression; 8. Graph and structure compression; Part II. Universal Codes: 9. Minimax redundancy and regret; 10. Redundancy of universal memoryless sources; 11. Markov types and redundancy for Markov sources; 12. Non-Markovian sources: redundancy of renewal processes; A. Probability; B. Generating functions; C. Complex asymptotics; D. Mellin transform and Tauberian theorems; E. Exponential sums and uniform distribution mod 1; F. Diophantine approximation; References; Index.