Comparing Exact Bayesian and BIC Markov Order Classifiers

We use an exact Bayesian calculation to design classifiers that distinguish whether a finite sequence drawn from a finite alphabet is a sample path of a Markov chain of order k = 0 or of order k> 0. Three exact Bayes (EB) classifiers are derived, each corresponding to a different choice of prior. We also include a classifier based on the Bayesian Information Criterion (BIC), a popular technique for Markov order estimation. Using thousands of random Markov chains of known order, we test the performance of the classifiers. In both average accuracy and ROC analyses, we find that EB classifiers with informative priors perform better than the BIC classifier, with the difference becoming strikingly large when either the size of the alphabet is large or the length of the sequence is small. We also test the classifiers on five real-world data sets and find that the EB classifications, unlike the BIC classifications, match the orders of the models with highest out-of-sample predictive accuracies