Markov chains with discontinuous drifts have differential inclusion limits

Nicolas Gast 1 Bruno Gaujal 2
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we study deterministic limits of Markov processes having discontinuous drifts. While most results assume that the limiting dynamics is continuous, we show that these conditions are not necessary to prove convergence to a deterministic system. More precisely, we show that under mild assumptions, the stochastic system is a stochastic approximation algorithm with constant step size that converges to a differential inclusion. This differential inclusion is obtained by convexifying the rescaled drift of the Markov chain. This generic convergence result is used to compute stability conditions of stochastic systems, via their fluid limits. It is also used to analyze systems where discontinuous dynamics arise naturally, such as queueing systems with boundary conditions or with threshold control policies, via mean field approximations.
Complete list of metadatas

https://hal.inria.fr/hal-00787999
Contributor : Arnaud Legrand <>
Submitted on : Wednesday, February 13, 2013 - 2:57:22 PM
Last modification on : Thursday, October 11, 2018 - 8:48:02 AM

Links full text

Identifiers

Collections

Citation

Nicolas Gast, Bruno Gaujal. Markov chains with discontinuous drifts have differential inclusion limits. Performance Evaluation, Elsevier, 2012, 69 (12), pp.623-642. ⟨10.1016/j.peva.2012.07.003⟩. ⟨hal-00787999⟩

Share

Metrics

Record views

268