How to solve 2D Markov Chains with Infinite State Space

Question

I have 2 dimensional markov chain and I want to calculate steady state probabilities and then basic performance measurements such as expected number of customers, expected waiting time, etc. You can check the transition rate diagram link below:

http://tinypic.com/view.php?pic=2n063dd&s=8

As I search for solution methods, matrix geometric and spectral expansion methods appear. I tried matrix geometric method, however since my Markov chain is not repetitive, it did not work.

I read some paper (e.g. Spectral expansion solution for a class of Markov models: application and comparison with the matrix-geometric method), but I could not figure out how to create matrices and what is the steady state probabilities.

1. Does spectral expansion method require "repetitive process" as matrix geometric method does? If no, how to apply to my problem?
2. Are there any other methods to compute?

Thanks for all your help!

Ali

Answer 1

First, there is no stable solution method for two-way infinite lattice strip. At least one variable should be capacitated. Second, the following are the most known solution methods for two-dimensional Markov chains with semi-infinite or finite state space:

• Spectral Expansion Method
• Matrix Geometric Method
• Block Gauss-Seidel Method
• Seelen's Method

All methods require high computational work. Experimental studies show that for semi-infinite lattice strip, as the capacitated variable exceeds 50, solution may not be trustable. Also there is a state explosion problem beyond that threshold. To overcome the state explosion problem, iterative methods are used such Gauss-Seidel and Seelen's methods.

Regarding my problem, I determined capacity for both variables. After a search in the literature, block Gauss-Seidel Iterative method seems to be the most appropriate method to apply my problem.

Thank you.