The minimum universal coding redundancy for finite-statearbitrarily varying sources, is investigated. If the space of allpossible underlying state sequences is partitioned into types, then thisminimum can be essentially lower bounded by the sum of two terms. Thefirst is the minimum redundancy within the type class and the second isthe minimum redundancy associated with a class of sources that can bethought of as “representatives” of the different types.While the first term is attributed to the cost of uncertainty within thetype, the second term corresponds to the type itself. The bound isachievable by a Shannon code w.r.t an appropriate two-stage mixture ofall arbitrarily varying sources in the class
展开▼
