On complexity and randomness of Markov-chain prediction

Let {X-t : t is an element of Z} be a sequence of binary random variables generated by a stationary Markov source of order k*. Let beta 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-(n) (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 Xi((n)) the sequence of errors where the error bit Xi(t) at time t equals 1 or 0 according to whether an error occurred or not, respectively. Consider the subsequence Xi((nu)) of Xi((n)) which corresponds to the errors made when predicting a 0, that is, Xi((nu)) consists of those bits Xi(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 Xi((nu)) and beta. The bound has an explicit dependence on k, k*, m, nu, n. It shows that the larger k, or the larger the difference k-k*, the less random that Xi((nu)) can become.