On the randomness in learning

Given a random binary sequence X⁽ⁿ⁾ of random variables, X_t, t = 1, 2, ..., n, for instance, one that is generated by a Markov source (teacher) of order k^* (each state represented by k^* bits). Assume that the probability of the event X_t = 1 is constant and denote it by ß. Consider a learner which is based on a parametric model, for instance a Markov model of order k, who trains on a sequence x^(m) which is randomly drawn by the teacher. Test the learner´s performance by giving it a sequence x⁽ⁿ⁾ (generated by the teacher) and check its predictions on every bit of x⁽ⁿ⁾. An error occurs at time t if the learner´s prediction Y_t differs from the true bit value X_t. Denote by ¿⁽ⁿ⁾ the sequence of errors where the error bit ¿_t at time t equals 1 or 0 according to whether the event of an error occurs or not, respectively. Consider the subsequence ¿^(¿) of ¿⁽ⁿ⁾ which corresponds to the errors of predicting a 0, i.e., ¿^(¿) consists of the bits of ¿⁽ⁿ⁾ only at times t such that Y_t = 0. In this paper we compute an estimate on the deviation of the frequency of 1s of ¿^(¿) from ß. The result shows that the level of randomness of ¿^(¿) decreases relative to an increase in the complexity of the learner.