0.3 Universal coding for classes of sources  (Page 3/3)

and plugging this parameter $\theta ={\theta }_{ML}$ into $p_{\theta }\left(x\right)$ minimizes the coding length among all possible parameters, $\theta \in \Lambda$ . It is readily seen that

Suppose, however, that we were to encode with ${\theta }^{\text{'}}={\theta }_{ML}+\Delta$ . Then the coding length would be

It can be shown that this coding length is suboptimal w.r.t. $l_{{\theta }_{ML}}\left(x\right)$ by $n·O\left({\Delta }^2\right)$ bits. Keep in mind that doubling the number of parameter levels used by ouruniversal encoder requires an extra bit to encode the extra factor of 2 in resolution. It makes sense to expend this extra bit only if it buys us at least one other bit,meaning that $n·O\left({\Delta }^2\right)=1$ , which implies that we encode ${\theta }_{ML}$ to a resolution of $1/\sqrt{n}$ , corresponding to $O\left(\sqrt{n}\right)$ levels. Again, this is a redundancy of $\approx \frac{1}{2}log\left(n\right)$ bits per parameter.

Having described Rissanen's result intuitively, let us formalize matters. Consider $\{p_{\theta },\theta \in \Lambda \}$ , where $\Lambda \subset {\mathbb{R}}^K$ is a compact set. Suppose that there exists an estimator $\widehat{\theta }$ such that

where ${lim}_{c\to \infty }\delta \left(c\right)=0$ . Then we have the following converse result.

Theorem 6 (Converse to universal coding  [link] ) Given a parametric class that satisfies the above condition [link] , for all $ϵ>0$ and all codes $l$ that do not know $\theta$ ,

except for a class of $\theta$ in $B_{ϵ}\left(n\right)\subseteq \Lambda$ whose Lebesgue volume shrinks to zero as $n$ increases.

That is, a universal code cannot compress at a redundancy substantialy below $\frac{1}{2}log\left(n\right)$ bits per parameter. Rissanen also proved the following achievable result in his seminal paper.

Theorem 7 (Achievable to universal coding  [link] ) If $p_{\theta }\left(x\right)$ is twice differentiable in $\theta$ for every $x^n$ , then there exists a universal code such that $\forall \theta \in \Lambda :r_n(l,\theta )\le (1+ϵ)\frac{K}{2}\frac{log\left(n\right)}{n}$ .

Universal coding for piecewise i.i.d. sources

We have emphasized stationary parametric classes, but a parametric class can be nonstationary. Let us show how universal coding can be achieved for some nonstationary classes of sourcesby providing an example. Consider $\Lambda =\{0,1,...,n\}$ where

where $Q_1$ and $Q_2$ are both know i.i.d. sources. This is a piecewise i.i.d. source ; in each segment it is i.i.d., and there is an abrupt transition in statistics when the first segment ends and the second begins.

Here are two approaches to coding this source.

1. Encode the best index ${\theta }_{ML}$ using $\lceil log(n+1)\rceil$ bits, then encode $p_{{\theta }_{ML}}\left(x^n\right)$ . This is known as two-part code or plug-in ; after encoding the index, we plug the best parameter into the distribution. Clearly,
   $$\begin{array}{ccc}\hfill l\left(x\right)& =& \underset{0\le \theta \le n}{min}\lceil -log{p}_{\theta }\left(x\right)\rceil +\lceil log(n+1)\rceil \hfill \\ & \le & -log{p}_{\theta }\left(x\right)+log(n+1)+2.\hfill \end{array}$$
2. The second approach is a mixture , we allocate weights for all possible parameters,
   $$\begin{array}{ccc}\hfill l\left(x\right)& =& -log\left(\frac{1}{n+1},\sum _{i=0}^n,p_i,\left(x^n\right)\right)\hfill \\ & <& -log\left(\frac{1}{n+1},p_{{\theta }_{ML}},\left(x^n\right)\right)\hfill \\ & =& -log\left(p_{{\theta }_{ML}}\left(x\right)\right)+log(n+1).\hfill \end{array}$$

Merhav  [link] provided redundancy theorems for this class of sources. Algorithmic approaches to the mixture appear in Shamir and Merhav  [link] and Willems  [link] .

The theme that is common to both approaches, the plug-in and the mixture, is that they lose approximately $log\left(n\right)$ bits in encoding the location of the transition. Indeed, Merhav showed that the penalty for each transition in universal codingis approximately $log\left(n\right)$ bits  [link] . Intuitively, the reason that the redundancy required to encode the location of the transition is largerthan the $\frac{1}{2}log\left(n\right)$ from Rissanen  [link] is because the location of the transitionmust be described precisely to prevent paying a big coding length penalty in encoding segments using the wrong i.i.d. statistics. In contrast, in encoding our Bernoulli example an imprecision of $\frac{1}{\sqrt{n}}$ in encoding ${\theta }_{ML}$ in the first part of the code yields only an $O\left(1\right)$ bit penalty in the second part of the code.

It is well known that mixtures out-compress the plug-in. However, in many cases they do so by only a small amount per parameter. For example, Baron et al. showed that the plug-in for i.i.d. sourcesloses approximately 1 bit per parameter w.r.t. the mixture.