Random generation of uni-dimensional walks (Culminating paths)

Above is an Java applet implemented as a proof-of-concept for researches on random uni-dimensional walks (See the article published in DMTCS) with two kind of steps (+1,+a) (up step) and (+1,-b) (down step), done in collaboration with Mireille Bousquet-Mélou. Our main goal was to design efficient algorithms for the uniform random generation of culminating paths of length n, i.e. walks that remain positive (positivity) and reaching their maximal ordinate (not known a priori) at their last step (final record condition).

This led us to revisit the random generation of meanders, a.k.a. positive walks, for which we also derived efficient random generation algorithms. The efficiency of some of these algorithms turned out to be highly dependent on a drift parameter D:=a-b. Most of these algorithms are available in the implementation above:

• Binary words: Unconstrained walks, simply obtained by flipping a coin.
• Meanders using an anticipated rejection: Barcucci et al showed that meanders can be generated in linear time when D>=0 by choosing up and down steps with equal probability, until the walk becomes negative (in which case the walk is regenerated from scratch) or the desired size of the walk is attained. Despite its good behavior (and embarrassingly simple implementation), this algorithm was shown to be exponential when D<0.
• Meanders using recursive step-by-step: The positive walks can be generated using a step-by-step approach, picking at each step an up or down step according to carefully precomputed probabilities (thus ensuring the uniformity of the approach). This yields a quasi-linear generation algorithm after a quadratic precomputation. However, the memory used by this implementation is roughly quadratic, leading the Applet to crash for lengths greater than 200.
• Culminating paths using an anticipated rejection: Using a combinatorial argument, we have shown that culminating path can also be generated by a combination of coin-flipping/rejection in linear-time for D>0. For D=0, the expected time-complexity has requires an extra square-root factor on the size. When D<0, the expected time-complexity is still exponential.
• Culminating paths using recursive step-by-step: The step-by-step generation (aka recursive method) can be used in the case of culminating paths. The cost of a generation remains roughly linear, but the precomputation of the probabilities now requires a O(n⁴) memory, which may become an issue for lengths greater than 100.

We observed that the positivity and final-record conditions play symmetrical filtering roles (exchanged by rotating a culminating path by 180 degrees). Furthermore, the former has an impact mostly on the beginning of the walk, while the latter constrains its ending. Therefore it was tempting to draw walks that are positive on their first half, and culminating on their second, and perform rejection until a culminating is found. After pointing out that any final-record admissible path becomes a positive path upon reading it backward (and vice-versa), we proposed two new strategies, based on piecing together respectively positive and final-record paths:

• Culminating paths through mirror-images (Recursive): A recursive approach is used to generate meanders, from which the mirror-images, culminating candidates, are built. The memory requirement is then in O(n³).
• Culminating paths through mirror-images (Rejection): An anticipated rejection strategy is used to generate meanders, from which the mirror-images, culminating candidates, are built. This type of generation is now linear in n for D&ge 0, and exponential otherwise.