Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

It is known that if x∈[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 β>1 is Pisot, then x is "normal in base β", in the sense that the sequence (xβn)n∈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. © 2015 Elsevier Inc.

Registro:

Documento: Artículo
Título:Normality in non-integer bases and polynomial time randomness
Autor:Almarza, J.I.; Figueira, S.
Filiación:Departamento de Matemática, FCEyN, Universidad de Buenos Aires, Argentina
Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina
CONICET, Argentina
Palabras clave:Algorithmic randomness; Deterministic finite automaton; Martingale; Normality; Pisot number; Polynomial time randomness; Subshift; Polynomial approximation; Polynomials; Algorithmic randomness; Deterministic finite automata; Martingale; Normality; Pisot numbers; Polynomial-time; Subshifts; Random processes
Año:2015
Volumen:81
Número:7
Página de inicio:1059
Página de fin:1087
DOI: http://dx.doi.org/10.1016/j.jcss.2015.04.005
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n7_p1059_Almarza

Referencias:

  • Becher, V., Heiber, P., Slaman, T.A., A polynomial-time algorithm for computing absolutely normal numbers (2013) Inf. Comput., 232, pp. 1-9
  • Bertrand-Mathis, A., Développement en base θ, répartition modulo un de la suite (xθn), n ≥ 0, langages codés et θ-shift (1986) Bull. Soc. Math. Fr., 114, pp. 271-323
  • Brattka, V., Miller, J.S., Nies, A., Randomness and differentiability (2015) Trans. Am. Math. Soc., , arxiv:1104.4465 in press
  • Brown, G., Moran, W., Pearce, C.E.M., A decomposition theorem for numbers in which the summands have prescribed normality properties (1986) J. Number Theory, 24 (3), pp. 259-271. , MR866972 (88c:11044)
  • Coven, E.M., Paul, M.E., Endomorphisms of irreducible subshifts of finite type (1974) Math. Syst. Theory, 8, pp. 167-175
  • Figueira, S., Nies, A., Feasible analysis, randomness and base invariance (2013) Theory Comput. Syst.
  • Kitchens, B., (1998) Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts, , Springer Berlin
  • Ko, K.-I., Friedman, H., Computational complexity of real functions (1982) Theor. Comput. Sci., 20, pp. 323-352
  • Lind, D., Marcus, B., (1995) An Introduction to Symbolic Dynamics and Coding, , Cambridge University Press Cambridge
  • Lutz, J., Mayordomo, E., (2012) Construction of An Absolutely Normal Real Number in Polynomial Time, , Manuscript
  • Norris, J.R., (1997) Markov Chains, , Cambridge University Press Cambridge
  • William, P., On the β-expansions of real numbers (1960) Acta Math. Hung., 11, pp. 401-416
  • Parry, W., Intrinsic Markov chains (1964) Trans. Am. Math. Soc., 112, pp. 55-66
  • Pollington, A.D., The Hausdorff dimension of a set of normal numbers (1981) Pac. J. Math., 95, pp. 193-204
  • Reimann, J., Randomness: Beyond Lebesgue measure (2006) Logic Colloquium 2006, , B. Cooper, H. Geuvers, A. Pillay, J. Väänänen, Cambridge University Press
  • Schnorr, C.-P., Zufälligkeit und Wahrscheinlichkeit (1971) Lecture Notes in Mathematics, 218
  • Schnorr, C.-P., Stimm, H., Endliche Automaten und Zufallsfolgen (1972) Acta Inform., 1, pp. 345-359
  • Shannon, C.E., A mathematical theory of communication (1948) Bell Syst. Tech. J., 27, pp. 379-423
  • Walters, P., An Introduction to Ergodic Theory (1982) Graduate Texts in Mathematics, , Springer-Verlag New York

Citas:

---------- APA ----------
Almarza, J.I. & Figueira, S. (2015) . Normality in non-integer bases and polynomial time randomness. Journal of Computer and System Sciences, 81(7), 1059-1087.
http://dx.doi.org/10.1016/j.jcss.2015.04.005
---------- CHICAGO ----------
Almarza, J.I., Figueira, S. "Normality in non-integer bases and polynomial time randomness" . Journal of Computer and System Sciences 81, no. 7 (2015) : 1059-1087.
http://dx.doi.org/10.1016/j.jcss.2015.04.005
---------- MLA ----------
Almarza, J.I., Figueira, S. "Normality in non-integer bases and polynomial time randomness" . Journal of Computer and System Sciences, vol. 81, no. 7, 2015, pp. 1059-1087.
http://dx.doi.org/10.1016/j.jcss.2015.04.005
---------- VANCOUVER ----------
Almarza, J.I., Figueira, S. Normality in non-integer bases and polynomial time randomness. J. Comput. Syst. Sci. 2015;81(7):1059-1087.
http://dx.doi.org/10.1016/j.jcss.2015.04.005