Randomness with Respect to the Signed-Digit Representation

• Autorzy: Archibald M. , Brattka V. , Heuberger C.
• Języki publikacji: EN

Abstrakty

EN

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-digit measure. Finally, we provide an invariance theorem which 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.

Słowa kluczowe

EN

algorithmic randomness; computable analysis; signed-digit representation; Stern-Brocot tree; Farey fractions; Stern's diatomic sequence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 1--19
• Opis fizyczny: bibliogr. 28 poz., tab., wykr.

Twórcy

autor

Archibald M.

autor

Brattka V.

autor

Heuberger C.

• Department of mathematics &Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa,

Bibliografia

• [1] Avizienis, A.: Signed-Digit Number Representations for Fast Parallel Arithmetic, IRE Transactions on Electronic Computers, EC-10, September 1961, 389-400.
• [2] Banach, S., Mazur, S.: Sur les fonctions calculables, Ann. Soc. Pol. de Math., 16, 1937,223.
• [3] Bauer, H.: Probability Theory and Elements of Measure Theory, Holt, Rinehart and Winston, New York, 1972.
• [4] Brattka, V., McNicholl, T. H.: Algorithmic Randomness in Represented Spaces, unpublished manuscript.
• [5] Brattka, V., Presser, G.: Computability on subsets of metric spaces, Theoretical Computer Science, 305, 2003,43-76.
• [6] Calude, C: Information and Randomness, Monographs in Theoretical Computer Science, Springer, Berlin, 1994.
• [7] Calude, C, Jiirgensen, H.: Randomness as an invariant for number representations, Results and Trends in Theoretical Computer Science (H. Maurer, J. Karhumaki, G. Rozenberg, Eds.), Springer, Berlin, 1994.
• [8] Cohn, D. L.: Measure Theory, Birkhauser, Boston, 1980.
• [9] Dumont, J. M., Sidorov, N., Thomas, A.: Number of representations related to a linear recurrent basis, Acta Arithmetica, 88(4), 1999, 371-396.
• [10] Feng, D.-J., Olivier, E.: Multifractal analysis of weak Gibbs measures and phase transition-application to some Bernoulli convolutions, Ergodic Theory and Dynamical Systems, 23(6), 2003, 1751-1784.
• [11] Grabner, P. J., Heuberger, C: On the number of optimal base 2 representations, Designs, Codes and Cryptography, 40, 2006, 25-39.
• [12] Hertling, P.: A Banach-Mazur computable but not Markov computable function on the computable real numbers, Annals of Pure and Applied Logic, 132(2-3), 2005, 227-246.
• [13] Hertling, P.: A sequentially computable function that is not effectively continuous at any point, Journal of Complexity, 22(6), 2006, 752-767.
• [14] Hertling, P., Weihrauch, K.: Random elements in effective topological spaces with measure, Information and Computation, 181(1), 2003, 32-56.
• [15] Jessen, B., Wintner, A.: Distribution Functions and the Riemann Zeta Function, Trans. Amer. Math. Soc, 38, 1935,48-88.
• [16] Kolmogorov, A. N., Uspenskii, V.: Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1, 1965, 1-7.
• [17] Kolmogorov, A. N., Uspenskii, V.: Algorithms and randomness, SIAM J. Theory Probab. Appl, 32(3), 1987, 389-412.
• [18] Lagarias, J., Tresser, C.: A walk along the branches of the extended Farey tree, IBM Journal of Research and Development, 39(3), 1995, 283-294.
• [19] Lehmer, D.: On Stern's Diatomic Series, The American Mathematical Monthly,36(2), 1929,59-67.
• [20] Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, Graduate Texts in Computer Science, 2nd edition, Springer, New York, 1997.
• [21] Martin-Lof, P.: The definition of random sequences, Information and Control, 9, 1966, 602-619.
• [22] Morain, R, Olivos, J.: Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Theor. Appl, 24,1990, 531-543,
• [23] Reitwiesner, G. W.: Binary arithmetic, in: Advances in computers, vol. 1, Academic Press, New York, 1960, 231-308.
• [24] Rudin, W.: Real and Complex Analysis, 3rd edition, McGraw-Hill, New York, 1987.
• [25] Staiger, L.: The Kolmogorov complexity of real numbers, Theoretical Computer Science, 284(2), 2002, 455-466.
• [26] Stern, M.: Uber eine zahlentheoretische Funktion, Journal fur die reine und angewandte Mathematik, 55(3), 1858, 193-220.
• [27] Van Lint, J. H.: Introduction to coding theory, vol. 86 of Graduate Texts in Mathematics, 2nd edition, Springer, 1992.
• [28] Weihrauch, K.: Computable Analysis, Springer, Berlin, 2000.