A multi-cluster time aggregation approach for Markov chains
| Autor: | Marcelo D. Fragoso, Fabrício Ourique, Edilson F. Arruda |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Steady state (electronics) Markov chain Computer science Computation 020208 electrical & electronic engineering 02 engineering and technology Partition (database) 020901 industrial engineering & automation Cardinality Control and Systems Engineering Convergence (routing) 0202 electrical engineering electronic engineering information engineering State space Electrical and Electronic Engineering Algorithm Curse of dimensionality |
| Zdroj: | Automatica. 99:382-389 |
| ISSN: | 0005-1098 |
| Popis: | This work focuses on the computation of the steady state distribution of a Markov chain, making use of an embedding algorithm. In this regard, a well-known approach dubbed time aggregation has been proposed in Cao et al., (2002). Roughly, the idea hinges on the partition of the state space into two subsets. The linchpin in this partitioning process is a small subset of states, selected to be the state space of the aggregated process, which will account for the state space of the embedded semi-Markov process. Although this approach has provided an interesting body of theoretical results and advanced in the study of the so-called curse of dimensionality, one is still left with a high-dimensional problem to be solved. In this paper we investigate the possibility to remedy this problem by proposing a time aggregation approach with multiple subsets. This is achieved by devising a decomposition algorithm which makes use of a partition scheme to evaluate the steady state probabilities of the chain. Besides the convergence proof of the algorithm, we prove also a result for the cardinality of the partition, vis-à-vis the computational effort of the algorithm, for the case in which the state space is partitioned in a collection of subsets of the same cardinality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect