EPSRC Reference: 
GR/M14937/01 
Title: 
PREDICTIVE COMPLEXITY: RECURSIONTHEORETIC VARIANTS 
Principal Investigator: 
Vovk, Professor V 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
Royal Holloway, Univ of London 
Scheme: 
Standard Research (PreFEC) 
Starts: 
01 October 1998 
Ends: 
30 September 2001 
Value (£): 
50,922

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Kolmogorov complexity of a sequence can be defined as the length of the shortest 'programme' describing this sequence. Another possible interpretation (going back to Solomonoff) of this notion is that Kolmogorov complexity is the loss suffered by the 'universal prediction strategy' when predicting online the elements of the sequence under the logarithmic loss function. The most natural tool in defining the later version of Kolmogorov complexity is the Bayesian merging scheme. The Bayesian merging scheme has been generalised by the proposer to the 'Aggregating Algorithm', which is applicable to a wide class of loss functions. (The Aggregating Algorithm becomes the Bayesian merging scheme when applied to the logloss function). With the Aggregating Algorithm, it becomes possible to generalise the notion of Kolmogorov complexity to a wide class of loss function, etc. In this project we plan to study this general notion, which we call predictive complexity. One of the most important applications of Kolmogorov complexity is to the definition of random sequences, and we expect that predictive complexity will generate other useful notions of randomness.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
