I am reading A Mathematical Theory of Communication. The second requirement of an ergodic process confuses me (emphasis mine):

All the examples of artificial languages given above are ergodic. This property is related to the structure of the corresponding graph. If the graph has the following two properties the corresponding process will be ergodic:

  1. The graph does not consist of two isolated parts $A$ and $B$ such that it is impossible to go from junction points in part $A$ to junction points in part $B$ along lines of the graph in the direction of arrows and also impossible to go from junctions in part $B$ to junctions in part $A$.

  2. A closed series of lines in the graph with all arrows on the lines pointing in the same orientation will be called a “circuit.” The “length” of a circuit is the number of lines in it. Thus in Fig. 5 series BEBES is a circuit of length 5. The second property required is that the greatest common divisor of the lengths of all circuits in the graph be one.

The author later elaborates

If the first condition is satisfied but the second one violated by having the greatest common divisor equal to $d > 1$, the sequences have a certain type of periodic structure. The various sequences fall into $d$ different classes which are statistically the same apart from a shift of the origin (i.e., which letter in the sequence is called letter 1). By a shift of from $0$ up to $d - 1$ any sequence can be made statistically equivalent to any other. A simple example with $d =2$ is the following: There are three possible letters $a, b, c$. Letter $a$ is followed with either $b$ or $c$ with probabilities $\frac{1}{3}$ and $\frac{2}{3}$ respectively. Either $b$ or $c$ is always followed by letter $a$. Thus a typical sequence is


This type of situation is not of much importance for our work.

But unfortunately, I still didn't get his point. Can you show me how to perform "a shift of from $0$ up to $d - 1$" to make two sequences statistically equivalent? In fact, the process already seems ergodic to me, but that's just my intuition, and I cannot justify my argument with rigorous reasoning.

In addition, what makes the above-mentioned process not of much importance in communication?


This is my understanding: the statistics of the source described in the paper depend on which character is produced first. If the first character is $a$, then one of the source properties is that letters in odd positions are always $a$. However, if the first letter is $b$ (in other words, a shift of $1$ in the circuit), then letters in odd positions can be either $b$ or $c$. This is what makes the source non-ergodic.

Note that the statistics when choosing $b$ as first letter and $c$ as first letter are exactly the same. In other words, there are $d=2$ different classes of sequences, and those in each class have the same statistics.

Regarding the importance of these sources: for one, Shannon's theorems depend on the source being ergodic. From a more practical standpoint (and this is purely my interpretation), non-ergodic sources are not good models for real-world processes; referring back to the example, no practical language produces repeated letters in a fixed periodic pattern.

I recommend reading "An Introduction to Information Theory: Symbols, Signals and Noise" by John R. Pierce, along with Shannon's paper. It explains many of the concepts in the paper in a very didactic manner. For example, it takes four pages to very clearly explain ergoidc sources, with nice examples.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.