×

zbMATH — the first resource for mathematics

Spatial birth-death swap chains. (English) Zbl 1254.60080
Author’s abstract: Markov chains have long been used for generating random variates from spatial point processes. Broadly speaking, these chains fall into two categories Metropolis-Hastings type chains running in discrete time and spatial birth-death chains running in continuous time. These birth-death chains only allow for the removal or addition of a point.
In this paper, it is shown that the addition of transitions, whereby a point is moved from one location to the other, can aid in shortening the mixing time of the chain. Here, the mixing time of the chain is analyzed through coupling, and the use of the swap moves allows for the analysis of a broader class of chains. Furthermore, these swap moves can be employed in perfect sampling algorithms via the dominated coupling from the past procedure of W. S. Kendall and J. Møller [Adv. Appl. Probab. 32, No. 3, 844–865 (2000; Zbl 1123.60309)]. This method can be applied to any pairwise interaction model with repulsion. In particular, an application to the Strauss process is developed in detail, and the swap chains are shown to be much faster than standard birth-death chains.

MSC:
60J22 Computational methods in Markov chains
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J27 Continuous-time Markov processes on discrete state spaces
65C40 Numerical analysis or methods applied to Markov chains
Software:
spatial
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Azéma, J., Kaplan-Duflo, M. and Revuz, D. (1967). Mesure invariante sur les classes récurrentes des processus de Markov. Z. Wahrsch. Verw. Gebiete 8 157-181. · Zbl 0178.20302 · doi:10.1007/BF00531519
[2] Baddeley, A.J. and van Lieshout, M.N.M. (1995). Area-interaction point processes. Ann. Inst. Statist. Math. 47 601-619. · Zbl 0848.60051 · doi:10.1007/BF01856536
[3] Berthelsen, K.K. and Møller, J. (2002). A primer on perfect simulation for spatial point processes. Bull. Braz. Math. Soc. ( N.S. ) 33 351-367. · Zbl 1042.60028 · doi:10.1007/s005740200019
[4] Carter, D.S. and Prenter, P.M. (1972). Exponential spaces and counting processes. Z. Wahrsch. Verw. Gebiete 21 1-19. · Zbl 0213.19301 · doi:10.1007/BF00535104
[5] Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23 493-507. · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[6] Clifford, P. and Nicholls, G. (1994). Comparison of birth-and-death and Metropolis-Hastings Markov chain Monte Carlo for the Strauss process. Unpublished manuscript.
[7] Dyer, M. and Greenhill, C. (2000). On Markov chains for independent sets. J. Algorithms 35 17-49. · Zbl 0961.05063 · doi:10.1006/jagm.1999.1071
[8] Feller, W. (1966). An Introduction to Probability Theory and Its Applications. Vol. II . New York: Wiley. · Zbl 0138.10207
[9] Geyer, C. (1999). Likelihood inference for spatial point processes. In Stochastic Geometry ( Toulouse , 1996). Monogr. Statist. Appl. Probab. 80 79-140. Boca Raton, FL: Chapman & Hall/CRC. · Zbl 0809.62089
[10] Häggström, O. and Steif, J.E. (2000). Propp-Wilson algorithms and finitary codings for high noise Markov random fields. Combin. Probab. Comput. 9 425-439. · Zbl 0973.60049 · doi:10.1017/S0963548300004363
[11] Häggström, O., van Lieshout, M.C.N.M. and Møller, J. (1999). Characterization results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes. Bernoulli 5 641-658. · Zbl 0981.65012 · doi:10.2307/3318694
[12] Harkness, R.D. and Isham, V. (1983). A bivariate spatial point pattern of ants’ nests. Appl. Stat. 32 293-303.
[13] Huber, M. (2000). A faster method for sampling independent sets. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms ( San Francisco , CA , 2000) 625-626. New York: ACM. · Zbl 0954.65005
[14] Huber, M. (2004). Perfect sampling using bounding chains. Ann. Appl. Probab. 14 734-753. · Zbl 1052.60057 · doi:10.1214/105051604000000080
[15] Illian, J., Penttinen, A., Stoyan, H. and Stoyan, D. (2008). Statistical Analysis and Modelling of Spatial Point Patterns . Chichester: Wiley. · Zbl 1197.62135 · doi:10.1002/9780470725160
[16] Kaspi, H. and Mandelbaum, A. (1994). On Harris recurrence in continuous time. Math. Oper. Res. 19 211-222. · Zbl 0803.60070 · doi:10.1287/moor.19.1.211
[17] Kelly, F.P. and Ripley, B.D. (1976). A note on Strauss’s model for clustering. Biometrika 63 357-360. · Zbl 0332.60034 · doi:10.1093/biomet/63.2.357
[18] Kendall, W.S. (1998). Perfect simulation for the area-interaction point process. In Probability Towards the Year 2000 (L. Accardi and C. C. Heyde, eds.) 218-234. Springer, New York. · Zbl 1045.60503 · doi:10.1007/978-1-4612-2224-8_13
[19] Kendall, W.S. and Møller, J. (2000). Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. in Appl. Probab. 32 844-865. · Zbl 1123.60309 · doi:10.1239/aap/1013540247 · euclid:aap/1013540247
[20] Møller, J. and Waagepetersen, R.P. (2004). Statistical Inference and Simulation for Spatial Point Processes. Monographs on Statistics and Applied Probability 100 . Boca Raton, FL: Chapman & Hall/CRC. · Zbl 1044.62101
[21] Preston, C.J. (1977). Spatial birth-and-death processes. Bull. Inst. Int. Stat. 46 371-391. · Zbl 0379.60082
[22] Propp, J.G. and Wilson, D.B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9 223-252. · Zbl 0859.60067 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O
[23] Ripley, B.D. (1977). Modelling spatial patterns (with discussion). J. Roy. Statist. Soc. Ser. B 39 172-212.
[24] Strauss, D.J. (1975). A model for clustering. Biometrika 62 467-475. · Zbl 0313.62044 · doi:10.1093/biomet/62.2.467
[25] Widom, B. and Rowlinson, J.S. (1970). A new model for the study of liquid-vapor phase transition. J. Chem. Phys. 52 1670-1684.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.