### A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations

*Helmut Prodinger, Guy Louchard*

#### Abstract

In words, generated by independent geometrically distributed random variables, we study
the lth descent, which is, roughly speaking, the lth occurrence of a neighbouring pair
ab with a>b. The value a is called the initial height, and b the end height.
We study these two random variables (and some similar ones) by combinatorial and probabilistic tools.
We find in all instances a generating function Ψ(v,u), where the
coefficient of v

^{j}u^{i}refers to the jth descent (ascent), and i to the initial (end) height. From this, various conclusions can be drawn, in particular expected values. In the probabilistic part, a Markov chain model is used, which allows to get explicit expressions for the heights of the*second*descent. In principle, one could go further, but the complexity of the results forbids it. This is extended to permutations of a large number of elements. Methods from q-analysis are used to simplify the expressions. This is the reason that we confine ourselves to the geometric distribution only. For general discrete distributions, no such tools are available.Full Text: PDF PostScript