Continuous-time Markov chains as transformers of unbounded observablesReportar como inadecuado

Continuous-time Markov chains as transformers of unbounded observables - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 ENS Paris - Ecole Normale Supérieure de Paris 2 DIKU - Department of computer Science Copenhagen 3 Informatics - School of Informatics

Abstract : This paper provides broad sufficient conditions for the com-putability of time-dependent averages of stochastic processes of the form f Xt where Xt is a continuous-time Markov chain CTMC, and f is a real-valued function aka an observable. We consider chains with values in a countable state space S, and possibly unbounded f s. Observables are seen as generalised predicates on S and chains are interpreted as transformers of such generalised predicates, mapping each observable f to a new observable Ptf defined as Ptfx = Exf Xt, which represents the mean value of f at time time t as a function of the initial state x. We obtain three results. First, the well-definedness of this operator interpretation is obtained for a large class of chains and observables by restricting Pt to judiciously chosen rescalings of the basic Banach space C0S of S-indexed sequences which vanish at infinity. We prove, under appropriate assumptions, that the restricted family Pt forms a strongly continuous operator semigroup equivalently the time evolution map t → Pt is continuous w.r.t. the usual topology on bounded operators. The computability of the time evolution map follows by generic arguments of constructive analysis. A key point here is that the assumptions are flexible enough to accommodate unbounded observables, and we give explicit examples of such using stochastic Petri nets and stochastic string rewriting. Thirdly, we show that if the rate matrix aka the q-matrix of the CTMC is locally algebraic on a subspace containing f , the time evolution of projections t → Ptfx is PTIME computable for each x. These results provide a functional analytic alternative to Monte Carlo simulation as test bed for mean-field approximations, moment closure, and similar techniques that are fast, but lack absolute error guarantees.

Keywords : Probabilistic systems Computability theory

Autor: Vincent Danos - Tobias Heindel - Ilias Garnier - Jakob Simonsen -



Documentos relacionados