Bounds on the deviation of discrete-time Markov chains from their mean-field model

TitleBounds on the deviation of discrete-time Markov chains from their mean-field model
Publication TypeJournal Article
Year of Publication2013
AuthorsBortolussi L, Hayden R
JournalPerformance Evaluation
Volume70
Issue10
Pages736-749
KeywordsMarkov population models, mean field approximation, Steady state error bounds for mean field, Steady state mean field approximation, Transient error bounds for mean field
Abstract

We consider a generic mean-field scenario, in which a sequence of population models, described by discrete- time Markov chains (DTMCs), converges to a deterministic limit in discrete time. Under the assumption that the limit has a globally attracting equilibrium, the steady states of the sequence of DTMC models converge to the point-mass distribution concentrated on this equilibrium. In this paper we provide explicit bounds in probability for the convergence of such steady states, combining stochastic bounds on the local error with control-theoretic tools used in the stability analysis of perturbed dynamical systems to bound the global accumulation of error. We also adapt this method to compute bounds on the transient dynamics. The approach is illustrated by a wireless sensor network example.

Notes

Proceedings of the 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation 2013, PERFORMANCE 2013

URLhttp://www.sciencedirect.com/science/article/pii/S0166531613000904
DOI10.1016/j.peva.2013.08.012