We present an approximation for the stationary distribution π of a countably infinite-state Markov chain with transition probability matrix P = (pij) of upper Hessenberg form. Our approximation makes use of an associated upper Hessenberg matrix which is spatially homogeneous one P(N) except for a finite number of rows obtained by letting pij = pj−i+1, i ⩾ N + 1, for some distribution p = {pj} with mean p < 1, where p−j = 0 for j ⩾ 1. We prove that there exists an optimal p, say p*(N) with which our method provides exact probabilities up to the level N. However, in general to find this optimal p*(N) is practically impossible unless one has the exact distribution π. Therefore, we propose a number of approximations to p*(N) and prove that a better approximation than that given by finite truncation methods can be obtained in the sense of smaller l1-distance between exact distribution of its approximation. Numerical experiments are implemented for the M/M/1 retrial queue.
