| Search the Collection|Browse Subjects|Services|Library Information|Community |News & Events | |
|
|
|
|
|
|
|
|
||||
|
|||||||
Type of Document Dissertation Author Peng, Bin , Author's Email Address bpeng2@unity.ncsu.edu URN etd-11292004-223731 Title Convergence, Rank Reduction and Bounds for the Stationary Analysis of Markov Chains Degree PhD Graduate Program Operations Research Advisory Committee
Advisor Name Title William J. Stewart Committee Chair Keywords
- Markov chains
- bounds
- stationary analysis
- stochastic ordering
- rank reduction
- convergence
Date of Defense 2004-10-29 Availability unrestricted Abstract We introduce a rank reduction method for computing stationary distributions of Markov chains for which low-rank iteration matrices can be formed. We first prove that, for an irreducible Markov chain, a necessary and sufficient condition for convergence in a single iteration is that the iteration matrix have rank one. Since most iteration matrices have rank larger than 1,we also consider the Wedderburn rank-1 reduction formula and develop a rank reduction procedure that takes an initial iteration matrix with rank greater than one and modifies it in successive steps, under the constraint that the exact solution be preserved at each step, until a rank-1 iteration matrix is obtained. When the iteration matrix has rank r, the proposed algorithm
has time complexity O(r^2n). Secondly we investigate the relationship among lumpability, weak lumpability, quasi-lumpability and near complete decomposability. These concepts
are important in aggregating and disaggregating Markov chains. White's algorithm for identifying all possible lumpable partitions for Markov
chains is improved by incorporating lumpability tests on special state orderings. Finally,
instead of computing exact stationary distributions, we design stochastic-ordering-based techniques to bound them. Upper bounds can be
obtained by using constructive algorithms developed recently. We observe that the more lumpable partitionings, the more accurate the upper bound for the state of interest both
with matrix transformation and without matrix transformation. Lastly we combine the approaches of state permutation, matrix transformation and state partitioning to improve the quality
of the upper bound for the state of interest.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access etd.pdf 751.74 Kb 00:03:28 00:01:47 00:01:33 00:00:46 00:00:04