Two-dimensional Markov chains with geometric jumps


Adan, I.J.B.F., Visschers, J.W.C.H. & Wessels, J. (1999). Two-dimensional Markov chains with geometric jumps. (Memorandum COSOR, No. 9901). Eindhoven: Technische Universiteit Eindhoven, 28 pp. Lees meer: Medialink/Full text



Several queueing problems lead to Markov chains with jumps of unbounded length, particularly with geometric behaviour in one or more directions. In the present paper the equilibrium behaviour is analysed for two-dimensional nearest neighbour random walks, which may make geometric jumps in one direction. The first step in the analysis consists of searching for product forms satisfying the equilibrium equations for inner states. This is made possible by simplifying the equations by taking differences of equations for neighbouring states in a well-chosen direction. Such a difference is called \Delta-equation. It appears that the \Delta-equation is state-independent. Therefore one obtains two equations, the starting equation and the \Delta-equation; these equations have a large set of product form solutions S. It appears that, in the case of no transitions from inner states to the North, North-East and East, plus some restrictions on the horizontal boundary, there is a linear combination of countably many product forms from S which satisfies the boundary equations. This linear ombination may be constructed with a compensation procedure. In other cases there is a finite linear combination from S satisfying the boundary equations, if the boundary equations satisfy some rather severe extra conditions.