James Crutchfield, Nicholas Travers

Paper #: 10-11-031

We analyze how an observer synchronizes to the internal state of a finite-state information source, using the ε-machine causal representation. Here, we treat the case of exact synchronization, when only a finite number of observations are required. The more difficult case of strictly asymptotic synchronization is treated in a sequel. In both cases, we find that an observer synchronizes to the source exponentially fast and, as a result, the accuracy in an observer's predictions of future source output approaches its optimal level exponentially fast as well. Additionally, we show here how to analytically calculate the synchronization rate for exact ε-machines and provide an efficient polynomial-time algorithm to test ε-machines for exactness.