|
Martina Pfeifer

A. Nies: Randomness via algorithmic versions of concepts from probability theory

Monday, 02.06.2014 10:15 im Raum SR 1D

Mathematik und Informatik

How would one formalise the intuitive notion that an infinite sequence of bits is random? Surprisingly, effective (i.e. algorithmic) versions of concepts from probability help. For instance, various effective forms of martingales can be used as tests defining algorithmic randomness notions for bit sequences. In this way, new aspects of well-established arguments appear, such as Doob's upcrossing inequality. So far the martingales used have been a very restricted form of the concept from probability: they assign a non-negative real to a binary string. We will consider some other types of martingales. For instance, effective backwards martingales promise to be helpful in algorithmic aspects of the pointswise ergodic theorem. Book references: A. Nies, Computability and Randomness, OUP, 2008 Downey and Hirschfeldt, Algorithmic randomness and complexity, Springer 2009



Angelegt am Tuesday, 20.05.2014 09:49 von Martina Pfeifer
Geändert am Tuesday, 20.05.2014 09:49 von Martina Pfeifer
[Edit | Vorlage]

Oberseminare und sonstige Vorträge
Sonstige Vorträge