Open Collections

Normality in non-integer bases and polynomial time randomness

Banff International Research Station for Mathematical Innovation and Discovery

It is known that if $x\in[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 \beta>1 is Pisot, then x is "normal in base beta", in the sense that the sequence $(x \beta^n)_{n \in 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. (Joint with Javier Almarza)

Mathematics; Mathematical logic and foundations; Dynamical systems and ergodic theory; Logic and foundations

video/mp4

Author affiliation: Universidad de Buenos Aires

2017-06-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61889

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/