A Combinatorial Problem Arising in Information Theory: Precise Minimax Redundancy for Markov Sources
Philippe Jacquet, Wojciech Szpankowski · Birkhäuser Basel eBooks · 2002
Redundancy of a code is defined as the excess of the code length over the optimal code length. When the source of information is unknown, then one wants to design the best code for the worst source (within the class of sources that are being considered). This is called the minimax redundancy. It can come in two flavors: either on average or the worst case. The latter is known as the maximal minimax redundancy, and it is studied in this paper for Markovian sources. Surprisingly, this problem led us to an interesting combinatorial problem on directed graphs that we shall solve using analytic tools. To be more precise, we need to count the number of Eulerian cycles in a directed multi-graph. The maximal minimax redundancy turns out to be a sum over such Eulerian paths. In particular, we shall prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2 m r (m-1) log n + log A m + O(1/n), where n is the length of source sequences, m is the size of the alphabet and A m is an explicit constant that depends on m.* These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.