Perfect Simulation of Vervaat Perpetuities

James Allen Fill (The Johns Hopkins University)
Mark L Huber (Claremont McKenna College)

Abstract


We use coupling into and from the past to sample perfectly in a simple and provably fast fashion from the Vervaat family of perpetuities. The family includes the Dickman distribution, which arises both in number theory and in the analysis of the Quickselect algorithm (the motivation for our work).

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 96-109

Publication Date: January 21, 2010

DOI: 10.1214/EJP.v15-734

References

  1. Devroye, Luc. Simulating perpetuities. Methodol. Comput. Appl. Probab. 3 (2001), no. 1, 97–115. MR1833738 (2003a:65008)
  2. Devroye, L.; Fawzi, O. Simulating the Dickman distribution. Statistics and Probability Letters 80 (2010), 242–247.
  3. Durrett, Richard. Probability. Theory and examples. The Wadsworth & Brooks/Cole Statistics/Probability Series. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. x+453 pp. ISBN: 0-534-13206-5 MR1068527 (91m:60002)
  4. Hoare, C. R. Find (algorithm 65). Comm. ACM 4 (1961), 321–322.
  5. Huber, M.; Wolpert, R. L. Likelihood-based inference for Matérn Type III repulsive point processes. Adv. Appl. Prob., to appear.
  6. Hwang, Hsien-Kuei; Tsai, Tsung-Hsi. Quickselect and the Dickman function. Combin. Probab. Comput. 11 (2002), no. 4, 353–371. MR1918722 (2003g:68031)
  7. Kendall, W. S. Perfect simulation for the area-interaction point process. In Proceedings of the Symposium on Probabiity Towards the Year 2000 (1995).
  8. Kendall, Wilfrid S.; Møller, Jesper. Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. in Appl. Probab. 32 (2000), no. 3, 844–865. MR1788098 (2001h:62176)
  9. Kendall, W. S.; Thönnes, E.. Random walk CFTP. Technical report, Department of Statistics, University of Warwick (2004).
  10. Lawler, Gregory F. Introduction to stochastic processes. Chapman & Hall Probability Series. Chapman & Hall, New York, 1995. x+176 pp. ISBN: 0-412-99511-5 MR1372946 (97a:60001)
  11. Lindvall, Torgny. Lectures on the coupling method. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xiv+257 pp. ISBN: 0-471-54025-0 MR1180522 (94c:60002)
  12. Mahmoud, Hosam M.; Modarres, Reza; Smythe, Robert T. Analysis of QUICKSELECT: an algorithm for order statistics. RAIRO Inform. Théor. Appl. 29 (1995), no. 4, 255–276. MR1359052 (96h:68040)
  13. Murdoch, D. J.; Green, P. J. Exact sampling from a continuous state space. Scand. J. Statist. 25 (1998), no. 3, 483–502. MR1650023
  14. Propp, James Gary; Wilson, David Bruce. Exact sampling with coupled Markov chains and applications to statistical mechanics. Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995). Random Structures Algorithms 9 (1996), no. 1-2, 223–252. MR1611693 (99k:60176)
  15. Vervaat, Wim. On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables. Adv. in Appl. Probab. 11 (1979), no. 4, 750–783. MR0544194 (81b:60064)
  16. Wilson, David Bruce. Layered multishift coupling for use in perfect sampling algorithms (with a primer on CFTP). Monte Carlo methods (Toronto, ON, 1998), 143–179, Fields Inst. Commun., 26, Amer. Math. Soc., Providence, RI, 2000. MR1772313 (2001h:65014)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.