Testing the order of discrete Markov chains using surrogate data

Tests of the null-hypothesis that a symbolic sequence is of nth Markov order are described. These tests are based on resampling methods similar to the method of surrogate data used to test continuous time series for nonlinear structure. The size and power of these symbolic surrogate tests are estimated using binary and heptary test-sequences of known order. Conditioning on a sufficient statistic under the null-hypothesis yields an estimated true size which closely approximates the nominal size and increases the power of the test with respect to the unconditional test. We apply one method to a symbolic sequence derived from the Rossler system and to a binary and heptary representation of an interspike interval sequence of an electroreceptor of the weakly electric eel Apteronotus Leptorhynchus.