How Random is a Coin Toss? Bayesian Inference and the Symbolic Dynamics of Deterministic Chaos

Christopher C. Strelioff and James P. Crutchfield

06-11-042

Symbolic dynamics has proven to be an invaluable tool in analyzing the mechanisms that lead to unpredictability and random behavior in nonlinear dynamical systems. Surprisingly, a discrete partition of continuous state space can produce a coarse-grained description of the behavior that accurately describes the invariant properties of an underlying chaotic attractor. In particular, measures of the rate of information production---the topological and metric entropy rates---can be estimated from the outputs of Markov or generating partitions. Here we develop Bayesian inference for $k$-th order Markov chains as a method to finding generating partitions and estimating entropy rates from finite samples of discretized data produced by coarse-grained dynamical systems.