0.2 Source models  (Page 3/4)

Therefore, the space of Markov sources covers the stationary ergodic sources in the limit of large $k$ .

Unifilar sources : For unifilar sources, it is possible to reconstruct the set of states that a source went through by looking at the output sequence. In the Markov case we have $S_i=\left(X_{i-k}^{i-1}\right)$ , but in general it may be more complicated to determine the state.

To put us on a concrete basis for analysis of unifilar sources, consider a source with $M$ states, $S=\{1,2,...,M\}$ , and an alphabet $\alpha =\{1,2,...,r\}$ . In each time step, the source outputs a symbol and moves to a new state. Denote the output sequence by $x=x_1{x}_2\cdots x_n$ , and the state sequence by $s=s_1{s}_2\cdots s_n$ , where $s_i\in S$ and $x_i\in \alpha$ . Denote also

This is a first-order time-homogeneous Markov source. The probability that the next symbol is $a$ follows,

There exists a deterministic function,

this is called the next state function. Given that we start at some state $S_1=s_1$ , the probability for the sequence of states $s_1,...,s_n$ is given by

Note the relation

To summarize, unifilar sources can be described by a state machine style of diagram as illustrated in [link] .

Given that an initial state was fixed, a unifilar source with $M$ states and an alphabet of size $r$ can be expressed with $M(r-1)$ parameters. If the initial state is a random variable, then there are $M-1$ parameters that define probabilities for the initial state, giving $M(r-1)+M-1=Mr-1$ parameters in total. In the Markov case, we have $M=r^k$ , it is a special type of unifilar source.

A state $S$ is called transient if once we leave it we cannot go back; $S_1$ is such a state in the exaple. A subset $E$ of states is called irreducible if from every state in $E$ it is possible to move to every other state in $E$ in a finite number of steps, and it is impossible to leave $E$ . We see that $\{S_2,S_3\}$ and $\left\{S_4\right\}$ are irreducible sets. The states can be decomposed (in a single unique way) into a set of transient states and irreducible components. It can be shown that withprobability 1 the time spent in transient states is finite, and after that the source enters one of the irreducible components and stays there forever.Finally, in an ergodic source there may only be one irreducible component. Therefre, our example source is not ergodic because it contains two such components.

Given that we are in some state $s$ , which belongs to an irreducible component, the number of time steps until we return to $s$ for the first time is a random variable called recurrence time . The period of an irreducible component is the largest integer that divides all possible recurrence times.