Prediction and dimension

DOI10.1016/J.JCSS.2004.10.007MaRDI QIDQ1780452zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz, Lance Fortnow

Publication date 13 June 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.10.007

zbMATH Keywords

PredictionShannon entropyHausdorff dimensionComputational complexityInformation theoryFeasible dimensionSelf-information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Measures of information, entropy (94A17)

Recommendations

• scientific article; zbMATH DE number 2089375
• Fractal dimension and logarithmic loss unpredictability.
• The complexity and effectiveness of prediction algorithms
• Effective Dimensions and Relative Frequencies
• On complexity of easy predictable sequences

Cites work

• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 4119313 (Why is no real title available?)
• scientific article; zbMATH DE number 3205709 (Why is no real title available?)
• A New Interpretation of the von Mises' Concept of Random Sequence
• A game of prediction with expert advice
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A unified approach to the definition of random sequences
• Algorithmic approach to the prediction problem
• Dimension in Complexity Classes
• Finite-state dimension
• Fractal dimension and logarithmic loss unpredictability.
• How to use expert advice
• Kolmogorov complexity and Hausdorff dimension
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On prediction of individual sequences
• Prediction and Entropy of Printed English
• The complexity and effectiveness of prediction algorithms
• The definition of random sequences
• The dimensions of individual strings and sequences
• Universal prediction
• Universal prediction of individual sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(9)

• Identification and Prediction
• Predictive sets
• Pushdown dimension
• Generic density and small span theorem
• Generalised entropies and asymptotic complexities of languages
• Universal coding and prediction on ergodic random points
• Dimension, entropy rates, and compression
• scientific article; zbMATH DE number 2089375 (Why is no real title available?)
• Martingale families and dimension in P

This page was built for publication: Prediction and dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1780452)