A Two-Stage Iteration for Solving Nearly Uncoupled Markov Chains

Loading...
Thumbnail Image

Files

CS-TR-1384.ps (202.4 KB)
No. of downloads: 205
CS-TR-1384.pdf (212.37 KB)
No. of downloads: 483

Publication or External Link

Date

1995-02-06

Advisor

Citation

DRUM DOI

Abstract

This paper is concerned with an iteration for determining the steady-state probability vector of a nearly uncoupled Markov Chain. The states of these chains can be partitioned into aggregates with low probabilities of transitions between aggregates. The iteration consists of alternating block Gauss--Seidel iterations with Rayleigh--Ritz refinements. Under natural regularity conditions, the composite iteration reduces the error by a factor proportional to the size of the coupling between aggregates, so that the more loosely the chain is coupled, the faster the convergence.

Notes

Rights