  We introduce the Conditional Mutual Information (CMI) for the estimation of
the Markov chain order. For a Markov chain of $K$ symbols, we define CMI of
order $m$, $I_c(m)$, as the mutual information of two variables in the chain
being $m$ time steps apart, conditioning on the intermediate variables of the
chain. We find approximate analytic significance limits based on the estimation
bias of CMI and develop a randomization significance test of $I_c(m)$, where
the randomized symbol sequences are formed by random permutation of the
components of the original symbol sequence. The significance test is applied
for increasing $m$ and the Markov chain order is estimated by the last order
for which the null hypothesis is rejected. We present the appropriateness of
CMI-testing on Monte Carlo simulations and compare it to the Akaike and
Bayesian information criteria, the maximal fluctuation method (Peres-Shields
estimator) and a likelihood ratio test for increasing orders using
$\phi$-divergence. The order criterion of CMI-testing turns out to be superior
for orders larger than one, but its effectiveness for large orders depends on
data availability. In view of the results from the simulations, we interpret
the estimated orders by the CMI-testing and the other criteria on genes and
intergenic regions of DNA chains.
