Expected passage times in homogeneous quasi-birth-and-death processes

Recently, very efficient algorithms have been found, to compute the stationary distribution of finite and infinite quasi-birth-and-death processes. Here, the authors consider the probem of determining various first passage times from some level to another level. They briefly review the previously published results on this subject. Then, using the spatial homogeneity of the process, the authors establish a simple property which may serve as a general method for solution. They demonstrate its use on various examples. The most striking result is an algorithm which computes the expected first passage time from the level 0 to some level K in O(log2K) elementary steps.