Normality in non-integer bases and polynomial time randomness

DOI10.1016/J.JCSS.2015.04.005MaRDI QIDQ2353390zbMATH OpenOpenAlexFDO

Authors Javier Ignacio Almarza, Santiago Figueira

Publication date 13 July 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.8594

zbMATH Keywords

algorithmic randomnessdeterministic finite automatonmartingalenormalityPisot numberpolynomial time randomnesssubshift

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Generalizations of martingales (60G48) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Abstract: 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 $$ is Pisot, then $x$ is "normal in base $$", in the sense that the sequence $$ 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.

Recommendations

• Feasible analysis, randomness, and base invariance
• Normal numbers and computer science
• Computable absolutely Pisot normal numbers
• Normal numbers and finite automata
• scientific article; zbMATH DE number 2012395

Cites work

• A decomposition theorem for numbers in which the summands have prescribed normality properties
• A Mathematical Theory of Communication
• A polynomial-time algorithm for computing absolutely normal numbers
• An Introduction to Symbolic Dynamics and Coding
• Computational complexity of real functions
• Développement en base \theta, répartition modulo un de la suite (x\theta \sp n), n\ge 0, langages codés et \theta-shift
• Endliche Automaten und Zufallsfolgen
• Endomorphisms of irreducible subshifts of finite type
• Feasible analysis, randomness, and base invariance
• scientific article; zbMATH DE number 3745547 (Why is no real title available?)
• Intrinsic Markov Chains
• Markov Chains
• On theβ-expansions of real numbers
• Randomness -- beyond Lebesgue measure
• Randomness and differentiability
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• The Hausdorff dimension of a set of normal numbers
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(4)

• Feasible analysis, randomness, and base invariance
• Computable absolutely Pisot normal numbers
• Discrepancy bounds for normal numbers generated by necklaces in arbitrary base
• On normality in shifts of finite type

This page was built for publication: Normality in non-integer bases and polynomial time randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353390)