  We present a theoretical analysis of Maximum a Posteriori (MAP) sequence
estimation for binary symmetric hidden Markov processes. We reduce the MAP
estimation to the energy minimization of an appropriately defined Ising spin
model, and focus on the performance of MAP as characterized by its accuracy and
the number of solutions corresponding to a typical observed sequence. It is
shown that for a finite range of sufficiently low noise levels, the solution is
uniquely related to the observed sequence, while the accuracy degrades linearly
with increasing the noise strength. For intermediate noise values, the accuracy
is nearly noise-independent, but now there are exponentially many solutions to
the estimation problem, which is reflected in non-zero ground-state entropy for
the Ising model. Finally, for even larger noise intensities, the number of
solutions reduces again, but the accuracy is poor. It is shown that these
regimes are different thermodynamic phases of the Ising model that are related
to each other via first-order phase transitions.
