Randomness with Respect to the Signed-Digit Representation

Article type: Research Article

Authors: Archibald, Margaret | Brattka, Vasco | Heuberger, Clemens

Affiliations: Laboratory of Foundational Aspects of Computer Science, Department of Mathematics & Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa. E-mails: [email protected]; [email protected] | Institut für Optimierung und Diskrete Mathematik Technische Universität Graz, 8010 Graz, Austria. E-mail: [email protected]

Abstract: The ordinary notion of algorithmic randomness of reals can be characterised as Martin-Löf randomness with respect to the Lebesgue measure or as Kolmogorov randomness with respect to the binary representation. In this paper we study the question of how the notion of algorithmic randomness induced by the signed-digit representation of the real numbers is related to the ordinary notion of algorithmic randomness. We first consider the image measure on real numbers induced by the signed-digit representation. We call this measure the signed-digit measure and using the Fourier transform of this measure and the Riemann-Lebesgue Lemma we prove that this measure is not absolutely continuous with respect to the Lebesgue measure. We also show that the signed-digit measure can be obtained as a weakly convergent convolution of discrete measures and therefore, by the classical Theorem of Jessen and Wintner the Lebesgue measure is not absolutely continuous with respect to the signed-digitmeasure. Finally, we provide an invariance theoremwhich shows that if a computable map preserves Martin-Löf randomness, then its induced image measure has to be absolutely continuous with respect to the target space measure. This theorem can be considered as a loose analog for randomness of the Banach-Mazur theorem for computability. Using this Invariance Theorem we conclude that the notion of randomness induced by the signed-digit representation is incomparable with the ordinary notion of randomness.

Keywords: Algorithmic randomness, computable analysis, signed-digit representation, Stern-Brocot tree, Farey fractions, Stern's diatomic sequence

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 1-19, 2008