Exact Sampling of the Infinite Horizon Maximum of a Random Walk Over a Non-linear Boundary

Abstract

We present the first algorithm that samples ${\max }_{n\ge 0}\{S_n-n^{\alpha }\},$ where $S_n$ is a mean zero random walk, and $n^{\alpha }$ with $\alpha \in (1/2,1)$ defines a nonliner boundary. We show that our algorithm has finite expected running time. We also apply the algorithm to construct the first exact simulation method for the steady-state departure process of a $GI/GI/\infty$ queue where the service time distribution has infinite mean.