title: Antipredictable sequences: harder to predict than random sequences.
abstract: For any discrete-state sequence prediction algorithm A, it is always possible, using an algorithm B no more complicated than A, to generate a sequence for which A's prediction is always wrong. For any prediction algorithm A and sequence x, there exists a sequence y no more complicated than x, such that if A performs better than random on x, then it will perform worse than random on y by the same margin. An example of a simple neural network predicting a bit sequence is used to illustrate this very general but not widely recognized phenomenon. This implies that any predictor with good performance must rely on some (usually implicitly) assumed prior distributions of the problem.
authors.affiliation: The Santa Fe Institute,1399 Hyde Park Road, Santa Fe, MN 87501, USA. zhuh@santafe.edu
authors.forename: H
authors.initials: H
authors.lastname: Zhu
authors.forename: W
authors.initials: W
authors.lastname: Kinzel
mesh_terms: D000465:Algorithms; D007858:Learning; D008959:Models, Neurological; D008960:Models, Psychological; D016571:Neural Networks, Computer; D011897:Random Allocation; D015203:Reproducibility of Results