Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems

信息论经历了50多年的严谨研究、发展和应用。尽管其相对成熟，但由于新的应用和新兴的理论发展（例如，对多媒体应用，分子生物学和安全性中的源代码编码的兴趣重新抬头），新的挑战也出现了。在1997年的香农讲座中，雅各布·齐夫提出了一个令人信服的论点，即在一定程度上“退出”信息系统的一阶渐近分析，以便预测有限（通常很小）长度（序列、文件、代码、数据库等）的真实系统的行为。克服这些困难的一种方法是通过取代一阶分析来提高渐近分析的准确性(例如：由完全渐近展开和更精确的分析（例如，大偏差，中心极限定律）得到的平均码长的前导项。本研究主要关注源编码的一个重要方面，即冗余率问题。近年来，人们对无损编码和有损编码的冗余率重新产生了兴趣。我们描述了分析、组合和算法方法，这些方法携手解决了这个问题和信息论中的其他问题。一类源的冗余率问题对应于确定实际代码长度超过最佳代码长度的程度。这个问题是二阶渐近的理想候选者，因为人们必须超越代码长度的第一项，这是已知的源的熵。按照Hadamard的原则，我们使用复分析的技术，如生成函数、Rice公式、Mellin变换、傅立叶级数、序列分布模1、鞍点法、解析泊松化和解泊松化以及奇点分析来研究这些问题。我们提出了研究已深入的问题的新结果（例如，最大冗余的最优编码，无记忆和马尔可夫源）以及旧问题的新公式(例如。混合源类的冗余性、算术编码的冗余性和Lemepl-Ziv码)。此外，我们将作为本研究的一部分开发的技术应用于相关问题，如预测（基于模式匹配），随机数生成器，信道编码中未检测到错误的平均最坏情况概率，（精确和近似）运行长度编码的模式匹配方法等。

Information theory has enjoyed over fifty years of rigorous research,development, and application.In spite of its relative maturity,new challenges arise due to novel applications and emerging theoreticaldevelopments (e.g., there is a resurgence of interest in sourcecoding in multimedia applications, molecular biology, and security).In the 1997 Shannon Lecture Jacob Zivpresented compelling arguments for ``backing off'' to a certain extentfrom first-order asymptotic analysis of informationsystems in order to predict the behavior of real systems withfinite (and often small) lengths (of sequences, files, codes,databases, etc.) One way of overcoming these difficulties is toincrease accuracy of asymptotic analysis by replacing first-orderanalyses (e.g., a leading term of the average code length)by full asymptotic expansions and moreaccurate analyses (e.g., large deviations, central limit laws).This research primarily focuses on an important aspect ofsource coding, namely, the redundancy rate problem.Recent years have seen a resurgence of interest inredundancy rates of lossless and lossy coding.We describe analytic, combinatorial and algorithmic methods thatwork hand in hand to solve this and other problems in information theory.The redundancy rate problem fora class of sources corresponds to determining the extent to whichthe actual code length exceeds the optimal code length.This problem is an ideal candidatefor second-order asymptoticssince one must look beyond the leading term of the code length,which is known to be the entropy of the source.Following Hadamard's precept we study these problems usingtechniques of complex analysis such as generating functions,Rice's formula, Mellin transform, Fourier series,sequence distributed modulo 1, saddle point methods,analytic poissonization and depoissonization, andsingularity analysis. We present new results forwell-studied problems (e.g., optimal codes for maximal redundancy,memoryless and Markovian sources) as well as novel formulations of old problems(e.g., redundancy of the class of mixing sources, redundancy ofarithmetic coding and the Lemepl-Ziv codes). Furthermore,we apply the techniques developed as a part of this studyto related problems such as prediction (based on pattern matching),random number generators, the average worst case probability ofundetected error in channel coding, pattern matching approach to(exact and approximate) run length coding, and others.