 |
|
|
| | | | | |
|
|
|
|
|
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: PDF
Pages: 96-109
Published on: January 21, 2010
|
Bibliography
-
Devroye, Luc. Simulating perpetuities. Methodol.
Comput. Appl. Probab. 3 (2001),
no. 1, 97–115.
MR1833738
(2003a:65008)
-
Devroye, L.; Fawzi, O. Simulating the
Dickman distribution. Statistics and Probability Letters 80
(2010), 242–247.
-
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)
-
Hoare, C. R. Find (algorithm 65). Comm.
ACM 4 (1961), 321–322.
-
Huber, M.; Wolpert, R.
L.
Likelihood-based inference for Matérn Type III repulsive
point processes.
Adv. Appl. Prob.,
to appear.
-
Hwang, Hsien-Kuei; Tsai, Tsung-Hsi.
Quickselect and the
Dickman function.
Combin. Probab. Comput. 11 (2002),
no.
4, 353–371.
MR1918722
(2003g:68031)
-
Kendall, W. S. Perfect simulation for the
area-interaction point process.
In Proceedings of the Symposium on
Probabiity Towards the Year 2000 (1995).
-
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)
-
Kendall, W. S.; Thönnes, E.. Random
walk CFTP. Technical report, Department
of Statistics, University of
Warwick (2004).
-
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)
-
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)
-
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)
-
Murdoch, D. J.; Green, P. J.
Exact sampling
from a continuous state space.
Scand. J. Statist. 25
(1998), no. 3, 483–502.
MR1650023
-
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)
-
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)
-
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)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context