Normality in non-integer bases and polynomial time randomness

It is known that if x∈[0,1] is polynomial time random then x is normal in any integer base greater than one. We show that if x is polynomial time random and β>1 is Pisot, then x is "normal in base β", in the sense that the sequence (<inf>x</inf>βn)n∈<inf>N</inf>...

Descripción completa

Detalles Bibliográficos
Autor principal:	Figueira, Santiago Daniel
Publicado:	2015
Materias:	Algorithmic randomness Deterministic finite automaton Martingale Normality Pisot number Polynomial time randomness Subshift Polynomial approximation Polynomials Deterministic finite automata Pisot numbers Polynomial-time Subshifts Random processes
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n7_p1059_Almarza http://hdl.handle.net/20.500.12110/paper_00220000_v81_n7_p1059_Almarza
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00220000_v81_n7_p1059_Almarza
record_format	dspace
spelling	paper:paper_00220000_v81_n7_p1059_Almarza2023-06-08T14:45:03Z Normality in non-integer bases and polynomial time randomness Figueira, Santiago Daniel Algorithmic randomness Deterministic finite automaton Martingale Normality Pisot number Polynomial time randomness Subshift Polynomial approximation Polynomials Algorithmic randomness Deterministic finite automata Martingale Normality Pisot numbers Polynomial-time Subshifts Random processes It is known that if x∈[0,1] is polynomial time random then x is normal in any integer base greater than one. We show that if x is polynomial time random and β>1 is Pisot, then x is "normal in base β", in the sense that the sequence (<inf>x</inf>βn)n∈<inf>N</inf> is uniformly distributed modulo one. We work with the notion of P-martingale, a generalization of martingales to non-uniform distributions, and show that a sequence over a finite alphabet is distributed according to an irreducible, invariant Markov measure P if an only if no P-martingale whose betting factors are computed by a deterministic finite automaton succeeds on it. This is a generalization of Schnorr and Stimm's characterization of normal sequences in integer bases. Our results use tools and techniques from symbolic dynamics, together with automata theory and algorithmic randomness. © 2015 Elsevier Inc. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n7_p1059_Almarza http://hdl.handle.net/20.500.12110/paper_00220000_v81_n7_p1059_Almarza
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 randomness Deterministic finite automaton Martingale Normality Pisot number Polynomial time randomness Subshift Polynomial approximation Polynomials Algorithmic randomness Deterministic finite automata Martingale Normality Pisot numbers Polynomial-time Subshifts Random processes
spellingShingle	Algorithmic randomness Deterministic finite automaton Martingale Normality Pisot number Polynomial time randomness Subshift Polynomial approximation Polynomials Algorithmic randomness Deterministic finite automata Martingale Normality Pisot numbers Polynomial-time Subshifts Random processes Figueira, Santiago Daniel Normality in non-integer bases and polynomial time randomness
topic_facet	Algorithmic randomness Deterministic finite automaton Martingale Normality Pisot number Polynomial time randomness Subshift Polynomial approximation Polynomials Algorithmic randomness Deterministic finite automata Martingale Normality Pisot numbers Polynomial-time Subshifts Random processes
description	It is known that if x∈[0,1] is polynomial time random then x is normal in any integer base greater than one. We show that if x is polynomial time random and β>1 is Pisot, then x is "normal in base β", in the sense that the sequence (<inf>x</inf>βn)n∈<inf>N</inf> is uniformly distributed modulo one. We work with the notion of P-martingale, a generalization of martingales to non-uniform distributions, and show that a sequence over a finite alphabet is distributed according to an irreducible, invariant Markov measure P if an only if no P-martingale whose betting factors are computed by a deterministic finite automaton succeeds on it. This is a generalization of Schnorr and Stimm's characterization of normal sequences in integer bases. Our results use tools and techniques from symbolic dynamics, together with automata theory and algorithmic randomness. © 2015 Elsevier Inc.
author	Figueira, Santiago Daniel
author_facet	Figueira, Santiago Daniel
author_sort	Figueira, Santiago Daniel
title	Normality in non-integer bases and polynomial time randomness
title_short	Normality in non-integer bases and polynomial time randomness
title_full	Normality in non-integer bases and polynomial time randomness
title_fullStr	Normality in non-integer bases and polynomial time randomness
title_full_unstemmed	Normality in non-integer bases and polynomial time randomness
title_sort	normality in non-integer bases and polynomial time randomness
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n7_p1059_Almarza http://hdl.handle.net/20.500.12110/paper_00220000_v81_n7_p1059_Almarza
work_keys_str_mv	AT figueirasantiagodaniel normalityinnonintegerbasesandpolynomialtimerandomness
_version_	1768545450933092352

Normality in non-integer bases and polynomial time randomness

Ejemplares similares