Modular automata

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.