Normality in non-integer bases and polynomial time randomness

JAVIER ALMARZA; SANTIAGO FIGUEIRA

JOURNAL OF COMPUTER AND SYSTEM SCIENCES

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2015 vol. 81 p. 1059 - 1087

0022-0000

It is known that if $xin[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 $eta>1$ is Pisot, then $x$ is ``normal in base $eta$´´, in the sense that the sequence $(xeta^n)_{ninNN}$ is uniformly distributed modulo one. We work with the notion of {em $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.