In Claude Shannon's paper,A Mathematical Theory of Communication, it states that
- 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.
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).
He gives an example:
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 1/ 3 and 2/ 3 respectively. Either b or c is always followed by letter a. Thus a typical sequence is abacacacabacababacac
However, I still don't understand how the lack of coprimality gives a shift. Could someone please elaborate further?
Thanks
If you are familiar with Markov chain terminology, another way of phrasing this is that if the chain is $d$-periodic with $d > 1$ (v.s. aperiodic with $d = 1$), the vertices of the graph can be partitioned into $d$ equivalence classes $C_0, C_1, \dots, C_{d-1}$ on which the chain moves around cyclically. That is, if $x \in C_k$, then $P(x, y) > 0$ only if $y \in C_{k + 1}$ (where the indices are taken modulo $d$). (For example, see Exercise 1.6 of Levin, Peres, Wilmer - Markov Chains and Mixing Times.)
In the example given, we have $C_0 = \{ a \}$ and $C_1 = \{ b, c \}$, so there are essentially the same number of elements from each class in the sequence (up to a shift).