Complexity of Forecasting in a Class of Simple Models
Domenico Zambella
C.N.R. Istituto per lo Studio della Dinamica,
delle Grande Masse, 1364 S. Polo, I-30125 Venezia, Italy
Peter Grassberger
Physics Department, University of Wuppertal,
D-56 Wuppertal, Gauss-Str. 20, West Germany
Abstract
We deal in this paper with the difficulty of performing optimal or nearly optimal forecasts of discrete symbol sequences generated by very simple models. These are spatial sequences generated by elementary one-dimensional cellular automata after one time step, with completely random input strings. They have positive entropy and thus cannot be predicted. Making forecasts which are optimal within this limitation is proven to be surprisingly difficult. Scaling laws with new anomalous exponents are found both for optimal forecasts and for forecasts which are nearly optimal.
The same remarks hold not only for forecasting but also for data compression.
