BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Normality in non-integer bases and polynomial time randomness Figueira, Santiago


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)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International