0.6 Compression of nonparametric sources

Consider a stationary ergodic source, where we no longer assume that it is parametric. We need to define notions of probability that fit the universal framework. For this,we study Kac's lemma  [link] .

We have a stationary source, $\{...,X_{-n},X_{-n+1},...,X_0,X_1,...\}$ , $z=X_{-\ell +1}^0=\{X_{-\ell +1},X_{-\ell +2},...,X_0\}$ . Define $N_r$ as the number of shifts forward of a window of length $\ell$ until we see $z$ again; this is called recurrence time. Define

e.g., $Y_0=1$ , then $N_r$ is the smallest positive number for which $Y_k=1$ . Note that ${\left\{Y_k\right\}}_{-\infty }^{+\infty }$ is a binary stationary ergodic source. Define $Q_k=Pr\{Y_k=1;1\le j\le k-1,Y_j=0|Y_0=1\}$ . Then the average recurrence time can be computed, $\mu ={\sum }_{\ell =1}^{\infty }\ell Q_{\ell }=E\left[N_r\right]$ . We can now present Kac's lemma.

Lemma 3 [link] $\mu =\frac{1}{Pr(Y=1)}$ and $E\left[N_r,=\mu |,X_{-\ell +1}^0,=,z\right]$ = $\frac{1}{Pr\left(z\right)}$ .

Let $A=\{Y_n=1\text{for}\text{some}-\infty <n<+\infty \}$ . Because $z$ just appeared, then its probability is positive. We will prove that $\mu =\frac{Pr\left(A\right)}{Pr(Y_0=1)}$ .

Define $B^{+}=\{Y_n=1,\text{for}\text{some}0\le n<\infty \}$ , and $B^{-}=\{Y_n=1,\text{for}\text{some}n<0\}$ . Then $A=B^{+}\bigcup B^{-}=(B^{+}\bigcap B^{-})\bigcup \left(B^{+},\bigcap ,{\left(B^{-}\right)}^C\right)\bigcup \left({\left(B^{+}\right)}^C,\bigcap ,B^{-}\right)$ . We claim that $Pr\left(B^{+},\bigcap ,{\left(B^{-}\right)}^C\right)=Pr\left({\left(B^{+}\right)}^C,\bigcap ,B^{-}\right)=0$ . This can be shown formally, but is easily seen by realizing that if $z$ appears at any time $n$ (say, positive) then it must appear at some negative time $n$ with probability 1, because its probability is positive.

Therefore, we have

Therefore, $\mu =\frac{Pr\left(A\right)}{Pr(Y_0=1)}.$ We conclude the proof by noting that $Pr\left(A\right)=0$ .

Let us now develop a universal coding technique for stationary sources. Recall $H_{\ell }=\frac{1}{\ell }E[-log(Pr\left(X_1^{\ell }\right))]$ . The asymptotic equipartition property (AEP) of information theory  [link] gives

where ${lim}_{\ell \to \infty }ϵ(\delta ,\ell )=0$ . Define in this context a typical set $T(\delta ,\ell )$ that satisfies

For a typical sequence $z$ , $E\left[N_r\right|X_1^{\ell }=z]\le 2^{\ell (H_{\ell }+\delta )}$ . Then

Consider our situation, we have a source with memory of length $n$ and want to transmit $X_1^{\ell }$ .

1. Choose $n=2^{\ell (H_{\ell }+2\delta )}$ .
2. For $z=X_1^{\ell }$ , find the value of $N_r$ if it appears in memory.
3. If it appears, then transmit a 0 flag bit followed by the value of $N_r$ .
4. Else transmit a 1 followed by the uncompressed $z$ .

Transmitting $z$ via $N_r$ requires $\lceil log\left(N_r\right)\rceil$ bits, and so the expected coding length is

After we normalize by $\ell$ , the per symbol length converges to $\frac{2}{\ell }+H_{\ell }+2\delta$ .

Note that this analysis assumes that the entropy $H_{\ell }$ for a block of $\ell$ symbols is known. If not, then we can have several sets that are each adjusted for some differententropy level.

Universal coding of the integers

Coding of an index also appears in other information theoretic problems such as indexing a coset in distributed source coding and a codeword in lossycoding. What are good ways to encode the index?

If the index $n$ lies in the range $n\in \{1,...,N\}$ and $N$ is known, then we can encode the index using $\lceil log\left(N\right)\rceil$ bits. However, sometimes the index can be unbounded, or there could be an(unknown) distribution that biases us strongly toward smaller indices. Therefore, we are interested in a universal encoding of the integerssuch that each $n$ is encoded using roughly $log\left(n\right)$ bits.