Notebooks

Symbolic Dynamics

13 Nov 2005 14:07

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

permanent link for this note   RSS feed for this note

Notebooks:     Hosted, but not endorsed, by the Center for the Study of Complex Systems