The chain rule writes the likelihood of a sequence as a product of conditionals \(p(x_t\mid x_{1:t-1})\). Restricting each conditional to the last \(k\) symbols gives the order-\(k\) Markov model, fitted here by counting. The sequence is \(x_t=x_{t-2}\oplus x_{t-5}\oplus\) noise, so a model needs five symbols of context; the best possible score is the noise entropy \(h_2(\varepsilon)\) (green line). Blue: bits per symbol on the training sequence; red: on a fresh test sequence. The golden marker is the order you select.
Orders 0 to 4 cannot see the symbol \(x_{t-5}\), so the conditional given the last \(k\le4\) symbols is a fair coin: one bit per symbol. At \(k=5\) the dependence is captured and the score drops to the noise entropy. Beyond it the number of contexts, \(2^k\), grows while the number of observations per context shrinks: the training score keeps improving but the test score worsens; moderate smoothing limits the damage but cannot remove it, and no smoothing at all is worst. The estimate of each conditional is \((n_{c,v}+\alpha)/(n_c+2\alpha)\).
code/ch22_autoregressive_models.py (xor_source, markov_bits, Figure x22.a).