Artículo
Normality in non-integer bases and polynomial time randomness
Fecha de publicación:
04/2015
Editorial:
Academic Press Inc Elsevier Science
Revista:
Journal of Computer and System Sciences
ISSN:
0022-0000
e-ISSN:
1090-2724
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
It is known that if x ∈ [0, 1] is polynomial time random (i.e. no polynomial time computable martingale succeeds on the binary fractional expansion of x) 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 (xβn)n∈N 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.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Almarza, Javier Ignacio; Figueira, Santiago; Normality in non-integer bases and polynomial time randomness; Academic Press Inc Elsevier Science; Journal of Computer and System Sciences; 81; 7; 4-2015; 1059-1087
Compartir
Altmétricas