Subshift of finite type

Last updated June 16, 2024

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.

Motivating examples

A (one-sided) shift of finite type is the set of all sequences, infinite on one end only, that can be made up of the letters $A,B,C$ , like $AAA\cdots ,ABAB\cdots ,\dots$ . A (two-sided) shift of finite type is similar, but consists of sequences that are infinite on both ends.

A subshift can be defined by a directed graph on these letters, such as the graph $A\to B\to C\to A$ . It consists of sequences whose transitions between consecutive letters are only those allowed by the graph. For this example, the subshift consists of only three one-sided sequences: $ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots$ . Similarly, the two-sided subshift described by this graph consists of only three two-sided sequences.

Other directed graphs on the same letters produce other subshifts. For example, adding another arrow $A\to C$ to the graph produces a subshift that, instead of containing three sequences, contains an uncountably infinite number of sequences.

Markov and non-Markov measures

Given a Markov transition matrix and an invariant distribution on the states, we can impose a probability measure on the set of subshifts. For example, consider the Markov chain given on the left on the states $A,B_{1},B_{2}$ , with invariant distribution $\pi =(2/7,4/7,1/7)$ . If we "forget" the distinction between $B_{1},B_{2}$ , we project this space of subshifts on $A,B_{1},B_{2}$ into another space of subshifts on $A,B$ , and this projection also projects the probability measure down to a probability measure on the subshifts on $A,B$ .

The curious thing is that the probability measure on the subshifts on $A,B$ is not created by a Markov chain on $A,B$ , not even multiple orders. Intuitively, this is because if one observes a long sequence of $B^{n}$ , then one would become increasingly sure that the $Pr(A|B^{n})\to {\frac {2}{3}}$ , meaning that the observable part of the system can be affected by something infinitely in the past.^[1]^[2]

Conversely, there exists a space of subshifts on 6 symbols, projected to subshifts on 2 symbols, such that any Markov measure on the smaller subshift has a preimage measure that is not Markov of any order (Example 2.6 ^[2]).

Definition

Let $V$ be a finite set of $n$ symbols (alphabet). Let $X$ denote the set $V^{\mathbb {Z} }$ of all bi-infinite sequences of elements of $V$ together with the shift operator $T$ . We endow $V$ with the discrete topology and $X$ with the product topology. A symbolic flow or subshift is a closed $T$ -invariant subset $Y$ of $X$ ^[3] and the associated language $L Y$ is the set of finite subsequences of $Y$ .^[4]

Now let $A$ be an $n \times n$ adjacency matrix with entries in ${0, 1}.$ Using these elements we construct a directed graph $G = (V, E)$ with $V$ the set of vertices and $E$ the set of edges containing the directed edge $x \to y$ in $E$ if and only if $A x, y = 1$ . Let $Y$ be the set of all infinite admissible sequences of edges, where by admissible it is meant that the sequence is a walk of the graph, and the sequence can be either one-sided or two-sided infinite. Let $T$ be the left shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. A subshift of finite type is then defined as a pair $(Y, T)$ obtained in this way. If the sequence extends to infinity in only one direction, it is called a one-sided subshift of finite type, and if it is bilateral, it is called a two-sided subshift of finite type.

Formally, one may define the sequences of edges as

\Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.

This is the space of all sequences of symbols such that the symbol $p$ can be followed by the symbol $q$ only if the $(p, q)$ -th entry of the matrix $A$ is 1. The space of all bi-infinite sequences is defined analogously:

\Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.

The shift operator $T$ maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.

\displaystyle (T(x))_{j}=x_{j+1}.

Clearly this map is only invertible in the case of the two-sided shift.

A subshift of finite type is called transitive if $G$ is strongly connected: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense.

An important special case is the full $n$ -shift: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The full $n$ -shift corresponds to the Bernoulli scheme without the measure.

Terminology

By convention, the term shift is understood to refer to the full $n$ -shift. A subshift is then any subspace of the full shift that is shift-invariant (that is, a subspace that is invariant under the action of the shift operator), non-empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, subshifts of finite type are called simply shifts of finite type. Subshifts of finite type are also sometimes called topological Markov shifts.

Examples

Many chaotic dynamical systems are isomorphic to subshifts of finite type; examples include systems with transverse homoclinic connections, diffeomorphisms of closed manifolds with a positive metric entropy, the Prouhet–Thue–Morse system, the Chacon system (this is the first system shown to be weakly mixing but not strongly mixing), Sturmian systems and Toeplitz systems.^[5]

Generalizations

A sofic system is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. For example, if one only watches the output from a hidden Markov chain, then the output appears to be a sofic system.^[1] It may be regarded as the set of labellings of paths through an automaton: a subshift of finite type then corresponds to an automaton which is deterministic.^[6] Such systems correspond to regular languages.

Context-free systems are defined analogously, and are generated by phrase structure grammars.

A renewal system is defined to be the set of all infinite concatenations of some fixed finite collection of finite words.

Subshifts of finite type are identical to free (non-interacting) one-dimensional Potts models ( $n$ -letter generalizations of Ising models), with certain nearest-neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space^{[ when defined as? ]} (continuous with respect to the product topology, defined below); the partition function and Hamiltonian are explicitly expressible in terms of this function.^{[ clarification needed ]}

Subshifts may be quantized in a certain way, leading to the idea of the quantum finite automata.

Topology

A subshift has a natural topology, derived from the product topology on $V^{\mathbb {Z} },$ where

V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}

and $V$ is given the discrete topology. A basis for the topology of $V^{\mathbb {Z} },$ which induces the topology of the subshift, is the family of cylinder sets

C_{t}[a_{0},\ldots ,a_{s}]=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}

The cylinder sets are clopen sets in $V^{\mathbb {Z} }.$ Every open set in $V^{\mathbb {Z} }$ is a countable union of cylinder sets. Every open set in the subshift is the intersection of an open set of $V^{\mathbb {Z} }$ with the subshift. With respect to this topology, the shift $T$ is a homeomorphism; that is, with respect to this topology, it is continuous with continuous inverse.

The space $V^{\mathbb {Z} }$ is homeomorphic to a Cantor set.

Metric

A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is the $p$ -adic metric. In fact, both the one- and two-sided shift spaces are compact metric spaces.

Measure

A subshift of finite type may be endowed with any one of several different measures, thus leading to a measure-preserving dynamical system. A common object of study is the Markov measure, which is an extension of a Markov chain to the topology of the shift.

A Markov chain is a pair $(P, π)$ consisting of the transition matrix, an $n \times n$ matrix $P = (p ij)$ for which all $p ij \geq 0$ and

\sum _{j=1}^{n}p_{ij}=1

for all $i$ . The stationary probability vector $π = (π i)$ has all $π i \geq 0$ , ${\textstyle \sum \pi _{i}=1}$ and has

\sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.

A Markov chain, as defined above, is said to be compatible with the shift of finite type if $p ij = 0$ whenever $A ij = 0$ . The Markov measure of a cylinder set may then be defined by

\mu (C_{t}[a_{0},\ldots ,a_{s}])=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}

The Kolmogorov–Sinai entropy with relation to the Markov measure is

s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}

Zeta function

The Artin–Mazur zeta function is defined as the formal power series

\zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),

where $Fix(T n)$ is the set of fixed points of the $n$ -fold shift.^[7] It has a product formula

\zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\

where $γ$ runs over the closed orbits.^[7] For subshifts of finite type, the zeta function is a rational function of $z$ :^[8]

\zeta (z)=(\det(I-zA))^{-1}\ .

Notes

1 2 Sofic Measures: Characterizations of Hidden Markov Chains by Linear Algebra, Formal Languages, and Symbolic Dynamics - Karl Petersen, Mathematics 210, Spring 2006, University of North Carolina at Chapel Hill
1 2 Boyle, Mike; Petersen, Karl (2010-01-13), Hidden Markov processes in the context of symbolic dynamics, arXiv: 0907.1858
↑ Xie (1996) p.21
↑ Xie (1996) p.22
↑ Matthew Nicol and Karl Petersen, (2009) "Ergodic Theory: Basic Examples and Constructions", Encyclopedia of Complexity and Systems Science, Springer https://doi.org/10.1007/978-0-387-30440-3_177
↑ Pytheas Fogg (2002) p.205
1 2 Brin & Stuck (2002) p.60
↑ Brin & Stuck (2002) p.61

Related Research Articles

In mathematics, one can often define a direct product of objects already known, giving a new one. This induces a structure on the Cartesian product of the underlying sets from that of the contributing objects. More abstractly, one talks about the product in category theory, which formalizes these notions.

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members. The number of elements is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an arbitrary index set.

In mathematical analysis and in probability theory, a σ-algebra on a set X is a nonempty collection Σ of subsets of X closed under complement, countable unions, and countable intersections. The ordered pair $is called a measurable space.$

In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points, along with an additional structure called a topology, which can be defined as a set of neighbourhoods for each point that satisfy some axioms formalizing the concept of closeness. There are several equivalent definitions of a topology, the most commonly used of which is the definition through open sets, which is easier than the others to manipulate.

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In mathematics, a measure-preserving dynamical system is an object of study in the abstract formulation of dynamical systems, and ergodic theory in particular. Measure-preserving systems obey the Poincaré recurrence theorem, and are a special case of conservative systems. They provide the formal, mathematical basis for a broad range of physical systems, and, in particular, many systems from classical mechanics as well as systems in thermodynamic equilibrium.

In mathematics, specifically order theory, a well-quasi-ordering or wqo on a set $is a quasi-ordering of for which every infinite sequence of elements from contains an increasing pair with$

In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenomena of solid-state physics. The strength of the Potts model is not so much that it models these physical systems well; it is rather that the one-dimensional case is exactly solvable, and that it has a rich mathematical formulation that has been studied extensively.

<span class="mw-page-title-main">Dyadic transformation</span> Doubling map on the unit interval

The dyadic transformation is the mapping

A Dynkin system, named after Eugene Dynkin, is a collection of subsets of another universal set $satisfying a set of axioms weaker than those of 𝜎-algebra. Dynkin systems are sometimes referred to as 𝜆-systems or d-system . These set families have applications in measure theory and probability.$

In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes. Bernoulli schemes appear naturally in symbolic dynamics, and are thus important in the study of dynamical systems. Many important dynamical systems exhibit a repellor that is the product of the Cantor set and a smooth manifold, and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift. This is essentially the Markov partition. The term shift is in reference to the shift operator, which may be used to study Bernoulli schemes. The Ornstein isomorphism theorem shows that Bernoulli shifts are isomorphic when their entropy is equal.

In mathematics, the cylinder sets form a basis of the product topology on a product of sets; they are also a generating family of the cylinder σ-algebra.

In mathematics, a $π$ -system on a set $is a collection of certain subsets of such that$

In mathematics, ergodicity expresses the idea that a point of a moving system, either a dynamical system or a stochastic process, will eventually visit all parts of the space that the system moves in, in a uniform and random sense. This implies that the average behavior of the system can be deduced from the trajectory of a "typical" point. Equivalently, a sufficiently large collection of random samples from a process can represent the average statistical properties of the entire process. Ergodicity is a property of the system; it is a statement that the system cannot be reduced or factored into smaller components. Ergodic theory is the study of systems possessing ergodicity.

In topology, a branch of mathematics, the ends of a topological space are, roughly speaking, the connected components of the "ideal boundary" of the space. That is, each end represents a topologically distinct way to move to infinity within the space. Adding a point at each end yields a compactification of the original space, known as the end compactification.

In mathematics, a topological space $is said to be limit point compact or weakly countably compact if every infinite subset of has a limit point in This property generalizes a property of compact spaces. In a metric space, limit point compactness, compactness, and sequential compactness are all equivalent. For general topological spaces, however, these three notions of compactness are not equivalent.$

In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms. The most widely studied shift spaces are the subshifts of finite type and the sofic shifts.

In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties and the global dynamics that result.

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion.

In mathematics, a Markov odometer is a certain type of topological dynamical system. It plays a fundamental role in ergodic theory and especially in orbit theory of dynamical systems, since a theorem of H. Dye asserts that every ergodic nonsingular transformation is orbit-equivalent to a Markov odometer.

References

Brin, Michael; Stuck, Garrett (2002). Introduction to Dynamical Systems (2nd ed.). Cambridge University Press. ISBN 0-521-80841-3.
David Damanik, Strictly Ergodic Subshifts and Associated Operators , (2005)
Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
Natasha Jonoska, Subshifts of Finite Type, Sofic Systems and Graphs , (2000).
Michael S. Keane, Ergodic theory and subshifts of finite type, (1991), appearing as Chapter 2 in Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X (Provides a short expository introduction, with exercises, and extensive references.)
Lind, Douglas; Marcus, Brian (1995). An introduction to symbolic dynamics and coding. Cambridge University Press. ISBN 0-521-55124-2. Zbl 1106.37301.
Teschl, Gerald (2012). Ordinary Differential Equations and Dynamical Systems. Providence: American Mathematical Society. ISBN 978-0-8218-8328-0.
Xie, Huimin (1996). Grammatical Complexity and One-Dimensional Dynamical Systems. Directions in Chaos. Vol. 6. World Scientific. ISBN 9810223986.