  We present two new methods for estimating the order (memory depth) of a
finite alphabet Markov chain from observation of a sample path. One method is
based on entropy estimation via recurrence times of patterns, and the other
relies on a comparison of empirical conditional probabilities. The key to both
methods is a qualitative change that occurs when a parameter (a candidate for
the order) passes the true order. We also present extensions to order
estimation for Markov random fields.
