×

Multiprocess parallel antithetic coupling for backward and forward Markov chain Monte Carlo. (English) Zbl 1068.62090

Summary: Antithetic coupling is a general stratification strategy for reducing Monte Carlo variance without increasing the simulation size. The use of the antithetic principle in the Monte Carlo literature typically employs two strata via antithetic quantile coupling. We demonstrate here that further stratification, obtained by using \(k>2\) (e.g., \(k=3-10)\) antithetically coupled variates, can offer substantial additional gain in Monte Carlo efficiency, in terms of both variance and bias. The reason for reduced bias is that antithetically coupled chains can provide a more dispersed search of the state space than multiple independent chains. The emerging area of perfect simulation provides a perfect setting for implementing the \(k\)-process parallel antithetic coupling for MCMC because, without antithetic coupling, this class of methods delivers genuine independent draws.
Furthermore, antithetic backward coupling provides a very convenient theoretical tool for investigating antithetic forward coupling. However, the generation of \(k>2\) antithetic variates that are negatively associated, that is, they preserve negative correlation under monotone transformations, and extremely antithetic, that is, they are as negatively correlated as possible, is more complicated compared to the case with \(k=2\). We establish a theoretical framework for investigating such issues. Among the generating methods that we compare, Latin hypercube sampling and its iterative extension appear to be general-purpose choices, making another direct link between Monte Carlo and quasi Monte Carlo.

MSC:

62M05 Markov processes: estimation; hidden Markov models
65C40 Numerical analysis or methods applied to Markov chains
62F15 Bayesian inference
65C60 Computational problems in statistics (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albert, J. and Chib, S. (1993). Bayesian analysis of binary and polychotomous response data. J. Amer. Statist. Assoc. 88 669–679. JSTOR: · Zbl 0774.62031 · doi:10.2307/2290350
[2] Arjas, E. and Gasbarra, D. (1996). Bayesian inference of survival probabilities, under stochastic ordering constraints. J. Amer. Statist. Assoc. 91 1101–1109. JSTOR: · Zbl 0880.62024 · doi:10.2307/2291729
[3] Arvidsen, N. I. and Johnsson, T. (1982). Variance reduction through negative correlation—a simulation study. J. Statist. Comput. Simulation 15 119–127.
[4] Bailey, B. J. R. (1981). Alternatives to Hastings’ approximation to the inverse of the normal cumulative distribution function. Appl. Statist. 30 275–276. JSTOR: · doi:10.2307/2346351
[5] Billingsley, P. (1986). Probability and Measure , 2nd ed. Wiley, New York. · Zbl 0649.60001
[6] Bondesson, L. (1983). Problem 128. Statist. Neerlandica 37 149.
[7] Borel, E. (1924). Traité du Calcul des Probabilités et de ses Applications . Gauthier-Villars, Paris. · JFM 50.0348.03
[8] Casella, G., Lavine, M. and Robert, C. P. (2001). Explaining the perfect sampler. Amer. Statist. 55 299–305. JSTOR: · doi:10.1198/000313001753272240
[9] Casella, G., Mengersen, K. L., Robert, C. P. and Titterington, D. M. (2002). Perfect samplers for mixtures of distributions. J. R. Stat. Soc. Ser. B Stat. Methodol . 64 777–790. JSTOR: · Zbl 1067.62028 · doi:10.1111/1467-9868.00360
[10] Craiu, R. V. (2001). Multivalent framework for approximate and exact sampling and resampling. Ph.D. dissertation, Univ. Chicago.
[11] Craiu, R. V. (2004). Antithetic acceleration of the multiple-try Metropolis. Technical Report 0407, Dept. Statistics, Univ. Toronto.
[12] Craiu, R. V. and Meng, X.-L. (2001). Chance and fractals. Chance 14 (2) 47–52.
[13] Craiu, R. V. and Meng, X.-L. (2002). Multi-process parallel antithetic coupling for backward and forward MCMC. Technical Report 0205, Dept. Statistics, Univ. Toronto.
[14] Damien, P., Wakefield, J. and Walker, S. (1999). Gibbs sampling for Bayesian non-conjugate and hierarchical models by using auxiliary variables. J. R. Stat. Soc. Ser. B Stat. Methodol. 61 331–344. JSTOR: · Zbl 0913.62028 · doi:10.1111/1467-9868.00179
[15] Esary, J. D., Proschan, F. and Walkup, D. W. (1967). Association of random variables, with applications. Ann. Math. Statist. 38 1466–1474. · Zbl 0183.21502 · doi:10.1214/aoms/1177698701
[16] Fill, J. A. (1998). An interruptible algorithm for perfect sampling via Markov chains. Ann. Appl. Probab. 8 131–162. · Zbl 0939.60084 · doi:10.1214/aoap/1027961037
[17] Fill, J. A., Machida, M., Murdoch, D. J. and Rosenthal, J. S. (2000). Extension of Fill’s perfect rejection sampling algorithm to general chains. Random Structures Algorithms 17 229–316. · Zbl 1122.60310 · doi:10.1002/1098-2418(200010/12)17:3/4<290::AID-RSA6>3.0.CO;2-Q
[18] Fishman, G. S. (1972). Variance reduction in simulation studies. J. Stat. Comput. Simul. 1 173–182. · Zbl 0249.62085 · doi:10.1080/00949657208810012
[19] Foss, S. G. and Tweedie, R. L. (1998). Perfect simulation and backward coupling. Comm. Statist. Stochastic Models 14 187–203. · Zbl 0934.60088 · doi:10.1080/15326349808807466
[20] Fréchet, M. (1951). Sur les tableaux de corrélation dont les marges sont données. Ann. Univ. Lyon. Sect. A ( 3 ) 14 53–77. · Zbl 0045.22905
[21] Frigessi, A., Gåsemyr, J. and Rue, H. (2000). Antithetic coupling of two Gibbs sampler chains. Ann. Statist. 28 1128–1149. · Zbl 1105.65303 · doi:10.1214/aos/1015956710
[22] Gelfand, A. E., Smith, A. F. M. and Lee, T.-M. (1992). Bayesian analysis of constrained parameter and truncated data problems using Gibbs sampling. J. Amer. Statist. Assoc. 87 523–532. JSTOR: · doi:10.2307/2290286
[23] Gelman, A. and Rubin, D. B. (1992). Inference from iterative simulation using multiple sequences (with discussion). Statist. Sci. 7 457–511. · Zbl 0767.62021
[24] Gentle, J. (1998). Random Number Generation and Monte Carlo Methods. Springer, New York. · Zbl 0972.65003
[25] Gerow, K. and Holbrook, J. (1996). Statistical sampling and fractal distributions. Math. Intelligencer 18 (2) 12–22. · Zbl 0879.60032 · doi:10.1007/BF03027288
[26] Häggström, O. and Nelander, K. (1998). Exact sampling from anti-monotone systems. Statist. Neerlandica 52 360–380. · Zbl 0948.60069 · doi:10.1111/1467-9574.00090
[27] Hammersley, J. M. and Handscomb, D. C. (1965). Monte Carlo Methods . Methuen, London. · Zbl 0121.35503
[28] Hammersley, J. M. and Morton, K. V. (1956). A new Monte Carlo technique: Antithetic variates. Proc. Cambridge Philos. Soc. 52 449–475. · Zbl 0071.35404 · doi:10.1017/S0305004100031455
[29] Helton, J. C. and Davis, F. J. (2003). Latin hypercube sampling and the propagation of uncertainty in analyses of complex systems. Reliability Engineering and System Safety 81 23–69.
[30] Hobert, J. P., Robert, C. P. and Titterington, D. M. (1999). On perfect simulation for some mixtures of distributions. Statist. Comput. 9 287–298.
[31] Hoeffding, W. (1940). Masstabinvariante Korrelationtheorie. Schriften des Mathematischen Instituts und des Instituts für Angewandte Mathematik der Universitat Berlin 5 181–233. · Zbl 0024.05602
[32] Iman, R. L. (1999). Latin hypercube sampling. Encyclopedia of Statistical Sciences Update 3 408–411. Wiley, New York.
[33] Joag-Dev, K. and Proschan, F. (1983). Negative association of random variables, with applications. Ann. Statist. 11 286–295. JSTOR: · Zbl 0508.62041 · doi:10.1214/aos/1176346079
[34] Joe, H. (1997). Multivariate Models and Dependence Concepts . Chapman and Hall, London. · Zbl 0990.62517
[35] Kendall, W. S. (1998). Perfect simulation for the area-interaction point process. Probability Towards 2000. Lecture Notes in Statist. 128 218–234. Springer, New York. · Zbl 1045.60503
[36] Kennedy, W. J. and Gentle, J. E. (1980). Statistical Computing . Dekker, New York. · Zbl 0435.62003
[37] Kish, L. (1965). Survey Sampling . Wiley, New York. · Zbl 0151.23403
[38] Lancaster, H. O. (1957). Some properties of the bivariate normal distribution considered in the form of a contingency table. Biometrika 44 289–292. · Zbl 0082.35105 · doi:10.1093/biomet/44.1-2.289
[39] Lehmann, E. L. (1966). Some concepts of dependence. Ann. Math. Statist. 37 1137–1153. · Zbl 0146.40601 · doi:10.1214/aoms/1177699260
[40] Lew, R. A. (1981). An approximation to the cumulative normal distribution with simple coefficients. Appl. Statist. 30 299–301. JSTOR: · doi:10.2307/2346355
[41] Loh, W.-L. (1996). On Latin hypercube sampling. Ann. Statist. 24 2058–2080. · Zbl 0867.62005 · doi:10.1214/aos/1069362310
[42] McKay, M. D., Beckman, R. J. and Conover, W. J. (1979). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21 239–245. JSTOR: · Zbl 0415.62011 · doi:10.2307/1268522
[43] Meng, X.-L. (2000). Towards a more general Propp–Wilson algorithm: Multistage backward coupling. In Monte Carlo Methods (N. Madras, ed.) 85–93. Amer. Math. Soc., Providence, RI. · Zbl 0965.65008
[44] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, London. · Zbl 0925.60001
[45] Møller, J. (1999). Perfect simulation of conditionally specified models. J. R. Stat. Soc. Ser. B Stat. Methodol. 61 251–264. JSTOR: · Zbl 0937.60035 · doi:10.1111/1467-9868.00175
[46] Møller, J. and Nicholls, G. K. (1999). Perfect simulation for sample-based inference. Preprint, Dept. Mathematical Statistics, Chalmers Institute of Technology.
[47] Moran, P. A. P. (1967). Testing for correlation between non-negative variates. Biometrika 54 385–394. JSTOR: · Zbl 0166.15101 · doi:10.1093/biomet/54.3-4.385
[48] Murdoch, D. J. (2000). Exact sampling for Bayesian inference: Unbounded state spaces. In Monte Carlo Methods (N. Madras, ed.) 111–121. Amer. Math. Soc., Providence, RI. · Zbl 0966.65009
[49] Murdoch, D. J. and Green, P. J. (1998). Exact sampling from a continuous state space. Scand. J. Statist. 25 483–502. · Zbl 0921.62020 · doi:10.1111/1467-9469.00116
[50] Murdoch, D. J. and Meng, X.-L. (2001). Towards perfect sampling for Bayesian mixture priors. In Bayesian Methods, with Applications to Science, Policy and Official Statistics (E. George, ed.) 381–390. Eurostat.
[51] Neal, R. M. (2003). Slice sampling (with discussion). Ann. Statist. 31 705–767. · Zbl 1051.65007 · doi:10.1214/aos/1056562461
[52] Owen, A. B. (1992). A central limit theorem for Latin hypercube sampling. J. Roy. Statist. Soc. Ser. B 54 541–551. JSTOR: · Zbl 0776.62041
[53] Owen, A. B. (1997). Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34 1884–1910. JSTOR: · Zbl 0890.65023 · doi:10.1137/S0036142994277468
[54] Owen, A. B. (2002). Quasi Monte Carlo. Presented at the First Cape Cod Workshop on Monte Carlo Methods. · Zbl 0942.65024
[55] Page, E. S. (1965). On Monte Carlo methods in congestion problems. II. Simulation of queuing systems. Oper. Res. 13 300–305. · Zbl 0127.10005 · doi:10.1287/opre.13.2.291
[56] Pemantle, R. (2000). Towards a theory of negative dependence. J. Math. Phys. 41 1371–1390. · Zbl 1052.62518 · doi:10.1063/1.533200
[57] Philippe, A. and Robert, C. (2003). Perfect simulation of positive Gaussian distributions. Statist. Comput. 13 179–186. · doi:10.1023/A:1023264710933
[58] 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
[59] Rubinstein, R. Y. and Samorodnitsky, G. (1985). Variance reduction by the use of common and antithetic random variables. J. Statist. Comput. Simulation 22 161–180. · Zbl 0581.62100 · doi:10.1080/00949658508810841
[60] Rüschendorf, L. and Uckelmann, L. (2000). Variance minimization and random variables with constant sum. Technical report, Institüt für Mathematische Stochastik, Univ. Freiburg. · Zbl 1142.62316
[61] Simon, G. (1976). Computer simulation swindles, with applications to estimates of location and dispersion. Appl. Statist. 25 266–274. JSTOR: · doi:10.2307/2347234
[62] Snijders, T. A. B. (1984). Antithetic variates for Monte Carlo estimation of probabilities. Statist. Neerlandica 38 55–73. · Zbl 0552.65097 · doi:10.1111/j.1467-9574.1984.tb01099.x
[63] Stein, M. (1987). Large sample properties of simulations using Latin hypercube sampling. Technometrics 29 143–151. [Corrigendum Technometrics 32 (1990) 367.] JSTOR: · Zbl 0627.62010 · doi:10.2307/1269769
[64] Thorisson, H. (2000). Coupling, Stationarity, and Regeneration . Springer, New York. · Zbl 0949.60007
[65] van Dyk, D. and Meng, X.-L. (2001). The art of data augmentation (with discussion). J. Comput. Graph. Statist. 10 1–111. JSTOR: · Zbl 04565162 · doi:10.1198/10618600152418584
[66] Wilson, D. B. (1998). Annotated bibliography of perfectly random sampling with Markov chains. In Microsurveys in Discrete Probability (D. Aldous and J. Propp, eds.) 209–220. Amer. Math. Soc., Providence, RI. Updated versions appear at http://dimacs.rutgers.edu/ dbwilson/exact. · Zbl 0905.60039
[67] Wilson, D. B. (2000a). How to couple from the past using a read-once source of randomness. Random Structures Algorithms 16 85–113. · Zbl 0952.60072 · doi:10.1002/(SICI)1098-2418(200001)16:1<85::AID-RSA6>3.0.CO;2-H
[68] Wilson, D. B. (2000b). Layered multishift coupling for use in perfect sampling algorithms (with a primer on CFTP). In Monte Carlo Methods (N. Madras, ed.) 143–176. Amer. Math. Soc., Providence, RI. · Zbl 0965.65009
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.