Algorithms for an irreducible and lumpable strong stochastic bound (Q1434421)

As an extension of Vincent algorithm, a fairly new method based on the algorithmic derivation of a lumpable stochastic bounding matrix is proposed in order to analyze large state-space problems related to discrete time Markov chains with transition matrix \(P\). The main idea is to choose heuristically a partition which implies a large reduction of the state-space and may provide an appropriate irreducible, upper bound \(R\) for \(P\) during the bounding process. Because of the lumpability of the upper bound \(R\), the related numerical analysis deals with smaller matrices, and the lumped version is stored on the disk. The implementation is done using only 2 vectors in the memory. A basic algorithm IMSUB deals with the irreducibility of the bounding matrix. The method is purely algorithmic and algebraic, and it does not require proofs based on the sample-path theorem and coupling [see \textit{D. Stoyan}, Comparison methods for queues and other stochastic models, (Wiley) (1983; Zbl 0536.60085) for some examples)]. The algorithm is very efficient since it avoids to keep the entire transition matrix \(P\) in main memory. Monotonicity and comparability of one step transition probability matrices of time-homogeneous Markov chains is discussed too. An application of the proposed algorithm to the computation of the loss probabilities in a shared buffer with the Robin service discipline and the Pushout memory access algorithm is presented.