Pierre Nicodeme, University Paris13
"Height of simple trees, discrete bridges and excursions"
We consider directed discrete walks progressing by one unit to the right at
each step; besides, at each step,
the vertical jumps belong to a finite subset of ℤ.
The walks begins at (0,0).
We use generating functions to encode the walks.
In the case of the
bridges, a method named kernel method allows to get an explicit form
of the generating function of bridges of bounded height. Next,
singularity analysis and computer algebra provide an asymptotic refinement of the
limit law of the height of a standard brownian bridge, which is the
The case of Dyck paths in bijection with the binary trees is
handled by continuous fractions; it leads to a Theta law for the
A more sophisticated analysis handles more general trees.
- Bridges terminates at altitude zero.
- Excursions terminates at altitude zero and remains above the