2014/10/31 by Javier Almarza, Santiago Figueira, Almarza, Javier +1
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.DS
paper · pdf · doi:10.48550/arxiv.1410.8594
arxiv created 2014/10/31 · arxiv updated 2014/11/03
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∈ℕ 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.