Paper: Less predictable than random ...

[Huaiyu Zhu]

The following paper has been submitted to Neural Computation:

ftp://ftp.santafe.edu/pub/zhuh/anti.ps


Anti-Predictable Sequences: Harder to Predict Than A Random Sequence

		Huaiyu Zhu <zhuh at santafe.edu>
 Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM 87501, USA

	  Wolfgang Kinzel <kinzel at physik.uni-wuerzburg.de>
 Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM 87501, USA
		Institut f\"ur Theoretische Physik,
	  Universit\"at, D-97074 W\"urzburg, Germany 


			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
  phenomena.
  
  This implies that any predictor with good performance must rely on
  some (usually implicitly) assumed prior distributions of the
  problem.


-- 
Huaiyu Zhu                      Tel: 1 505 984 8800 ext 305       
Santa Fe Institute              Fax: 1 505 983 0751 
1399 Hyde Park Road             mailto:zhuh at santafe.edu          
Santa Fe, NM 87501              http://www.santafe.edu/~zhuh/  
USA                             ftp://ftp.santafe.edu/pub/zhuh/