Fast perfect simulation of Vervaat perpetuities

This work presents a new method of simulating exactly from a distribution known as a Vervaat perpetuity. This type of perpetuity is indexed by a parameter β. The new method has a bound on the expected run time which is polynomial in β (as β goes to infinity). This is much faster than the previously best known bound due to an earlier method of Fill and the second author, which ran in expected time exp(βln(β)+Θ(β)) as β→∞. The earlier method utilized dominated coupling from the past to place bounds on a stochastic process for perpetuities from above. By extending to an update function that changes based on the dominating process, 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 expected time O(βln(β)) as β→∞.