Modular automata
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.
- Dynamical directions in numeration
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 1093829 (Why is no real title available?)
- Number representation and finite automata
- Probabilistic automata
- Probability and random processes.
This page was built for publication: Modular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589667)
