Symbolic Dynamics
Last update: 07 Jul 2025 12:03
First version: 5 July 2001, major expansion 26 October 2005
A useful method for studying discrete-time dynamical systems with continuous
state spaces. The basic idea is to take the state space and partition it into
a finite number of regions, each of which you label with some symbol. Each
point in the state space then gives you an infinite sequence of symbols: the
symbol for the cell of the partition of the original point, the symbol for the
cell of its first iterate, its second, and so forth. Normally this involves
some loss of information, since you're going from continuous to discrete
values. The symbolic dynamics are often stochastic even when the continuous
dynamics are deterministic, for starters. So why do this?
One reason is that the dynamics as such are drastically simplified.
Let me introduce some notation here. Write \( x \) for the continuous
state, \( f \) for the map, and \( \phi \) for the function taking
states to symbols. Then the symbol sequence \( s = \phi(x) \phi(f(x))
\phi(f^2(x)) \phi(f^3(x)) \ldots \) . Now suppose I started with
\( f(x) \) instead; my sequence would be
\( \phi(f(x)) \phi(f^2(x)) \phi(f^3(x)) \ldots \) . So the dynamics on
the space of symbol sequences just consists of shifting to the right:
\( s_0 s_1 s_2 \ldots \mapsto s_1 s_2 \ldots \) . (This is called
the shift map.) This is completely trivial. All of the structure in
the problem has been shifted from the map to space of sequences. For instance,
certain subsequences may not occur at all, or differ in probability. But we
have a lot of tools for studying sets of discrete symbol sequences --- not just
stochastic process theory, but the theory of formal
languages, for instance, so that we can write out the abstract automata
which generate the symbol sequences produced by the dynamics.
The other reason for using symbolic dynamics is that there are important
cases where one can find generating partitions --- mappings into
symbols where there is a one-to-one correspondence between continuous states
and the symbol sequences they generate. In these cases, studying the symbolic
dynamics is completely equivalent to studying the original dynamics.
Remarkably enough, even with a generating partition, the symbolic dynamics can
be stochastic for an underlying deterministic system. In this way, for
instance, one can show that some kinds of (sufficiently chaotic) deterministic
dynamics are in a sense completely equivalent to sources of independent,
identically-distributed random variables.
To go off on a tangent, there's something of a movement in cognitive science which sets up an opposition
between computation, conceived in the usual symbol-manipulation sense, and
continuous nonlinear dynamics. This seems to me quite wrong-headed, if only because the
existence of generating partitions shows how symbol-manipulating computation
can be completely equivalent to a dynamical system. Computation
is intrinsic to dynamics, but that's another
topic.
The most fundamental reason I like symbolic dynamics is that I know a lot
of tricks for predicting discrete stochastic
processes, and want to exploit them as widely as possible.
Recommended, big picture:
- Remo Badii and Antonio Politi, Complexity: Hierarchical
Structures and Scaling in Physics [Review, with some more explanation]
- C. Beck and F. Schögl, Thermodynamics of Chaotic
Systems [Applying the thermodynamic formalism to symbolic dynamics]
- R. L. Devaney, A First Course in Chaotic Dynamical
Systems
- Bruce P. Kitchens, Symbolic Dynamics [More algebraic
and less dynamical or probabilistic than I'd hoped. But useful.]
- Douglas Lind and Brian Marcus, Introduction to Symbolic
Dynamics and Coding
Recommended, close ups:
- R. L. Adler and B. Weiss, "Entropy, a Complete Metric Invariant for
Automorphisms of the Torus", Proceedings of the National Academy of
Sciences (USA) 57 (1967): 1573--1576
[PDf reprint. Classic
and cute, if somewhat specialized, paper.]
- Peter beim Graben and Harald Atmanspacher, "Complementarity in
Classical Dynamical Systems", nlin.CD/0407046 [A really cool,
if rather counter-intuitive, result about how one can get something which looks
rather like quantum-mechanical "complementarity" (i.e., incompatible
observables) from differing symbolic partitions of a single classical dynamical
system. I hasten to add that this is not how I think quantum mechanics works, and I'm pretty sure
it's not how beim Graben and Atmanspacher think it works.]
- P.-M. Binder and Juan M. Pedraza, "Nonregular Languages in the
Kicked Rotor," Physical Review E 62 (2000):
R5883--R5886
- Erik Bollt, Pawel Gora, Andrzej Ostruszka, and Karol Zyczkowski,
"Basis Markov Partitions and Transition Matrices for Stochastic Systems",
arxiv:nlin.CD/0605017
- Erik M. Bollt, Theodore Stanford, Ying-Cheng Lai and Karol
Zyczkowski, "What Symbolic Dynamics Do We Get with a Misplaced Partition? On
the Validity of Threshold Crossings Analysis of Chaotic Time-Series,"
Physica D 154 (2001): 259--286 [Short answer: You
get really wrong symbolic dynamics.]
- Milena C. Cuellar and P.-M. Binder, "Reducing Noise in Discretized
Time Series", Physical Review E 64 (2001): 046211
- Ruslan L. Davidchack, Ying-Cheng Lai, Erik M. Bollt and Mukeshwar
Dhamala, "Estimating Generating Partitions of Chaotic Systems by Unstable
Periodic Orbits," Physical Review E 61 (2000):
1353--1356
- Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas,
"Effective symbolic dynamics, random points, statistical behavior, complexity
and entropy", arxiv:0801.0209
[All, not almost all, Martin-Lof points are statistically
typical.]
- Yoshito Hirata, Kevin Judd and Kazuyuki Aihara, "Characterizing
chaotic response of a squid axon through generating partitions", Physics Letters
A 346 (2005): 141--147
- Yoshiro Hirata, Kevin Judd and Devin Kilaminster, "Estimating a
generating partition from observed time series: Symbolic shadowing", Physical Review
E 70 (2004): 016215 [A very elegant answer to "how
do we actually find a generating partition then?"]
- Matthew B. Kennel and Michael Buhl, "Estimating good discrete
partitions from observed data: symbolic false nearest neighbors", nlin.CD/0304054 =
Physical Review Letters 91 (2003): 084102
- X. Z. Tang, E. R. Tracy, A. D. Boozer, A. deBrauw, and R. Brown, "Symbol sequence statistics in noisy chaotic signal reconstruction", Physical Review E 51 (1995): 3871
Sort-of recommended:
- Elena S. Dimitrova, John J. McGee, and Reinhard C. Laubenbacher,
"Discretization of Time Series
Data", q-bio.OT/0505028
[There are some interesting ideas here, and I like that they tested the ability
of their discretization method to preserve information (in some sense) within
and across time-series. But they don't compare its ability to
preserve information with other discretization schemes (say, applying
randomly-chosen cut-offs), and gave me no sense of why the scheme itself should
work.]
To read:
- Jon Aaronson and Hotoshi Nakada, "Exchangeable, Gibbs and
equilibrium measures for Markov subshifts", math.PR/0505011
- Fatihcan Atay, Sarika Jalan and Jürgen Jost, "Randomness,
chaos, and
structure", arxiv:0711.4293
- Rajeev K. Azad, J. Subba Rao, and Ramakrishna Ramaswamy, "Symbol
sequence analysis of climatic time signals",
Nonlinear
Analysis: Real-World Applications 5 (2004):
487--500
- Peter beim Graben, J. Douglas Saddy, Matthias Schlesewsky and
Jürgen Kurths, "Symbolic Dynamics of Event-Related Brain Potentials,"
Physical Review E 62 (2000): 5518--5541
- Camillo Cammarota and Enrico Rogora, "Spectral and symbolic
analysis of heart rate data during the tilt
test", Physical
Review E 74 (2006):
- Julien Cervelle, Enrico Formenti, Pierre Guillon, "Sofic Trace of a
Cellular
Automaton", math.DS/0703241
[When can the sequence of states at a particular site in a
1D cellular automaton give us a sofic
shift, in the sense?]
- J.-R. Chazottes, Z. Coelho, P. Collet
- "Poisson processes for subsystems of finite type in symbolic dynamics", arxiv:0804.2550
- "On the asymptotic measure of periodic subsystems of finite type in symbolic dynamics", arxiv:0804.2551
- J.-R. Chazottes, G. Keller, "Pressure and Equilibrium States in Ergodic Theory", arxiv:0804.2562
- J.-R. Chazottes, L. Ramirez and E. Ugalde, "Finite type
approximations of Gibbs measures on sofic
subshifts", Nonlinearity 18
(2005): 445--463
[PDF
reprint via Dr. Ugalde]
- Jean-Rene Chazottes, Edgardo Ugalde
- "Projection of Markov Measures May be Gibbsian",
Journal of Statistical Physics 111 (2003): 1245--1272
- "On the preservation of Gibbsianness under symbol amalgamation", arxiv:0907.0528
- Alex Clark and Lorenzo Sadun, "When size matters: subshifts and
their related tiling spaces," math.DS/0201152
- Ethan M. Coven and Zbigniew H. Nitecki, "On the genesis of symbolic
dynamics as we know
it", math.DS/0611322
- Jean-Charles Delvenne, Petr Kurka and Vincent Blondel,
"Computational Universality in Symbolic Dynamical Systems", cs.CC/0404021
- Tomasz Downarowicz
- J. M. Finn, J. D. Goettee, Z. Toroczkai, M. Anghel and B. P. Wood,
"Estimation of entropies and dimensions by nonlinear symbolic time series
analysis", Chaos 13
(2003): 444--456
- Najah F. Ghalyan, David J. Miller and Asok Ray, "A Locally Optimal Algorithm for Estimating a Generating Partition from an Observed Time Series and Its Application to Anomaly Detection", Neural Computation 30 (2018): 2500--2529
- Bai-lin Hao
- Applied Symbolic Dynamics
- "Applied Symbolic Dynamics," chao-dyn/9806025 [Presumably a
resume of the book]
- Yoshito Hirata and Kevin Judd, "Constructing dynamical systems with
specified symbolic
dynamics", Chaos
15 (2005): 033102
- Detlef Holstein and Holger Kantz, "Optimal Markov approximations and generalized embeddings", Physical Review E 79 (2009): 056202
- Steven Huntsman, "Effective statistical physics of Anosov systems",
arxiv:1009.2127
- Sarika Jalan, Fatihcan M. Atay and Jürgen Jost, "Detection of
synchronised chaos in coupled map networks using symbolic
dynamics", nlin.CD/0510057
- Anders Johansson, Anders Oberg, and Mark
Pollicott, "Countable state shifts and uniqueness of g-measures",
math.DS/0509109
- Svetlana Katok and Ilie Ugarovici, "Symbolic Dynamics for the Modular
Surface and Beyond", Bulletion of the American Mathematical Scoeity
44 (n.s., 2007): 87--132
[PDF]
- Ljupco Kocarev and David M. Walker, "Compactness of Symbolic
Sequences from Chaotic Systems," Physics Letters
A 274 (2000): 200--205
- Wolfgang Krieger, "On g-functions for subshifts",
pp. 306--316 in Dee Denteneer, Frank den Hollander, Evgeny Verbitskiy, eds., Dynamics and Stochastics: Festschrift in honor of M. S. Keane
- Christophe Letellier, "Estimating the Shannon Entropy: Recurrence
Plots versus Symbolic Dynamics", Physical Review
Letters 96 (2006): 254102
- Kevin McGoff, "Random subshifts of finite type", arxiv:1006.1325
- Diana A. Mendes, Vivaldo M. Mendes, J. Sousa Ramos, "Symbolic
Dynamics in a Matching Labour Market
Model",nlin.CD/0608002
- George Osipenko, Lectures on Symbolic Analysis of Dynamical
Systems [Online
PDF]
- Shou-Li Peng and Ke-Fei Cao, Star Products in One-Dimensional
Symbolic Dynamics
- Simone Pigolotti, Sandeep Krishna, Mogens H. Jensen, "Symbolic dynamics of biological feedback networks", Physical Review Letters
102 (2009): 088701, arxiv:0806.0276
- Marcus Pivato, "Cellular Automata vs. Quasistrumian
Shifts", Ergodic Theory and Dynamical
Systems forthcoming (2005) = math.DS/0503502
- David Richeson, Jim Wiseman, "Symbolic dynamics for nonhyperbolic systems", arxiv:0909.0882
- E. Arthur Robinson and Ayse A. Sahin, "On the Existence of Markov
Partitions for \( \mathbb{Z}^d \) Actions", Journal of the
London Mathematical Society 69 (2004): 693--706
- Ben-Zion Rubshtein, "On a class of one-sided Markov shifts",
math.DS/0406059
- Peter I. Saparin, Wolfgang Gowin, Jürgen Kurths, and Dieter
Felsenber, "Quantification of cancellous bone structure using symbolic dynamics
and measures of complexity", Physical Review E 58
(1998): 6449--6459 [Journal link]
- Hiroki Takahasi, "Level-2 Large Deviation Principle for Countable Markov Shifts Without Gibbs States", Journal of Statistical Physics 190 (2023): 120
- Hiroshi Teramoto and Tamiki Komatsuzaki, "How does a choice of Markov partition affect the resultant symbolic dynamics?", Chaos
20 (2010): 037113 [PDF reprint]
- Roy Wilds and Leon Glass, "Contrasting methods for symbolic
analysis of biological regulatory networks", Physical Review E 80 (2009): 062902
- H.-M. Xie, Grammatical Complexity and One-Dimensional
Dynamical Systems
- Jisang Yoo, "On Factor Maps that Send Markov Measures to Gibbs
Measures", Journal of Statistical Physics
(2010): 1055--1070
- Liqiang Zhu, Ying-Cheng Lai, Frank C. Hoppensteadt and Erik M.
Bollt, "Numerical and experimental investigation of the effect of filtering on
chaotic symbolic dynamics", Chaos 13
(2003): 410--419
Previous versions: 2005年11月13日 14:07