Asymptotic properties of some underdiagonal walks generation algorithms

AbstractUsing classical properties of Random walks and Brownian motion, we derive the asymptotic distribution of some characteristics of an algorithm proposed by Barcucci et al. (1995) to generate underdiagonal walks of size n. The main parameters of interest are the cost of the algorithm (in terms of calls to a random generator), the height of the walk at its last step and the maximum of the walk. We obtain various forms of probability generating functions, Laplace transforms of densities, continuous distribution functions, asymptotic densities and discrete stationary distributions