The random generation of underdiagonal walks

✍ Scribed by E. Barcucci; R. Pinzani; R. Sprugnoli

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 626 KB
• Volume: 139
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00121-x

✦ Synopsis

In this paper, we propose an algorithm for the random generation of underdiagonal walks. We consider the plane walks which are made up of different kinds of east, north-east and north steps and which start from the origin and remain under the main diagonal. The algorithm is very simple: it randomly generates plane walks and refuses the walks crossing the diagonal. We prove that the algorithm works in linear time with respect to the walks' length when the number of different kinds of east steps is greater than, or equal to, the number of different kinds of north steps. Finally, the results of our experiments are reported in order to support our theoretical results with empirical evidence.