## 5 Probabilistic Arithmetic Automata
### Random Text Models  
Given an alphabet \(\Sigma\), a random text is a stochastic process \((S_{t})_{t\in\mathbb{N}_{0}}\), where each \(S_{t}\) takes values in \(\Sigma\). A text model \(\mathbb{P}\) is a probability measure assigning probabilities to (sets of) strings. It is given by (consistently) specifying the probabilities \(\mathbb{P}(S_{0}\ldots S_{|s|-1}=s)\) for all \(s\in\Sigma^{*}\). We only consider finite-memory models in this article which are formalized in the following definition.  
**Definition 3** (Finite-memory text model): _A finite-memory text model is a tuple \((\mathcal{C},c_{0},\Sigma,\varphi)\), where \(\mathcal{C}\) is a finite state space (called context space), \(c_{0}\in\mathcal{C}\) a start context, \(\Sigma\) an alphabet, and \(\varphi:\mathcal{C}\times\Sigma\times\mathcal{C}\rightarrow[0,1]\) a transition function with \(\sum_{\sigma\in\Sigma,\sigma^{\prime}\in\mathcal{C}}\varphi(c,\sigma,c^{ \prime})=1\) for all \(c\in\mathcal{C}\). The random variable giving the text model state after \(t\) steps is denoted \(C_{t}\) with \(C_{0}:\equiv c_{0}\). A probability measure is now induced by stipulating_  
\[\mathbb{P}(S_{0}\ldots S_{n-1}=s,C_{1}=c_{1},\ldots,C_{n}=c_{n}):=\prod_{i=0} ^{n-1}\,\varphi(c_{i},s[i],c_{i+1})\]  
_for all \(n\in\mathbb{N}_{0}\), \(s\in\Sigma^{n}\), and \((c_{1},\ldots,c_{n})\in\mathcal{C}^{n}\)._The idea is that the model given by \((\mathcal{C},c_{0},\Sigma,\varphi)\) generates a random text by moving from context to context and emitting a character at each transition, where \(\varphi(c,\sigma,c^{\prime})\) is the probability of moving from context \(c\) to context \(c^{\prime}\) and thereby generating the letter \(\sigma\).  
Note that the probability \(\mathbb{P}(S_{0}\ldots S_{|s|-1}=s)\) is obtained by marginalization over all context sequences that generate \(s\). This can be efficiently done, using the decomposition of the following lemma.  
**Lemma 1**: _Let \((\mathcal{C},c_{0},\Sigma,\varphi)\) be a finite-memory text model. Then,_  
\[\mathbb{P}(S_{0}\ldots S_{n}=s\sigma,C_{n+1}=c)=\sum_{c^{\prime}\in\mathcal{C} }\,\mathbb{P}(S_{0}\ldots S_{n-1}=s,C_{n}=c^{\prime})\cdot\varphi(c^{\prime}, \sigma,c)\]  
_for all \(n\in\mathrm{N}_{0}\), \(s\in\Sigma^{n}\), \(\sigma\in\Sigma\) and \(c\in\mathcal{C}\)._  
ProofWe have  
\[\mathbb{P}(S_{0}\ldots S_{n}=s\sigma,C_{n+1}=c)\] \[= \sum_{c_{1},\ldots,c_{n}}\,\mathbb{P}(S_{0}\ldots S_{n}=s\sigma, C_{1}=c_{1},\ldots,C_{n}=c_{n},C_{n+1}=c)\] \[= \sum_{c_{1},\ldots,c_{n}}\,\prod_{i=0}^{n-1}\,\varphi(c_{i},s[i],c_{i+1})\cdot\varphi(c_{n},\sigma,c)\] \[= \sum_{c_{n}\in\mathcal{C}}\,\left(\sum_{c_{1},\ldots,c_{n-1}}\, \prod_{i=0}^{n-1}\,\varphi(c_{i},s[i],c_{i+1})\right)\cdot\varphi(c_{n},\sigma,c)\] \[= \sum_{c_{n}\in\mathcal{C}}\,\mathbb{P}(S_{0}\ldots S_{n-1}=s,C_{ n}=c_{n})\cdot\varphi(c_{n},\sigma,c)\]  
Renaming \(c_{n}\) to \(c^{\prime}\) yields the claimed result. \(\Box\)  
Similar text models are used in [23], where they are called probability transducers. In the following, we refer to a finite-memory text model \((\mathcal{C},c_{0},\Sigma,\varphi)\) simply as text model, as all text models considered in this article are special cases of Definition 3.  
For an i.i.d. model, we set \(\mathcal{C}=\{\varepsilon\}\) and \(\varphi(\varepsilon,\sigma,\varepsilon)=p_{\sigma}\) for each \(\sigma\in\Sigma\), where \(p_{\sigma}\) is the occurrence probability of letter \(\sigma\) (and \(\varepsilon\) may be interpreted as an empty context). For a Markovian text model of order \(r\), the distribution of the next character depends on the \(r\) preceding characters (fewer at the beginning); thus \(\mathcal{C}:=\bigcup_{i=0}^{r}\Sigma^{i}\). This notion of text models also covers variable order Markov chains as introduced in [24], which can be converted into equivalent models of fixed order. Text models as defined above have the same expressive power as character-emitting HMMs, that means, they allow to construct the same probability distributions.