Universal sequence prediction can fail to converge on some computable patterns, but squared error stays bounded

Universal sequence prediction can accumulate unbounded per-bit error on computable patterns, changing what was expected of the errors on pattern-fixed bits. Earlier results showed that the error probabilities of bits fixed by a computable pattern have limit zero, for example the repeated-bit pattern has error tending to zero at even positions. For some computable pattern, the sum of the errors over the pattern's positions is not bounded, in contrast to the per-bit errors tending to zero.

Replacing per-bit error with its square restores a bound on the pattern positions, growing exponentially in the program length of the pattern. The sum of the per-bit errors has no bound, so the errors alone do not give an overall convergence rate on pattern positions. The sum of squared errors over the pattern positions is controlled by an exponential function of the pattern's program length.

When the predicted bits are fixed by a computable classification function, the bound on the squared-error sum tightens from exponential to polynomial. A general computable pattern yields only an exponential bound on the squared-error sum. For programs whose runtime is bounded by any fixed computable time bound, the squared-error sum is controlled by a polynomial in the program length.

The discussion covers conditional prediction probabilities from the universal semimeasure and bits fixed by a computable pattern or a computable classification function. The intended readers are researchers in algorithmic information theory and online learning. No next experiment or application is proposed.

The unbounded per-bit error sum holds only for some computable patterns, not all; the exponential and polynomial bounds on the squared-error sum apply to general computable patterns and to runtime-bounded computable classification functions respectively, so their scopes differ.