Consider a class Λ of parametric models, where the parameter set θ characterizes the distribution for a specific source within this class, .

The goal is to find a fixed to variable length lossless code that is independent of θ, which is unknown, yet achieves

(4.2)

where expectation is taken w.r.t. the distribution implied by θ. We have seen for

(4.3)

that a code that is good for two sources (distributions) p₁ and p₂ exists, modulo the one bit loss Equation 3.2. As an expansion beyond this idea, consider

where w(θ) is a prior.

(4.5)

Then

and

Moreover, it can be shown that

(4.8)

this result appears in Krichevsky and Trofimov 2.

Is the source X implied by the distribution p(x) an ergodic source? Consider the event . Owing to symmetry, in the limit of large n the probability of this event under p(x) must be ,

(4.9)

On the other hand, recall that an ergodic source must allocate probability 0 or 1 to this flavor of event. Therefore, the source implied by p(x) is not ergodic.

Recall the definitions of p_θ(x) and p(x) in Equation 4.6 and Equation 4.7, respectively. Based on these definitions, consider the following,

(4.10)

We get the following quantity for mutual information between the random variable Θ and random sequence X₁^N,

(4.11)

Note that this quantity represents the gain in bits that the parameter θ creates; more about this quantity will be mentioned later.

We now define the conditional redundancy,

(4.12)

this quantifies how far a coding length function l is from the entropy where the parameter θ is known. Note that

(4.13)

Denote by c_n the collection of lossless codes for length-n inputs, and define the expected redundancy of a code l∈C_n by

(4.14)

The asymptotic expected redundancy follows,

(4.15)

assuming that the limit exists.

We can also define the minimum redundancy that incorporates the worst prior for parameter,

(4.16)

while keeping the best code. Similarly,

(4.17)

Let us derive R_n^–,

(4.18)

where C_n is the capacity of a channel from the sequence x to the parameter 4. That is, we try to estimate the parameter from the noisy channel.

In an analogous manner, we define

(4.19)

where Q is the prior induced by the coding length function l.

Note that

(4.20)

Therefore,

(4.21)

In fact, Gallager showed that R_n⁺=R_n^–. That is, the min-max and max-min redundancies are equal.

Let us revisit the Bernoulli source p_θ where θ∈Λ=[0,1]. From the definition of Equation 4.6, which relies on a uniform prior for the sources, i.e., w(θ)=1,∀θ∈Λ, it can be shown that there there exists a universal code with length function l such that

(4.22)

where h₂(p)=–plog(p)–(1–p)log(1–p) is the binary entropy. That is, the redundancy is approximately log(n) bits. Clarke and Barron 1 studied the weighting approach,

and constructed a prior that achieves R_n^–=R_n⁺ precisely for memoryless sources.

Theorem 5 1 For memoryless source with an alphabet of size r, θ=(p(0),p(1),⋯,p(r–1)),

(4.24)

where O_n(1) vanishes uniformly as n→∞ for any compact subset of Λ, and

(4.25)

is Fisher's information.

Note that when the parameter is sensitive to change we have large I(θ), which increases the redundancy. That is, good sensitivity means bad universal compression.

Denote

(4.26)

this is known as Jeffrey's prior. Using w(θ)=J(θ), it can be shown that R_n^–=R_n⁺.

(4.27)

Therefore, the Fisher information satisfies .

(4.28)

where we used the gamma function. It can be shown that

(4.29)

where

(4.30)

Similar to before, this universal code can be implemented sequentially. It is due to Krichevsky and Trofimov 2, its redundancy satisfies  Theorem 5 by Clarke and Barron 1, and it is commonly used in universal lossless compression.

Let us consider – on an intuitive level – why . Expending bits allows to differentiate between parameter vectors. That is, we would differentiate between each of the r–1 parameters with levels. Now consider a Bernoulli RV with (unknown) parameter θ.

One perspective is that with n drawings of the RV, the standard deviation in the number of 1's is . That is, levels differentiate between parameter levels up to a resolution that reflects the randomness of the experiment.

A second perspective is that of coding a sequence of Bernoulli outcomes with an imprecise parameter, where it is convenient to think of a universal code in terms of first quantizing the parameter and then using that (imprecise) parameter to encode the input x. For the Bernoulli example, the maximum likelihood parameter θ_ML satisfies

(4.31)

and plugging this parameter θ=θ_ML into p_θ(x) minimizes the coding length among all possible parameters, θ∈Λ. It is readily seen that

(4.32)

Suppose, however, that we were to encode with θ^'=θ_ML+Δ. Then the coding length would be

(4.33)

It can be shown that this coding length is suboptimal w.r.t. l_θML(