论文标题
对厄贡马丁 - 兰夫随机点的通用编码和预测
Universal Coding and Prediction on Ergodic Martin-Löf Random Points
论文作者
论文摘要
假设我们有一种方法来估计某些未知随机来源的条件概率，并且我们使用它来猜测将发生哪些结果。我们希望尽可能多地做出正确的猜测。哪些估计器对此有益？在这项工作中，我们考虑了在算法随机性的框架中，即我们对Martin-Löf随机点的预测特别感兴趣的估计量熟悉的通用编码为固定的千古措施的概念。我们概述了一般理论，并展示了一些反例。从2009年开始完成Ryabko的结果，我们还表明，普遍编码意义上的普遍概率度量在术前的意义上会导致通用预测指标。令人惊讶的是，如果通用度量不会将条件概率太低地归因于单个符号，则这种含义是正确的。例如，我们表明，通过部分匹配（PPM）测量的预测可以满足大量储备的要求。
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e, we are particularly interested in prediction of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.
