0.2 Source models  (Page 4/4)

An irreducible component with period at least 2 is called periodic. In contrast, a component with period 1 is called aperiodic or ergodic, because the probabilities in being ineach of the states eventually converge to the statistical averages. Note that a periodic component cannot yield a stationary distribution.

An irreducible component $E$ contains asymptotic state probabilities given by the solution of the equations,

Additionally,

for aperiodic $E$ . The convergence of $\text{Pr}\{S_t=s|S_1=s^{\text{'}}\}$ to $q\left(s\right)$ is exponential in $t$ , and depends on the eigen-values of the transition probability matrix. In periodic components we donot have stationarity, but the following weaker property still holds,

The entropy rate of the output of a unifilar source at state $s$ is given by,

To see this, we begin with a lemma.

Lemma 1 For a unifilar source,

Proof $Pr\left\{X_n\right|X_1^{n-1},S_1\}=\text{Pr}\left\{X_n\right|S_n,X_1^{n-1},S_1\}$ , because $S_n$ is deterministic in $S_{n-1}$ , $X_{n-1}$ . Therefore, owing to the Markov property,

We can now compute the entropy,

Having proved the lemma, we can move forward with the computation of entropy rate. Note that

and

Therefore,

It is not complicated to show that this is the entropy rate of the unifilar source $X$ , provided that it is irreducible and aperiodic.

Tree Sources : Tree sources are very useful in modeling and processing text and data files in general.Consequently, tree sources have been studied in great detail. We will introduce these source models here and later in [link] discuss algorithms for universal lossless compression of these sources.

In a tree source, states are arranged as contexts , where a context consists of the last several symbols generatedby the source. The unique property of a context tree source is that states are arranged as leaves of a tree, and the state can be identified by following labels of the branches of the tree based onprevious symbols, until we reach a leaf.

This input sequence corresponds to the following sequence of states,

As before, for every state (leaf) there exist conditional probabilities for generating the next symbol. That said, and maybe surprisingly, a tree source is not necessarily a unifilar source. On the one hand, states can be observed from the source symbols. On the other hand, when transitioning from a “shallow" leaf to a deep leaf in the tree, the symbol currently being generated does not contain enough information to define the new state. To address this problem, extra states can be added to the tree. On the other hand, adding extra states to a tree source might make the context tree less efficient,because it increases the number of states; see for example the detailed discussion of expansion of tree machines by Martín et al.  [link] .

Hidden Markov models : Consider the following state transition probabilities,

The parameter space can be defined,

there are $M(M·r-1)$ parameters in total.

Note that

and

It is important to emphasize that the next state is not deterministic. This type of behavior is called a hidden Markov model (HMM).

What are the typical sets for HMM sources? Recall that for an i.i.d. source we saw

this is the main concept underlying the method of types. For a unifilar source,

For an HMM, there is no such partition into typical sets.