IEEE Transactions on Information Theory · 1989 · 133 citations · 20 references
EngineeringComputer ScienceMathematicsAlgorithmsProbability TheoryStochastic ProcessesData CompressionLossy Data CompressionMarkov ChainsMarkov ProcessesOrder StatisticsCompression AlgorithmsFinite Markov ChainsFinite-state Markov ChainsLempel-ziv CodingLempel-ziv CompressionUpper Bound Computation
The authors estimate the order of a finite Markov source based on empirically observed statistics. The performance criterion adopted is to minimize the probability of underestimating the model order while keeping the overestimation probability exponent at a prescribed level. A universal asymptotically optimal test, in the sense just defined, is proposed for the case where a given integer is known to be the upper bound of the true order. For the case where such a bound is unavailable, an alternative rule based on the Lempel-Ziv data compression algorithm is shown to be asymptotically optimal also and computationally more efficient.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
20