0.2 Source models

For i.i.d. sources, $D(P_1\left(x^n\right)\left|\right|P_2\left(x^n\right))=nD(P_1\left(x_i\right)\left|\right|P_2\left(x_i\right))$ , which means that the divergence increases linearly with $n$ . Not only does the divergence increase, but it does so by a constant per symbol.Therefore, based on typical sequence concepts that we have seen, for an $x^n$ generated by $P_1$ , its probability under $P_2$ vanishes. However, we can construct a distribution $Q$ whose divergence with both $P_1$ abd $P_2$ is small,

We now have for $P_1$ ,

On the other hand, $\frac{1}{n}D(P_1\left(x_1^n\right)\left|\right|Q\left(x_1^n\right))\ge 0$ [link] , and so

By symmetry, we see that $Q$ is also close to $P_2$ in the divergence sense.

Intuitively, it might seem peculiar that $Q$ is close to both $P_1$ and $P_2$ but they are far away from each other (in divergence terms). This intuition stems from the triangle inequality, which holds for all metrics. The contradiction is resolved by realizingthat the divergence is not a metric, and it does not satisfy the triangle inequality.

Note also that for two i.i.d. distributions $P_1$ and $P_2$ , the divergence

is linear in $n$ . If $Q$ were i.i.d., then $D(P_1\left(x^n\right)\parallel Q\left(x_1^n\right))$ must also be linear in $n$ . But the divergence is not increasing linearly in $n$ , it is upper bounded by 1. Therefore, we conclude that $Q(·)$ is not an i.i.d. distribution. Instead, $Q$ is a distribution that contains memory, and there is dependence in $Q$ between collections of different symbols of $x$ in the sense that they are either all drawn from $P_1$ or all drawn from $P_2$ . To take this one step further, consider $K$ sources with

then in an analogous manner to before it can be shown that

Sources with memory : Instead of the memoryless (i.i.d.) source,

let us now put forward a statistical model with memory,

Stationary source : To understand the notion of a stationary source, consider an infinite stream of symbols, $...,x_{-1},x_0,x_1,...$ . A complete probabilistic description of a stationary distribution is given by the collection of allmarginal distribution of the following form for all $t$ and $n$ ,

For a stationary source, this distribution is independent of $t$ .

Entropy rate : We have defined the first order entropy of an i.i.d. random variable [link] , and let us discuss more advanced concepts for sources with memory.Such definitions appear in many standard textbooks, for example that by Gallager  [link] .

1. The order- $n$ entropy is defined,
   $$H_n=\frac{1}{n}H(x_1,...,x_n)=-\frac{1}{n}E[log\left(P(x_1,...,x_n)\right)].$$
2. The entropy rate is the limit of order- $n$ entropy, $\overline{H}={lim}_{n\to \infty }{H}_n$ . The existence of this limit will be shown soon.
3. Conditional entropy is defined similarly to entropy as the expectation of the log of the conditional probability,
   $$H\left(x_n\right|x_1,...,x_{n-1})=-\frac{1}{n}E[log\left(P\left(x_n\right|x_1,...,x_{n-1})\right)],$$
   where expectation is taken over the joint probability space, $P(x_1,...,x_n)$ .

The entropy rate also satisfies $\overline{H}={lim}_{n\to \infty }H\left(x_n\right|x_1,...,x_n)$ .

Theorem 3 For a stationary source with bounded first order entropy, $H_1\left(x\right)<\infty$ , the following hold.

1. The conditional entropy $H\left(x_n\right|x_1,...,x_{n-1})$ is monotone non-increasing in n.
2. The order- $n$ entropy is not smaller than the conditional entropy,
   $$H_n\left(x\right)\ge H\left(x_n\right|x_1,...,x_{n-1}).$$
3. The order- $n$ entropy $H_n\left(x\right)$ is monotone non-increasing.
4. $\overline{H}\left(x\right)={lim}_{n\to \infty }{H}_n\left(x\right)={lim}_{n\to \infty }H\left(x_n\right|x_1,...,x_{n-1})$ .