| Above is an Java applet implemented as a proof-of-concept for researches
on random uni-dimensional walks with two kind of steps (+1,+a) and (+1,-b), done in
collaboration with M. Bousquet-Mélou. One of our main goal was to design efficient algorithms for
the uniform random generation of culminating paths, a culminating paths being a walk ending at its
highest position ever. That led us to consider meanders, a.k.a. positive walks, for which
we also derived efficient random generation algorithms. The efficiency of some of these algorithms
is highly dependent on the drift D:=a-b of the walks. Most of these algorithms are available in the
implementation below:
- Binary words: Unconstrained walks, obtained by flipping an unbiased coin as many times as is necessary.
- Meanders using an anticipated rejection: Barcucci et al had shown that meanders
could be generated in linear time when D>=0, by flipping coins until the positivity condition is failed, in which case the walk
is regenerated from scratch, or the desired size of the walk is attained. However, this algorithm is known to be
exponential when D<0.
- Meanders using recursive step-by-step: The positive walks can be generated using a step-by-step approach,
by picking at each step a up or down step according to precomputed probabilities. This yields a quasi-linear generation
algorithm after a quadratic precomputation. However, the memory used by this method is roughly
cubic, which may lead the Applet to crash for >200 sizes.
- Culminating paths using an anticipated rejection: As for meanders, we have shown, using a combinatorial argument,
that the culminating can be generated by flipping coins in a linear-time for D>0. For D=0, the expected time-complexity has
turned out to require 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 can be transposed to the case of
culminating paths. The cost of a generation remains roughly linear, but the precomputation of the probabilities now requires
a O(n4) memory, which may become an issue for sizes >100.
As the positivity and final-record (culminance) conditions filtering
roles, and because the former has an impact mostly on the beginning of the walk, whereas the latter constrains its ending,
it is tempting to draw walks that are positive on their first half, and final-record on their second, and perform rejection
until a culminating is found. After pointing out that a final-record paths is a positive path, read in reverse, it is
obvious that the generation of the rejection superset will rely on a strategy for generating meanders, thus the two
following implementations:
- Culminating paths through mirror-images (Recursive): The recursive approach is used to generate meanders,
from which the mirror-images, culminating candidates, are built. The memory requirement is in O(n3).
- 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 linear for D>=0, and
exponential otherwise.
|