1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

ODE methods for Markov chain stability with applications to MCMC

  • @INPROCEEDINGS{10.1145/1190095.1190149,
        author={G.  Fort and E. Moulines Moulines and S.  Meyn and P.  Priouret},
        title={ODE methods for Markov chain stability with applications to MCMC},
        proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={4},
        keywords={Markov Chain Monte-Carlo Metropolis-Hastings algorithm fluid limits for general state-space Markov chains fluid limit stability},
        doi={10.1145/1190095.1190149}
    }
    
  • G. Fort
    E. Moulines Moulines
    S. Meyn
    P. Priouret
    Year: 2012
    ODE methods for Markov chain stability with applications to MCMC
    VALUETOOLS
    ACM
    DOI: 10.1145/1190095.1190149
G. Fort1,*, E. Moulines Moulines1,*, S. Meyn2,*, P. Priouret3,*
  • 1: ENST, LTCI UMR 5141, 46 rue Barrault, 75634 Paris Cedex 13, France.
  • 2: CSL, University of Illinois, 1308 West Main Street, Urbana, IL 61801
  • 3: LPMA, UMR 7599, Université Paris VI, 4, Place Jussieu, 75252, PARIS Cedex 05
*Contact email: gfort@tsi.enst.fr, moulines@tsi.enst.fr, meyn@uiuc.edu, priouret@ccr.jussieu.fr

Abstract

Fluid limit techniques have become a central tool to analyze queueing networks over the last decade, with applications to performance analysis, simulation, and optimization.In this paper some of these techniques are extended to a general class of skip-free Markov chains. As in the case of queueing models, a fluid approximation is obtained by scaling time, space, and the initial condition by a large constant. The resulting fluid limit is the solution of an ODE in "most" of the state space. Stability and finer ergodic properties for the stochastic model then follow from stability of the set of fluid limits. Moreover, similar to the queueing context where fluid models are routinely used to design control policies, the structure of the limiting ODE in this general setting provides an understanding of the dynamics of the Markov chain. These results are illustrated through application to Markov Chain Monte Carlo.