Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429973 | Journal of Computer and System Sciences | 2015 | 29 Pages |
•Relationship between polynomial time randomness and normality in Pisot bases.•Generalization of martingales to non-uniform distributions.•Invariant Markov measures and martingales computed by a DFA.
It is known that if x∈[0,1]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β>1 is Pisot, then x is “normal in base β ”, in the sense that the sequence (xβn)n∈N(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.