Algorithmic identification of probabilities is hard

Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p, we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume t...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2018
Materias:	Algorithmic learning theory Algorithmic randomness Computer networks Systems science Algorithmic identification Algorithmic learning theories Bernoulli Computable reals Inductive inference Probability measures Strong law of large numbers Binary sequences
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v95_n_p98_Bienvenu http://hdl.handle.net/20.500.12110/paper_00220000_v95_n_p98_Bienvenu
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00220000_v95_n_p98_Bienvenu
record_format	dspace
spelling	paper:paper_00220000_v95_n_p98_Bienvenu2025-07-30T17:27:20Z Algorithmic identification of probabilities is hard Algorithmic learning theory Algorithmic randomness Computer networks Systems science Algorithmic identification Algorithmic learning theories Algorithmic randomness Bernoulli Computable reals Inductive inference Probability measures Strong law of large numbers Binary sequences Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p, we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p. We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. © 2018 Elsevier Inc. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v95_n_p98_Bienvenu http://hdl.handle.net/20.500.12110/paper_00220000_v95_n_p98_Bienvenu
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Algorithmic learning theory Algorithmic randomness Computer networks Systems science Algorithmic identification Algorithmic learning theories Algorithmic randomness Bernoulli Computable reals Inductive inference Probability measures Strong law of large numbers Binary sequences
spellingShingle	Algorithmic learning theory Algorithmic randomness Computer networks Systems science Algorithmic identification Algorithmic learning theories Algorithmic randomness Bernoulli Computable reals Inductive inference Probability measures Strong law of large numbers Binary sequences Algorithmic identification of probabilities is hard
topic_facet	Algorithmic learning theory Algorithmic randomness Computer networks Systems science Algorithmic identification Algorithmic learning theories Algorithmic randomness Bernoulli Computable reals Inductive inference Probability measures Strong law of large numbers Binary sequences
description	Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p, we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p. We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. © 2018 Elsevier Inc.
title	Algorithmic identification of probabilities is hard
title_short	Algorithmic identification of probabilities is hard
title_full	Algorithmic identification of probabilities is hard
title_fullStr	Algorithmic identification of probabilities is hard
title_full_unstemmed	Algorithmic identification of probabilities is hard
title_sort	algorithmic identification of probabilities is hard
publishDate	2018
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v95_n_p98_Bienvenu http://hdl.handle.net/20.500.12110/paper_00220000_v95_n_p98_Bienvenu
_version_	1840321883373830144

Algorithmic identification of probabilities is hard

Ejemplares similares