Applications of effective probability theory to martin-löf randomness

Mathieu Hoyrup, Cristóbal Rojas

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

18 Citas (Scopus)

Resumen

We pursue the study of the framework of layerwise computability introduced in a preceding paper and give three applications. (i) We prove a general version of Birkhoff's ergodic theorem for random points, where the transformation and the observable are supposed to be effectively measurable instead of computable. This result significantly improves V'yugin and Nandakumar's ones. (ii) We provide a general framework for deriving sharper theorems for random points, sensitive to the speed of convergence. This offers a systematic approach to obtain results in the spirit of Davie's ones. (iii) Proving an effective version of Prokhorov theorem, we positively answer a question recently raised by Fouché: can random Brownian paths reach any random number? All this shows that layerwise computability is a powerful framework to study Martin-Löf randomness, with a wide range of applications.

Idioma originalInglés
Título de la publicación alojadaAutomata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
Páginas549-561
Número de páginas13
EdiciónPART 1
DOI
EstadoPublicada - 2009
Evento36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Grecia
Duración: 5 jul 200912 jul 2009

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NúmeroPART 1
Volumen5555 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Otros

Otros36th International Colloquium on Automata, Languages and Programming, ICALP 2009
País/TerritorioGrecia
CiudadRhodes
Período5/07/0912/07/09

Áreas temáticas de ASJC Scopus

  • Ciencia computacional teórica
  • Informática (todo)

Huella

Profundice en los temas de investigación de 'Applications of effective probability theory to martin-löf randomness'. En conjunto forman una huella única.

Citar esto