Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

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


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: 22 Jan 2021 14:41

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics