On conditional stability of autonomous stochastic sequences of machines (Q1909812)

An autonomous stochastic sequential machine (shortly machine) is a triple \(M=(S,X,m)\) where \(S=\{1,2,\dots,n\}\) is a set of states, \(X\) is a finite output alphabet of at least 2 elements and \(m: S\times S\times X\to [0,1]\) satisfying \(\sum \{m(s,t,x): t\in S, x\in X\}=1\) for all \(s\in S\). The machine behavior can be described by the matrices \(M(x)\) whose \((i,j)\) entry is \(m(i,j,x)\). If \(p=x_1x_2\dots x_k\), then \(M(p)=M(x_1)M(x_2)\dots M(x_k)\). The matrices \(M_k=\sum\{M(p): |p|= k\}\) are stochastic for every \(k\geq 1\). For a given initial state \(i\) the sum of the entries in the \(i\)-th column in \(M(p)\) is denoted by \(\mu_M(p)\) and is the probability that \(p\) appears on the output of \(M\). If \(\mu_M(q)\neq 0\), then the conditional probability \(\mu_M(p\mid q)={\mu_M(qp)\over \mu_M(q)}\). A machine \(M=\{M(x): x\in X\}\) is called stable (conditionally stable) if for any initial state in \(S\) and \(\varepsilon > 0\), there is \(\delta > 0\) such that for any machine \(M'\) with the same number of states and same initial state as \(M\), \(\max|m(s,t,x)-m'(s,t,x)|\leq \delta\) implies \(|\mu_M(p)-\mu_{M'}(p)|\leq \varepsilon\) for all \(p\in X^* (|\mu_M(p\mid q)-\mu_{M'}(p\mid q)|\leq \varepsilon\) for all \(p,q\in X^*, \mu_M(q)\mu_{M'}(q)\neq 0)\). Conditional stability forces stability. The converse is not true. The author establishes several sufficient conditions for conditional stability. We quote here only one of the least technical theorems. Theorem: Let \(M=\{M(x): x\in X\}\) be a machine. If for some \(t>0\) every entry in \(M(p)\) is positive for every \(p\) with \(|p|= t\), then \(M\) is conditionally stable.