Markov chains with discontinuous drifts have differential inclusions limits. Application to stochastic stability and mean field approximation. - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

Markov chains with discontinuous drifts have differential inclusions limits. Application to stochastic stability and mean field approximation.

(1, 2) , (1)
1
2

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.
Ce document étudie des limites d'échelle de chaînes de Markov ayant une dérive discontinue. Alors que beaucoup de travaux sur le sujet supposent que la dérive est continue, nous montrons que cette condition n'est pas nécessaire pour obtenir une limite déterministe. Nous montrons que sous des hypothèses faibles, un passage à l'échelle d'une chaîne de Markov peut être vu comme un algorithme d'approximation stochastique à pas constant, qui converge vers l'ensemble des solutions d'une inclusion différentielle. Cette inclusion est obtenue à partir d'une convexification de la dérive du processus initial. Cette méthode est générique et permet de calculer la région de stabilité de nombreux systèmes stochastique, en étudiant leur limite fluide. Elle permet aussi d'étendre les techniques d'approximation champ moyen à des systèmes où les discontinuités apparaissent naturellement, comme des réseaux de files d'attente ou des systèmes contrôlés par une politique à seuil.
Fichier principal
Vignette du fichier
GastGaujal_MarkovDifferentialInclusions.pdf (698.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00491859 , version 1 (15-06-2010)
inria-00491859 , version 2 (22-12-2010)
inria-00491859 , version 3 (11-04-2011)
inria-00491859 , version 4 (12-03-2012)

Identifiers

  • HAL Id : inria-00491859 , version 4

Cite

Nicolas Gast, Bruno Gaujal. Markov chains with discontinuous drifts have differential inclusions limits. Application to stochastic stability and mean field approximation.. [Research Report] RR-7315, INRIA. 2012. ⟨inria-00491859v4⟩
431 View
399 Download

Share

Gmail Facebook Twitter LinkedIn More