A multi-cluster time aggregation approach for Markov chains. (January 2019)

• Record Type: Journal Article
• Authors: Arruda, Edilson; Fragoso, Marcelo; Ourique, Fabricio
• Is Part Of: Automatica. Volume 99(2019)
• Page Start: 382
• Page End: 389
• Publication Date: 2019-01
• Subjects: Markov processes -- Embedding -- Time aggregation -- Policy evaluation; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2018.10.027
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: 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.