Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 5 (2008) open journal systems 


Differential equation approximations for Markov chains

Richard W.R. Darling, National Security Agency
James Ritchie Norris, University of Cambridge


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.

AMS 2000 subject classifications: Primary 05C65; secondary 60J75, 05C80.

Creative Common LOGO

Full Text: PDF


Darling, Richard W.R., Norris, James Ritchie, Differential equation approximations for Markov chains, Probability Surveys, 5, (2008), 37-79 (electronic). DOI: 10.1214/07-PS121.

References

[1]     Dimitris Achlioptas. Lower bounds for random 3-SAT via differential equations. Theoret. Comput. Sci., 265(1-2):159–185, 2001. Phase transitions in combinatorial problems (Trieste, 1999). MR1848217

[2]     Karen Ball, Thomas G. Kurtz, Lea Popovic, and Greg Rempala. Asymptotic analysis of multiscale approximations to reaction networks. Ann. Appl. Probab., 16(4):1925–1961, 2006. MR2288709

[3]     D. J. Daley and J. Gani. Epidemic modelling: an introduction, volume 15 of Cambridge Studies in Mathematical Biology. Cambridge University Press, Cambridge, 1999. MR1688203

[4]     R. W. R. Darling and J. R. Norris. Structure of large random hypergraphs. Ann. Appl. Probab., 15(1A):125–152, 2005. MR2115039

[5]     R. W. R. Darling and J. R. Norris. Cores and cycles in random hypergraphs. In preparation, 2008.

[6]     Stewart N. Ethier and Thomas G. Kurtz. Markov processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, 1986. MR838085

[7]     Bruce Hajek. Asymptotic analysis of an assignment problem arising in a distributed communications protocol. In Proc. of the 27th Conf. on Decision and Control, pages 1455–1459. IEEE Press, 1988.

[8]     Jean Jacod and Albert N. Shiryaev. Limit theorems for stochastic processes, volume 288 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 2003. MR1943877

[9]     Olav Kallenberg. Foundations of modern probability. Probability and its Applications (New York). Springer-Verlag, New York, second edition, 2002. MR1876169

[10]     Richard Karp and Michael Sipser. Maximum matchings in sparse random graphs. In 22nd Annual Symposium on Foundations of Computer Science, pages 364–375. IEEE Press, 1981.

[11]     Claude Kipnis and Claudio Landim. Scaling limits of interacting particle systems, volume 320 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999. MR1707314

[12]     Thomas G. Kurtz. Approximation of population processes, volume 36 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1981. MR610982

[13]     Harold J. Kushner and G. George Yin. Stochastic approximation and recursive algorithms and applications. Springer, New York, 2003. MR1993642

[14]     Malwina J. Luczak and James Norris. Strong approximation for the supermarket model. Ann. Appl. Probab., 15(3):2038–2061, 2005. MR2152252

[15]     Brendan D. McKay. Asymptotics for 0-1 matrices with prescribed line sums. In Enumeration and design (Waterloo, Ont., 1982), pages 225–238. Academic Press, Toronto, ON, 1984. MR0782316

[16]     Michael Mitzenmacher. Studying balanced allocations with differential equations. Combin. Probab. Comput., 8(5):473–482, 1999. MR1731982

[17]     Michael Molloy. Cores in random hypergraphs and Boolean formulas. Random Structures Algorithms, 27(1):124–135, 2005. MR2150018

[18]     RĂ©mi Monasson and Guilhelm Semerjian. Relaxation and metastability in a local search procedure for the random satisfiability problem. Physical Review E, 67, 2003.

[19]     Boris Pittel, Joel Spencer, and Nicholas Wormald. Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B, 67(1):111–151, 1996. MR1385386

[20]     Oliver Riordan. The k-core and branching processes. Combin. Probab. Comput., 17:111–136, 2008. MR2376426

[21]     Adam Shwartz and Alan Weiss. Large deviations for performance analysis. Stochastic Modeling Series. Chapman & Hall, London, 1995. Queues, communications, and computing, With an appendix by Robert J. Vanderbei. MR1335456

[22]     H. F. Trotter. Approximation of semi-groups of operators. Pacific Journal of Mathematics, 8:887–919, 1958. MR0103420

[23]     Amanda G. Turner. Convergence of Markov processes near saddle fixed points. Ann. Probab., 35(3):1141–1171, 2007. MR2319718

[24]     Nicholas C. Wormald. Differential equations for random processes and random graphs. Ann. Appl. Probab., 5(4):1217–1235, 1995. MR1384372




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787