Transition Graphs and Transition Matrices

In Fig. 4.3 we show a phase space which is part of the real line. It is divided into three subintervals ($I,J,K$). The return map is shown. This return map shows that the interval $I$ is mapped onto the interval $K$. Similarly, $K$ is mapped onto $I$, and $J$ is mapped onto all three intervals. More mathematically, we could write $f(J) \supseteq I \cup J \cup K$. These relations are summarized on the right in a transition graph. The arrow from $I$ to $K$ says that $f(I)$ covers $K$, or that $K$ is in the image of $I$ (under $f$). Mathematically we write $f(I) \supseteq K$, and similarly for the arrow from $K$ to $I$. Since the image of $J$ covers everything, there are arrows from $J$ to everybody. These relations are also very conveniently summarized in a (Markov) transition matrix. The rows and columns are labeled by the indices for the partition (e.g., $I,J,K$). The matrix element $M_{ij}=0$ if $f(I_i)$ does not cover $I_j$. If $f(I_i) \supseteq I_j$, $M_{ij}=1$. The first row ($I$) of the $3 \times 3$ transition matrix for the return map of Fig. 4.3 is $(0,0,1)$. The entire matrix is

$$M = \left[ \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{array}\right]$$ (3)

Markov transition matrices are extremely useful for computing allowed and forbidden symbol sequences. They are also useful for computing topological entropy ( $h_T = \log(\lambda_M)$, where $\lambda_M$ is the largest eigenvalue of $M$).

Another example is given in Fig. 4.4. In this case the partition has four components. The return map is shown on the left and the transition graph is shown on the right. The Markov transition matrix is

$$M = \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array}\right]$$ (4)

Figure 3: (Alligood., p. 128). The interval is partitioned into three contiguous segments. The return map is shown on the left. Its transition graph is shown on the right.

Figure 4: (Alligood., p. 129). The interval is partitioned into four contiguous segments. The return map is shown on the left. Its transition graph is shown on the right.