Fast Perfect Simulation of Vervaat Perpetutities

Abstract

This work presents a faster method of simulating exactly from a distribution known as a Vervaat perpetuity. A parameter of the Vervaat perpetuity is ${\hat{I}}^2\in (0,\infty )$. An earlier method for simulating from this distributon ran in time $O((2.23{\hat{I}}^2{)}^2).$ This earlier method utilized dominated coupling from the past that bounded a stochastic process for perpetuities from above. By extending to non-Markovian update functions, it is possible to create a new method that bounds the perpetuities from both above and below. This new approach is shown to run in $O({\hat{I}}^2\ln ({\hat{I}}^2))$ time.

14 pages, 1 figure