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.