Modular automata

• Thomas N. Hibbard ^[1] ; Camilo A. Jadur ^[1] ; Jorge F. Yazlle ^[1]
  1. [1] Universidad Nacional de Salta

     Universidad Nacional de Salta

     Argentina

     
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 67, Nº. 1, 2024, págs. 229-244
• Idioma: inglés
• DOI: 10.33044/revuma.3076
• Enlaces
  • Texto completo
• Resumen

  • Let M and b be integers greater than 1, and let p be a positive probability vector for the alphabet Ab={0,…,b−1}. Let us consider a random sequence w0,w1,…,wj over AbAb, where the wi's are independent and identically distributed according to p. Such a sequence represents, in base b, the number n=∑ji=0wibj−i. In this paper, we explore the asymptotic distribution of n mod M, the remainder of nn divided by M. In particular, by using the theory of Markov chains, we show that if M and b are coprime, then n mod M exhibits an asymptotic discrete uniform distribution, independent of p; on the other hand, when Mand b are not coprime, n mod M does not necessarily have a uniform distribution, and we obtain an explicit expression for this limiting distribution.

• Referencias bibliográficas
  • SageMath, the Sage Mathematics Software System (Version 9.2), The Sage Developers, 2020. Available at https://sagemath.org.
  • G. Barat, V. Berthe´, P. Liardet, and J. Thuswaldner, Dynamical directions in numeration, Ann. Inst. Fourier (Grenoble) 56 no. 7 (2006), 1987–2092....
  • C. Frougny and J. Sakarovitch, Number representation and finite automata, in Combinatorics, automata and number theory, Encyclopedia Math....
  • G. R. Grimmett and D. R. Stirzaker, Probability and random processes, third ed., Oxford University Press, New York, 2001. MR Zbl
  • G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, fourth ed., Oxford, at the Clarendon Press, 1960. MR Zbl
  • J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley,...
  • D. E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, second ed., Addison-Wesley Series in Computer Science and...
  • M. O. Rabin, Probabilistic automata, Inf. Control 6 no. 3 (1963), 230–245. DOI Zbl
  • S. M. Ross, Stochastic processes, second ed., Wiley Series in Probability and Statistics, John Wiley & Sons, New York, 1996. MR Zbl