A multi-cluster time aggregation approach for Markov chains

Fernandes de Arruda, Edilson, Fragoso, Marcelo and Ourique, Fabricio 2019. A multi-cluster time aggregation approach for Markov chains. Automatica 99 , pp. 382-389. 10.1016/j.automatica.2018.10.027

Preview

PDF - Accepted Post-Print Version Download (26MB) | Preview

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	0005-1098
Date of First Compliant Deposit:	6 January 2020
Date of Acceptance:	18 September 2018
Last Modified:	06 Nov 2023 21:45
URI:	https://orca.cardiff.ac.uk/id/eprint/128227

Citation Data

Cited 2 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item