On complexity and randomness of Markov-chain prediction

Let {X_t : t ∈ ℤ} be a sequence of binary random variables generated by a stationary Markov source of order k*. Let β be the probability of the event “X_t = 1”. Consider a learner based on a Markov model of order k, where k may be different from k*, who trains on a sample sequence X^(m) which is randomly drawn by the source. Test the learner´s performance by asking it to predict the bits of a test sequence X⁽ⁿ⁾ (generated by the source). An error occurs at time t if the prediction Y_t differs from the true bit value X_t, 1 ≤ t ≤ n. Denote by Ξ⁽ⁿ⁾ the sequence of errors where the error bit Ξ_t at time t equals 1 or 0 according to whether an error occurred or not, respectively. Consider the subsequence Ξ^(ν) of Ξ⁽ⁿ⁾ which corresponds to the errors made when predicting a 0, that is, Ξ^(ν) consists of those bits Ξ_t at times t where Y_t = 0: In this paper we compute an upper bound on the absolute deviation between the frequency of 1 in Ξ^(ν) and β. The bound has an explicit dependence on k, k*, m, ν, n. It shows that the larger k, or the larger the difference k - k*, the less random that Ξ^(ν) can become.