Differential equation approximations for Markov chains

Abstract

We formulate some simple conditions under which a Markov chain may be approximated by the solution to a differential equation, with quantifiable error probabilities. The role of a choice of coordinate functions for the Markov chain is emphasised. The general theory is illustrated in three examples: the classical stochastic epidemic, a population process model with fast and slow variables, and core-finding algorithms for large random hypergraphs.

Published in at http://dx.doi.org/10.1214/07-PS121 the Probability Surveys (http://www.i-journals.org/ps/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Differential equation approximations for Markov chains
• Asymptotic analysis of multiscale approximations to reaction networks
• Structure of large random hypergraphs
• The k-core and branching processes
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Convergence of Markov processes near saddle fixed points

Cited by in corpus (58)

• Differential equation approximations for Markov chains
• Scalable load balancing in networked systems: A survey of recent advances
• The k-core and branching processes
• The $\Lambda$-coalescent speed of coming down from infinity
• The emergence of the deterministic Hodgkin--Huxley equations as a limit from the underlying stochastic ion-channel mechanism
• Invertible Bloom Lookup Tables
• Extinction times in the subcritical stochastic SIS logistic epidemic
• Recent progress in coalescent theory
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• Weak convergence of marked point processes generated by crossings of multivariate jump processes. Applications to neural network modeling
• The fluid limit of a random graph model for a shared ledger
• Laws of large numbers and Langevin approximations for stochastic neural field equations
• Continuum and thermodynamic limits for a simple random-exchange model
• A consistency estimate for Kac's model of elastic collisions in a dilute gas
• Isotropic Wave Turbulence with simplified kernels: existence, uniqueness and mean-field limit for a class of instantaneous coagulation-fragmentation processes
• Predicting the Impact of Measures Against P2P Networks on the Transient Behaviors
• Scaling Limits and Generic Bounds for Exploration Processes
• Susceptible-Infected Epidemics on Evolving Graphs
• Geometric fluid approximation for general continuous-time Markov chains
• Connecting deterministic and stochastic metapopulation models
• A Stochastic Analysis of Bike Sharing Systems
• Laws of large numbers for the frog model on the complete graph
• Stationary solutions of discrete and continuous Petri nets with priorities
• Rank deficiency in sparse random GF[2] matrices
• Buffer Occupancy and Delivery Reliability Tradeoffs for Epidemic Routing
• Dynamics, robustness and fragility of trust
• Equilibrium price in intraday electricity markets
• Over-Approximation of Fluid Models
• Efficient Checking of Individual Rewards Properties in Markov Population Models
• Design and Optimisation of the FlyFast Front-end for Attribute-based Coordination
• Random walks on discrete cylinders with large bases and random interlacements
• Law of large numbers for the SIR epidemic on a random graph with given degrees
• The core in random hypergraphs and local weak convergence
• Warning Propagation on random graphs
• The spread of fire on a random multigraph
• Coupled Systems of Differential-Algebraic and Kinetic Equations with Application to the Mathematical Modelling of Muscle Tissue
• Co-evolution of Content Popularity and Delivery in Mobile P2P Networks
• Warning Propagation: stability and subcriticality
• A stochastic epidemiological model and a deterministic limit for BitTorrent-like peer-to-peer file-sharing networks
• Limiting the spread of disease through altered migration patterns
• Stochastic calculus and sample path estimation for jump processes
• Nonlinear Markov Processes in Big Networks
• Continuous-time mean field Markov decision models
• A scaling limit for the degree distribution in sublinear preferential attachment schemes
• Extinction time of stochastic SIRS models with small initial size of the infected population
• The Impact of Smartphone Apps on Bike Sharing Systems
• Topology Inference over Networks with Nonlinear Coupling
• SIR Epidemics on Evolving Erdős-Rényi Graphs
• Latent Voter Model on Locally Tree-Like Random Graphs
• Optimal Forwarding in Delay Tolerant Networks with Multiple Destinations
• The Limits to Learning a Diffusion Model
• Vertices of high degree in the preferential attachment tree
• Thermodynamic Limit of Interacting Particle Systems over Time-varying Sparse Random Networks
• Extremal shift rule for continuous-time zero-sum Markov games
• A stochastic min-driven coalescence process and its hydrodynamical limit
• The Mean Drift: Tailoring the Mean Field Theory of Markov Processes for Real-World Applications
• Sharp approximation for density dependent Markov chains
• The Effect of Recombination on the Speed of Evolution