0.2 Source models  (Page 2/4)

Proof. Part (1):

Part (2):

Part (3): This comes from the fist equality in the proof of (2), because we have the average of a monotonely non-increasing sequence.

Part (4): Both sequences are monotone non-increasing (parts (1) and (3)) and bounded below (by zero). Therefore, they both have a limit. Denote $\overline{H}\left(x\right)={lim}_{n\to \infty }{H}_n\left(x\right)$ and $\tilde{H}\left(x\right)={lim}_{n\to \infty }H\left(x_n\right|x_1,...,x_{n-1})$ .

Owing to part(2), $\overline{H}\ge \tilde{H}$ . Therefore, it suffices to prove $\tilde{H}\ge \overline{H}$ .

Now fix $n$ and take the limit for large $m$ . The inequality $\overline{H}\le \tilde{H}$ appears, which proves that both limits are equal.

Coding theorem : Theorem 3 yields for fixed to variable length coding that for a stationary source, there exists a lossless code such that the compressionrate ${\rho }_n$ obeys,

This can be proved, for example, by choosing $l(x_1,...,x_n)=\lceil -logP(x_1,...,x_n)\rceil$ , which is a Shannon code.As $n$ is increased, the compression rate ${\rho }_n$ converges to the entropy rate.

We also have a converse theorem for lossless coding of stationary sources. That is, ${\rho }_n\ge H_n\left(x\right)\ge \overline{H}$ .

Stationary ergodic sources

Consider the sequence $x=(...,x_{-1},x_0,x_1,...)$ . Let $x^{\text{'}}=S_x$ denote a step $\forall n\in \mathbb{Z}$ , $x_n^{\text{'}}=x_{n+1}$ , where $S_x^i$ takes $i$ steps. Let $f_k\left(x\right)$ be a function that operates on coordinates $(x_0,...,x_{k-1})$ . An ergodic source has the property that empirical averages converge to statistical averages,

In block codes we want

We will be content with convergence in probability, and a.s. convergence is better.

Theorem 4 Let $X$ be a stationary ergodic source with $H_1\left(x\right)<\infty$ , then for every $ϵ>0,\delta >0$ , there exists $n_0(\delta ,ϵ)$ such that $\forall n\ge n_0(\delta ,ϵ)$ ,

where $I(x_1,...,x_n)=-log(Pr(x_1,...,x_n))$ .

The proof of this result is quite lengthy. We discussed it in detail, but skip it here.

Theorem 4 is called the ergodic theorem of information theory or the ergodic theorem of entropy. Shannon (48') proved convergence in probability for stationary ergodic Markov sources.McMillan (53') proved $L^1$ convergence for stationary ergodic sources. Brieman (57'/60') proved convergence with probability 1 for stationary ergodic sources.

Parametric models of information sources

In this section, we will discuss several parametric models and see what their entropy rate is.

Memoryless sources : We have seen for memoryless sources,

where there are $r-1$ parameters in total,

the parameters are denoted by $\theta$ , and $\alpha =\{1,2,...,r\}$ is the alphabet.

Markov sources : The distribution of a Markov source is defined as

where $n\ge k$ . We must define ${\left\{p(a_1,a_2,...,a_k)\right\}}_{(a_1,a_2,...a_k)\in {\alpha }^k}$ initial probabilities and transition probabilities, $\left\{p\left(a_{k+1}\right|a_1^k)\right\}$ . There are $r^k-1$ initial probabilities and $(r-1)r^k$ transition probabilities, giving a total of $r^{k+1}-1$ parameters. Note that