Bibliography
[1] D. Aldous. Some inequalities for reversible Markov chains. J. London Math.
Soc., 25(2):561–576, 1982.
[2] D. Aldous. A random walk construction of uniform spanning trees and uni-
form labelled trees. SIAM J. Discrete Math., 3(4):450–465, 1990.
[3] D.J. Aldous and P. Diaconis. Strong uniform times and finite random walks.
Adv. in Appl. Math., 8:69–97, 1987.
[4] S. Asmussen, P. W. Glynn, and J. Pitman. Discretization error in simulation of
one-dimensional reflecting Brownian motion. Ann. Appl. Probab., 5(4):875–
896, 1995.
[5] K. K. Berthelsen and J. Møller. Likelihood and non-parametric Bayesian
MCMC inference for spatial point processes based on perfect simulation and
path sampling. Scand. J. Stat., 30:549–564, 2003.
[6] K. K. Berthelsen and J. Møller. Non-parametric Bayesian inference for inho-
mogeneous Markov point processes. Aust.N.Z.J.Stat., 50:257–272, 2008.
[7] J. Bertoin and J. Pitman. Path transofrmations connecting Brownian bridge,
excursion and meander. Bull. Sci. Math., 118(2):147–166, 1994.
[8] J. Besag. Spa tial interaction and the statistical analysis of lattice systems (with
discussion). J. R. Statist. Soc. Ser. B Stat. Methodol., 36:192–236, 1974.
[9] J. Besag. On the statistical analysis of dirty pictures. J. R. Statist. Soc. Ser. B
Stat. Methodol., 48:259–302, 1986.
[10] A. Beskos, O. Papaspiliopoulos, and G. O. Roberts. A factorisation of diffu-
sion measure and finite sample path constructions. Methodol. Comput. Appl.
Probab., 10:85–104, 2008.
[11] A. Beskos, O. Papspiliopoulous, and G. O. Roberts. Retrospective exact sim-
ulation of diffusion sample paths with applications. Bernoulli, 12(6):1077–
1098, 2006.
[12] I. Bez´akov´a, D. Stefankovic, V. V. Vazirani, and E. Vigoda. Accelerating simu-
lated annealing for the permanent and combinatorial counting problems. SIAM
J. Comput., 37(5):1429–1454, 2008.
[13] L. M. Bregman. Some properties of nonnegative matrices and their perma-
nents. Soviet. Math. Dokl., 14(4):945–949, 1973.
[14] L.A. Breyer an d G. O. Roberts. Catalytic perfect simulation. Methodology
and Computing in Applied Probability, 3(2):161–177, 2001.
219
220 BIBLIOGRAPHY
[15] A. Brix and W.S. Kendall. Simulation of cluster point processes without edge
effects. Adv. in Appl. Probab., 34:267–280, 2002.
[16] A. Broder. Generating random spanning trees. In Proc. 30th Sympos. on
Foundations of Computer Science, pages 442–447, 1989.
[17] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in
Markov chains. In Proc. 38th Sympos. on Foundations of Computer Science,
pages 223–231, 1997.
[18] J. Bucklew. Introduction to Rare Event Simulation. Springer, New York, 2004.
[19] Z. A. Burq and O.D. Jones. Simulation of Brownian motion at first-passage
times. Math. Comput. Simulation, 77:64–81, 2008.
[20] Sergio Caracciolo, Enrico Rinaldi, and Andrea Sportiello. Exact sampling of
corrugated surfaces. J. Stat. Mech. Theory Exp., Feb 2009.
[21] D.S. Carter and P.M. Prenter. Exponential spaces and counting p rocesses. Z.
Wahrsheinlichkeitsth, 21:1–19, 1972.
[22] N. Ch en and Z. Huang. Localizatio n and exact simulation of Brownian
motion-driven stochastic differential equations. Math. Oper. Res., 38(3):591–
616, 2013.
[23] H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis
based on the sum of observations. Ann. of Math. Stat., 23:493–509, 1952.
[24] F. Chung. Spanning treees in subgraphs of lattices. Contemp. Math., 245:201–
219, 1999.
[25] H. Cohn, R. Pemantle, and J. Propp. Generating a random sink-free orientation
in quadratic time. Electron. J. Combin., 9(1), 2002.
[26] P. Dagum, R. Karp, M. Luby, and S. Ross. An optimal algorithm for Monte
Carlo estimation. Siam. J. Comput., 29(5):1484–1496, 2000.
[27] L. Devroye. Simulating perpetuities. Methodol. Comput. Appl. Probab.,
3(1):97–115, 2001.
[28] P. L. Dobruschin. The description of a random field by means of conditional
probabilities and conditions of its regularity. Theor. Prob. Appl., 13(2):197–
224, 1968.
[29] W. Doeblin. Expos´edelath´eorie des chains simples constantes de Markov
`a un nombre fini d’´etats. Rev. Math. de l’Union Interbalkanique, 2:77–105,
1933.
[30] P. Donnelly and D. Welsh. The antivoter problem: random 2-colourings of
graphs. Graph Theory and Combinatorics, pages 133–144, 1984.
[31] R. Durrett. Probability: Theory and Examples, 4th edition. Cambridge Uni-
versity Press, 2010.
[32] M. Dyer and C. Greenhill. On Markov chains for independent sets. J. Algo-
rithms, 35(1):17–49, 2000.
[33] G. P. Egorychev. The solution of van der Waerden’s problem for permanents.
BIBLIOGRAPHY 221
Adv. in Math., 42:299–305, 1981.
[34] D. I. Falikman. Proof of the van der Waerden’s conjecture on the permanent
of a doubly stochastic matrix. Mat. Zametki, 29(6):931–938, 1981.
[35] J. A. Fill. An interruptible algorithm for perfect sampling via Markov chains.
Ann. Appl. Probab., 8:131–162, 1998.
[36] J. A. Fill and M. L. Huber. Perfect simulation of Vervaat perpetuities. Elec-
tron. J. Probab., 15:96–109, 2010.
[37] J. A. Fill, M. Machida, D. J. Murdoch, and J. S. Rosenthal. Extension of Fill’s
perfect rejection sampling algorithm to general chains. Random Structures
Algorithms, 17:290–316, 2000.
[38] G. S. Fishman. Monte Carlo: concepts, algorithms, and applications.
Springer-Verlag, New York, 1996.
[39] A.E. Gelfand and A.F.M. Smith. Sampling based approaches to calculating
marginal densities. J. Amer. Statist. Assoc., 85:398–409, 1990.
[40] A. Gelman and X. Meng. Simulating normalizing constants: From impor-
tance sampling to bridge sampling to path sampling. Stat. Sci., 13(2):163–185,
1998.
[41] A. Gibbs. Convergen ce in the Wasserstein metric for Markov chain Monte
Carlo algorithms with applications to image restoration. Stochastic Models,
20:473–492, 2004.
[42] I.V. Girsanov. On transforming a certain class o f stochastic processes by abso-
lutely continuous substitution of measures. Theory Probab. Appl., 5(3):285–
301, 1960.
[43] S.W. Guo and E. A. Thompson. Performing the exact test of Hardy-Weinberg
proportion for multiple alleles. Biometrics, 48:361–372, June 1992.
[44] O. H¨aggstr¨om and K. Nelander. On exact simulation from Markov random
fields using coupling from the past. Scand. J. Statist., 26(3):395–411, 1999.
[45] O. H¨aggstr¨om and J. E. Steif. Propp-Wilson algorithms and finitary codings
for high noise Markov random fields. Combin. Probab. Computing, 9:425–
439, 2000.
[46] O. H¨aggstr¨om, M.N.M. van Leishout, and J. Møller. Characterisation re-
sults and Markov chain Monte Carlo algorithms including exact simulatio n
for some spatial point processes. Bernoulli, 5:641–658, 1999.
[47] W. K. Hastings. Monte Carlo sampling methods using Markov chains and
their a pplications. Biometrika, 57:97–109, 1970.
[48] J. R. Hindley and J. P. Seldin. Lambda-Calculus and Combinators: An Intro-
duction (2nd edition). Cambridge University Press, Cambridge, 2008.
[49] C.R. Hoare. Find (algorithm 65). Comm. ACM, 4:321–322, 1961.
[50] M. Huber. Nearly optimal Bernoulli factories for linear functions. Combin.
Probab. Comput. arXiv:1308.1562. To appear.
222 BIBLIOGRAPHY
[51] M. Huber. Perfect sampling using bounding chains. Ann. Appl. Probab.,
14(2):734–753, 2004.
[52] M. Huber. Exact sampling from perfect matchings of dense regular bipartite
graphs. Algorithmica, 44:183–193, 2006.
[53] M. Huber. Fast perfect sampling from linear extensions. Discrete Mathemat-
ics, 306:420–428, 2006.
[54] M. Huber. Perfect simulatio n for image restoration. Stochastic Models,
23(3):475–487, 2007.
[55] M. Huber. Spatial birth-death swap chains. Bernoulli, 18(3):1031–1041, 2012.
[56] M. Huber. An unbiased estimate for the mean of a {0,1}random variable with
relative error distributions independent of the mean. 2013. arXiv:1309.5413.
Submitted.
[57] M. Huber. Near-linear time simulation of linear extensions of a height-2 poset
with bounded interaction. Chic. J. Theoret. Comput. Sci., 2014, 2014.
[58] M. Huber. Approximation algorithms for the normalizing constant of Gibbs
distributions. Ann. Appl. Probab., 51:92–105, 2015. arXiv:1206.2689.
[59] M. Huber, Y. Chen, I. Dinwoodie, A. Dobra, and M. Nicholas. Monte Carlo
algorithms for Hardy-Weinberg proportions. Biometrics, 62:49–53, Mar 2006.
[60] M. Huber and J. Law. Fast approximation of the permanent for very dense
problems. In Proc. of 19th ACM-SIAM Symp. on Discrete Alg., pages 681–
689, 2008.
[61] M. Huber and G. Reinert. The stationary distribution in the Antivoter model:
exact sampling and approximations. In Stein’s Method: Expository Lectures
and Applications, pages 79–94. IMS Lecture Notes 46, 2004.
[62] M. L. Huber. Exact sampling and approximate counting techniques. In Proc.
30th Sympos. on the Theory of Computing, pages 31–40, 1998.
[63] M. L. Huber. Exact sampling using Swendsen-Wang. In Proc. 10th Sympos.
on Discrete Algorithms, pages 921–922, 1999.
[64] M. L. Huber. Perfect Sampling with Bounding Chains. PhD thesis, Cornell
University, 1999.
[65] M. L. Huber. A faster method for sampling independent sets. In Proc. 11th
ACM-SIAM Sympos. o n Discrete Algorithms, pages 625–626, 2000.
[66] M. L. Huber. A bounding chain for Swendsen-Wang. Random Structures
Algorithms, 22(1):43–59, 2003.
[67] M. L. Huber and R. L. Wolpert. Likelihood-based inference for Mat´ern type-
III repulsive point processes. Adv. Appl. Prob., 41(4):958–977, 2009.
[68] A. Iserles. A first course in the numerical analysis of differential equations,
Second Ed ition. Cambridge University Press, Cambridge, 2008.
[69] K. It¯o. Stochastic integral. Proc. Imperial Acad. Tokyo, 20:519–524, 1944.
[70] M. Jerrum and A. Sinclair. Polynomial-time approximation algorithms for the
BIBLIOGRAPHY 223
Ising model. SIAM J. Comput., 22:1087–1116, 1993.
[71] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation
algorithm for the p ermanent of a matrix with non-negative entries. In Proc.
33rd ACM Sympos. on Theory of Computing, pages 712–721, 2001.
[72] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial
structures from a uniform distribution. Theoret. Comput. Sci., 43:169–188,
1986.
[73] M.R. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation
algorithm for the permanent of a matrix with nonnegative entries. J. of the
ACM, 51(4):671–697, 2004.
[74] V. E. Johnson. Studying convergence of Markov chain Monte Carlo algo-
rithms using coupled sample paths. J. Amer. Statist. Assoc., 91:154–166, 1996.
[75] B. Kalantari and L. Khachiyan. On the complexity of nonnegative-matrix
scaling. Linear Algebra Appl., 240:87–103, 1996.
[76] S. Karlin and H.M. Taylor. A Second Course in Stochastic Processes. Aca-
demic Press, New York, 1981.
[77] A. Karzanov and L. Khachiyan. On the conductance of order Markov chains.
Order, 8(1):7–15, 1991.
[78] P.W. Kasteleyn. The statistics of dimers on a lattice, I., the number of dimer
arrangements on a quadratic lattice. Physica, 27:1664–1672, 1961.
[79] P.W. Kasteleyn. Dimer statistics and phase transitions. J. Math. Phys., 4:287,
1963.
[80] P.W. Kasteleyn. Graph theory and crystal Physics. In F. Harray, editor, Graph
Theory and Theoretical Physics, pages 43–110. Academic Press, London,
1967.
[81] W. S. Kendall. Perfect simulation for the area-interaction point process. In
Probability To wards 2000, volume 128 of Lecture notes in Statistics, pages
218–234. Springer-Verlag, 1998.
[82] W. S. Kendall and J. Møller. Perfect simulation u sing dominating processes on
ordered spaces, with application to locally stable point processes. Adv. Appl.
Prob., 32:844–865, 2000.
[83] P. E. Kloeden and E. Platen. Numerical Solution of Stochastic Differential
Equations. Springer-Verlag, Berlin Heidelberg New York, 1992.
[84] G. F. Lawler. Introduction to stochastic processes. Chapman & Hall/CRC,
1995.
[85] T. Lindvall. Lectures on the Coupling Method. Wiley, NY, 1992.
[86] N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic strongly
polynomial algorithm for matrix scaling and approximate permanents. Com-
binatorica, 20(4):545–568, 2000.
[87] E. Lubetzky and A. Sly. Information percolation f or the Ising model: cutoff in
three dimensions up to criticality. Technical report, 2014. Preprint.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.