Indeterminate Markov systems (Q1899341)

Let \(P\leq Q\) (componentwise) be \(n\times n\) nonnegative matrices; \(p\leq q\), \(\ell\leq h\), \(r\), \(s\) be \(1\times n\) nonnegative vectors. Define \[ \begin{multlined} A= [P, Q]= \bigl\{ B:\;B \text{ is an \(n\times n\) nonnegative matrix where }P\leq B\leq Q \text{ and}\\ r_i\leq \sum_k b_{ik}\leq s_i \text{ for all }i\bigr\}.\end{multlined} \] Define \(b= [p, q]= \{c\): \(c\) is a \(1\times n\) nonnegtive vector with \(p\leq c\leq q\}\), and \(X_0= [\ell, h]\) similarly. This paper considers the set valued difference equation \[ X_{k+1}= X_k A+b= \{\overline {x}:\;\overline {x}= xB+c \text{ where } x\in X_k,\;B\in A, \text{ and } c\in b\}. \] It is shown that each \(X_k\) is a compact convex polytope. These polytopes can have numerous vertices, so the paper describes how to compute tight component bounds on the vectors in \(X_k\) for all \(k\geq 0\).