Ramaswami's duality and probabilistic algorithms for determining the rate matrix for a structured GI/M/1 Markov chain

Abstract

We show that Algorithm H* for the determination of the rate matrix of a block-GI / M / 1 Markov chain is related by duality to Algorithm H for the determination of the fundamental matrix of a block-M / G / 1 Markov chain. Duality is used to generate some efficient algorithms for finding the rate matrix in a quasi-birth-and-death process.