0.3 Universal coding for classes of sources

We have discussed several parametric sources, and will now start developing mathematical tools in order to investigate properties of universal codes that offer universal compression w.r.t.a class of parametric sources.

Preliminaries

Consider a class $\Lambda$ of parametric models, where the parameter set $\theta$ characterizes the distribution for a specific source within this class, $\{p_{\theta }(·),\theta \in \Lambda \}$ .

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

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

that a code that is good for two sources (distributions) $p_1$ and $p_2$ exists, modulo the one bit loss [link] . As an expansion beyond this idea, consider

where $w\left(\theta \right)$ is a prior.

Then

and

Moreover, it can be shown that

this result appears in Krichevsky and Trofimov  [link] .

Is the source $X$ implied by the distribution $p\left(x\right)$ an ergodic source? Consider the event ${lim}_{n\to \infty }\frac{1}{n}{\sum }_{i=1}^n{X}_i\le \frac{1}{2}$ . Owing to symmetry, in the limit of large $n$ the probability of this event under $p\left(x\right)$ must be $\frac{1}{2}$ ,

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\left(x\right)$ is not ergodic.

Recall the definitions of $p_{\theta }\left(x\right)$ and $p\left(x\right)$ in [link] and [link] , respectively. Based on these definitions, consider the following,

We get the following quantity for mutual information between the random variable $\Theta$ and random sequence $X_1^N$ ,

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

Redundancy

We now define the conditional redundancy ,

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

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

The asymptotic expected redundancy follows,

assuming that the limit exists.

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

while keeping the best code. Similarly,

Let us derive $R_n^{-}$ ,

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

In an analogous manner, we define