## Symbolic Dynamics

*27 Apr 2012 11:51*

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.

Cf. Computation, Automata and Formal Languages; Computational Mechanics; Dynamics in Cognitive Science; Ergodic Theory; Information Theory; Nonlinear Dynamics; Time Series

- Recommended:
- 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.] - 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]
- 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 - R. L. Devaney, A First Course in Chaotic Dynamical Systems
- 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 - 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

- 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

- "Projection of Markov Measures May be Gibbsian",
Journal of Statistical Physics
- 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
- Entropy in Dynamical Systems
- "Symbolic extensions of smooth interval maps",
Probability Surveys
**7**(2010): 84--104

- 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 - 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 [explains "how to construct signals (time series) of continuous-time dynamical systems that exhibit a given symbolic dynamics. This is achieved without construction of the ordinary differential equations that generate the flow. This construction is of theoretical interest and is useful as a source of dynamical data that can be used to test various data analysis algorithms."] - 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] - 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