Skip to Main content Skip to Navigation
Conference papers

Bounded state space truncation and Censored Markov chains

Abstract : Markov chain modeling often suffers from the curse of dimensionality problems and many approximation schemes have been proposed in the literature that include state-space truncation. Estimating the accuracy of such methods is difficult and the resulting approximations can be far from the exact solution. Censored Markov chains (CMC) allow to represent the conditional behavior of a system within a subset of observed states and provide a theoretical framework to study state-space truncation. However, the transition matrix of a CMC is in general hard to compute. Dayar et al. (2006) proposed DPY algorithm, that computes a stochastic bound for a CMC, using only partial knowledge of the original chain. We prove that DPY is optimal for the information they take into account. We also show how some additional knowledge on the chain can improve stochastic bounds for CMC.
Document type :
Conference papers
Complete list of metadata
Contributor : Ana Busic <>
Submitted on : Tuesday, June 18, 2013 - 4:23:17 PM
Last modification on : Thursday, July 1, 2021 - 5:58:03 PM

Links full text



Ana Bušić, Hilal Djafri, Jean-Michel Fourneau. Bounded state space truncation and Censored Markov chains. CDC - 51st IEEE Conference on Decision and Control - 2012, Dec 2012, Maui, Hawaii, United States. pp.5828-5833, ⟨10.1109/CDC.2012.6426156⟩. ⟨hal-00835445⟩



Record views