Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTransient Reward Approximation for Continuous-Time Markov Chains
227
0
0.0
(
0
)
Added by
Ralf Wimmer
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We are interested in the analysis of very large continuous-time Markov chains (CTMCs) with many distinct rates. Such models arise naturally in the context of reliability analysis, e.g., of computer network performability analysis, of power grids, of computer virus vulnerability, and in the study of crowd dynamics. We use abstraction techniques together with novel algorithms for the computation of bounds on the expected final and accumulated rewards in continuous-time Markov decision processes (CTMDPs). These ingredients are combined in a partly symbolic and partly explicit (symblicit) analysis approach. In particular, we circumvent the use of multi-terminal decision diagrams, because the latter do not work well if facing a large number of different rates. We demonstrate the practical applicability and efficiency of the approach on two case studies.
rate research
Read More
Continuous-time Markov chains are mathematical models that are used to describe the state-evolution of dynamical systems under stochastic uncertainty, and have found widespread applications in various fields. In order to make these models computationally tractable, they rely on a number of assumptions that may not be realistic for the domain of application; in particular, the ability to provide exact numerical parameter assessments, and the applicability of time-homogeneity and the eponymous Markov property. In this work, we extend these models to imprecise continuous-time Markov chains (ICTMCs), which are a robust generalisation that relaxes these assumptions while remaining computationally tractable. More technically, an ICTMC is a set of precise continuous-time finite-state stochastic processes, and rather than computing expected values of functions, we seek to compute lower expectations, which are tight lower bounds on the expectations that correspond to such a set of precise models. Note that, in contrast to e.g. Bayesian methods, all the elements of such a set are treated on equal grounds; we do not consider a distribution over this set. The first part of this paper develops a formalism for describing continuous-time finite-state stochastic processes that does not require the aforementioned simplifying assumptions. Next, this formalism is used to characterise ICTMCs and to investigate their properties. The concept of lower expectation is then given an alternative operator-theoretic characterisation, by means of a lower transition operator, and the properties of this operator are investigated as well. Finally, we use this lower transition operator to derive tractable algorithms (with polynomial runtime complexity w.r.t. the maximum numerical error) for computing the lower expectation of functions that depend on the state at any finite number of time points.
We consider a generalization of the Ruelle theorem for the case of continuous time problems. We present a result which we believe is important for future use in problems in Mathematical Physics related to $C^*$-Algebras We consider a finite state set $S$ and a stationary continuous time Markov Chain $X_t$, $tgeq 0$, taking values on S. We denote by $Omega$ the set of paths $w$ taking values on S (the elements $w$ are locally constant with left and right limits and are also right continuous on $t$). We consider an infinitesimal generator $L$ and a stationary vector $p_0$. We denote by $P$ the associated probability on ($Omega, {cal B}$). This is the a priori probability. All functions $f$ we consider bellow are in the set ${cal L}^infty (P)$. From the probability $P$ we define a Ruelle operator ${cal L}^t, tgeq 0$, acting on functions $f:Omega to mathbb{R}$ of ${cal L}^infty (P)$. Given $V:Omega to mathbb{R}$, such that is constant in sets of the form ${X_0=c}$, we define a modified Ruelle operator $tilde{{cal L}}_V^t, tgeq 0$. We are able to show the existence of an eigenfunction $u$ and an eigen-probability $ u_V$ on $Omega$ associated to $tilde{{cal L}}^t_V, tgeq 0$. We also show the following property for the probability $ u_V$: for any integrable $gin {cal L}^infty (P)$ and any real and positive $t$ $$ int e^{-int_0^t (V circ Theta_s)(.) ds} [ (tilde{{cal L}}^t_V (g)) circ theta_t ] d u_V = int g d u_V$$ This equation generalize, for the continuous time Markov Chain, a similar one for discrete time systems (and which is quite important for understanding the KMS states of certain $C^*$-algebras).
Verifying quantum systems has attracted a lot of interests in the last decades. In this paper, we initialised the model checking of quantum continuous-time Markov chain (QCTMC). As a real-time system, we specify the temporal properties on QCTMC by signal temporal logic (STL). To effectively check the atomic propositions in STL, we develop a state-of-art real root isolation algorithm under Schanuels conjecture; further, we check the general STL formula by interval operations with a bottom-up fashion, whose query complexity turns out to be linear in the size of the input formula by calling the real root isolation algorithm. A running example of an open quantum walk is provided to demonstrate our method.
This paper contributes an in-depth study of properties of continuous time Markov chains (CTMCs) on non-negative integer lattices $N_0^d$, with particular interest in one-dimensional CTMCs with polynomial transitions rates. Such stochastic processes are abundant in applications, in particular in biology. We characterize the structure of the state space of general CTMCs on $N_0^d$ in terms of the set of jump vectors and their corresponding transition rate functions. For CTMCs on $N_0$ with polynomial transition rate functions, we provide threshold criteria in terms of easily computable parameters for various dynamical properties such as explosivity, recurrence, transience, certain absorption, positive/null recurrence, implosivity, and existence and non-existence of moments of hitting times. In particular, simple sufficient conditions for exponential ergodicity of stationary distributions and quasi-stationary distributions are obtained, and the few gap cases are well-illustrated by examples. Subtle differences in conditions for different dynamical properties are revealed in terms of examples. Finally, we apply our results to stochastic reaction networks, an extended class of branching processes, a general bursty single-cell stochastic gene expression model, and population processes which are not birth-death processes.
We study certain properties of the function space of autocorrelation functions of Unit Continuous Time Markov Chains (CTMCs). It is shown that under particular conditions, the $L^p$ norm of the autocorrelation function of arbitrary finite state space CTMCs is infinite. Several interesting inferences are made for point processes associated with CTMCs/ Discrete Time Markov Chains (DTMCs).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
