Revista de la
Unión Matemática Argentina
Modular automata
Thomas N. Hibbard, Camilo A. Jadur, and Jorge F. Yazlle

Volume 67, no. 1 (2024), pp. 229–244    

Published online: May 15, 2024

https://doi.org/10.33044/revuma.3076

Download PDF

Abstract

Let $M$ and $b$ be integers greater than 1, and let $\mathbf{p}$ be a positive probability vector for the alphabet $\mathcal{A}_{b}=\{0,\ldots,b-1\}$. Let us consider a random sequence $w_0,w_1,\ldots,w_j$ over $\mathcal{A}_{b}$, where the $w_i$'s are independent and identically distributed according to $\mathbf{p}$. Such a sequence represents, in base $b$, the number $n=\sum_{i=0}^j w_i b^{j-i}$. In this paper, we explore the asymptotic distribution of $n\mbox{ mod }M$, the remainder of $n$ divided by $M$. In particular, by using the theory of Markov chains, we show that if $M$ and $b$ are coprime, then $n\mbox{ mod } M$ exhibits an asymptotic discrete uniform distribution, independent of $\mathbf{p}$; on the other hand, when $M$ and $b$ are not coprime, $n\mbox{ mod }M$ does not necessarily have a uniform distribution, and we obtain an explicit expression for this limiting distribution.

References

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