License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6305
URL: http://drops.dagstuhl.de/opus/volltexte/2006/630/
Go to the corresponding Portal


V'Yugin, Vladimir

On impossibility of sequential algorithmic forecasting

pdf-format:
Document 1.pdf (206 KB)


Abstract

The problem of prediction future event given an individual sequence of past events is considered. Predictions are given in form of real numbers $p_n$ which are computed by some algorithm $varphi$ using initial fragments $omega_1,dots, omega_{n-1}$ of an individual binary sequence $omega=omega_1,omega_2,dots$ and can be interpreted as probabilities of the event $omega_n=1$ given this fragment. According to Dawid's {it prequential framework} %we do not consider %numbers $p_n$ as conditional probabilities generating by some %overall probability distribution on the set of all possible events. we consider partial forecasting algorithms $varphi$ which are defined on all initial fragments of $omega$ and can be undefined outside the given sequence of outcomes. We show that even for this large class of forecasting algorithms combining outcomes of coin-tossing and transducer algorithm it is possible to efficiently generate with probability close to one sequences for which any partial forecasting algorithm is failed by the method of verifying called {it calibration}.

BibTeX - Entry

@InProceedings{vyugin:DSP:2006:630,
  author =	{Vladimir V'Yugin},
  title =	{On impossibility of sequential algorithmic forecasting},
  booktitle =	{Kolmogorov Complexity and Applications},
  year =	{2006},
  editor =	{Marcus Hutter  and Wolfgang Merkle and Paul M.B. Vitanyi},
  number =	{06051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/630},
  annote =	{Keywords: Universal forecasting, computable calibration, Dawid's prequential framework, algorithmic randomness, defensive forecasting}
}

Keywords: Universal forecasting, computable calibration, Dawid's prequential framework, algorithmic randomness, defensive forecasting
Seminar: 06051 - Kolmogorov Complexity and Applications
Issue Date: 2006
Date of publication: 31.07.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI