Culminating paths
Mireille Bousquet-Mélou, Yann Ponty
Abstract
Let a and b be two positive integers. A
culminating
path is a path of ℤ2 that starts from
(0,0),
consists of steps (1,a) and (1,-b), stays
above
the x-axis and ends at the highest ordinate it ever
reaches.
These paths were first encountered in bioinformatics, in the analysis
of
similarity search algorithms. They are also related to certain models
of
Lorentzian gravity in theoretical physics. We first show that the
language
on a two letter alphabet that naturally encodes culminating paths is
not
context-free. Then, we focus on the enumeration of culminating paths.
A
step by step approach, combined with the kernel method, provides a
closed
form expression for the generating function of culminating paths ending at a
(generic)
height k. In the case a = b, we derive from
this
expression the asymptotic behaviour of the number of culminating paths
of
length n. When a > b, we obtain the
asymptotic
behaviour by a simpler argument. When a < b, we only
determine
the exponential growth of the number of culminating paths. Finally, we
study
the uniform random generation of culminating paths via various
methods.
The rejection approach, coupled with a symmetry argument, gives an
algorithm
that is linear when a ≥ b, with no precomputation stage
nor
non-linear storage required. The choice of the best algorithm is not
as
clear when a < b. An elementary recursive approach
yields
a linear algorithm after a precomputation stage involving O(n3)
arithmetic operations, but we also present some alternatives that may
be more efficient in practice.
Full Text: PDF PostScript