The Existence of Predictive Complexity and the Legendre Transformation.
 
Yuri Kalnishkan and Volodya Vovk
 
Abstract
 
Predictive complexity is a generalisation of Kolmogorov complexity. In
this paper we point out some properties of predictive complexity connected
with the Legendre (--Young--Fenchel) transformation.  Our main result is
that mixability is necessary for the existence of conditional predictive
complexity (it is known to be sufficient in under very mild assumptions).
 
We formulate a differential criterion of mixability and show that it
reduces to a very simple form if we employ the Legendre transformation.
The Legendre transformation also turns out to have a probabilistic meaning
which allows us to prove that a variant of predictive complexity specifies
a unique (up to a parametrisation) mixable game.