On conditional stability of autonomous stochastic sequences of machines

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.

Recommendations

Cited in

(5)

This page was built for publication: On conditional stability of autonomous stochastic sequences of machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1909812)