Modular automata (Q6589667)

This paper considers the random variable \(X_k = \sum_{i=0}^k w_i b^{k-i}\) mod \(M\), where \(M\) and \(b\) are integers larger than 1 and the \(w_i\in \{0,\dots,b-1\}\) are chosen randomly according to some probability vector \(\mathbf{p}\). The authors show that if \(M\) and \(b\) are coprime, then the asymptotic distribution of \(X_k\) is uniform, completely independent of the choice of \(\mathbf{p}\). This is done by associating to this random process a Markov chain, so that finding the asymptotic distribution is equivalent to finding the invariant vector for the associated transition matrix. The situation where \(M\) and \(b\) are not coprime is also considered, and a formula for the (not uniform) distribution in this situation is produced.\N\NThe paper begins with some motivating examples, for instance, a simulation that produces a sequence \(w_0w_1 \cdots w_{99}\) of 0's and 1's randomly according to a distribution \((p, 1-p)\), and then computes the integer \(n = \sum_{i=0}^{99}w_ib^{99-i}\) mod \(M\). They show that for \(M\) odd, such a simulation over a large number of trials yields a probability distribution that seems to be tending towards \((\frac{1}{M}, \dots,\frac{1}{M})\), and this remains true for three different values of \(p\) used. On the other hand, when \(M\) is even, the resulting probability distribution yields results that depend on \(p\). These results are presented at the end of the paper, providing a nice illustration of the result.