John Tromp

Algorithmic Statistics

abstract:

We present some results concerning `Algorithmic Statistics' for a binary string x, which are simple finite sets of which x is a `typical' element.
Such sets can be seen as separating the structure of a string from its randomness.
Specifically, we study the relation between the size of such sets, their complexity, and the complexity of x within (given) the set.