\documentclass[12pt,a4paper,reqno]{amsart}%{article}

%\section{packages}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{theorem}
\usepackage{xspace}

\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip
\setlength{\parindent}{0pt}            
\setlength{\parskip}{5pt plus 2pt minus 1pt}     
\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   



\newtheorem{theorem}{Theorem}

\newtheorem{lemma}{Lemma}

\newtheorem{prop}{Proposition}


\def\Prob{\mathbb{P}}

\newcommand{\Res}[1]{\mathop{\textrm{Res}}\nolimits\left\ldlm#1\right\rdlm}
                                                   % Residue
\newcommand{\ffact}[2]{#1^{\underline{#2}}}
\newcommand{\img}{\text{i}}
\newcommand{\bigOh}{\mathop{\mathcal{O}}\nolimits}  
\newcommand{\Pm}{\operatorname{pm}}
\newcommand{\C}{\hat{C}}
\newcommand{\A}{\hat{A}}
\def\bb#1{[\![#1]\!]}



% other useful commands

%\providecommand{\email}[1]{E-mail: \texttt{#1}}
\newcommand{\etal}{\emph{et al\@.}\xspace}
\newcommand{\key}[1]{\mathbf{#1}}
\renewcommand{\th}[1]{\ensuremath{#1^{\text{th}}}}
\newcommand{\Leaf}{\qedsymbol}

%\section{preamble}
\title[ Value and position of left--to--right
maxima]
{Combinatorics of geometrically distributed random
variables:\\  Value and position of the $r$th left--to--right
maximum}

\author{Arnold Knopfmacher and Helmut Prodinger}
\address{ Arnold Knopfmacher,
Centre for Applicable Analysis and Number Theory,
 Department of Applied Mathematics,
University of the Witwatersrand, P.~O. Wits, 
2050 Johannesburg, South Africa, email:
{\tt arnoldk@gauss.cam.wits.ac.za}.
}

\address{ Helmut Prodinger,
Centre for Applicable Analysis and Number Theory,
 Department of Mathematics,
University of the Witwatersrand, P.~O. Wits, 
2050 Johannesburg, South Africa, email:
{\tt helmut@gauss.cam.wits.ac.za}.
}


\date{September 6, 1999}


\begin{document}

\begin{abstract}
For words of length $n$, generated by independent geometric
random variables, we consider the average value and the
average position of the $r$th left--to--right maximum, for
fixed $r$ and $n\to \infty$.
\end{abstract}


\maketitle

\section{Introduction}
\label{sec:intro}



For a permutation $\sigma_1 \sigma_1\dots \sigma_n $,
a {\em left--to--right maximum\/} 
({\em outstanding element, record,\dots\/})
is an element $\sigma_j$ with $\sigma_j>\sigma_i$ 
for all $i=1,\dots,j-1$. The number of 
left--to--right maxima was first studied by R\'enyi \cite{Renyi62},
compare also \cite{Knuth68}. A survey of results on this topic
can be found in \cite{Glick78}.
In particular the study of records has applications to observations
of extreme weather problems, test of randomness, determination
of minimal failure, stresses of electronic components, etc. 


Recently Wilf in \cite{Wilf95} proved the formula 
$(1-2^{-r})n$
for the average {\em value \/} of the $r$th 
left--to--right maximum, for fixed $r$ and $n\to\infty$;
for the average {\em position\/} he obtained
the asymptotic formula
$(\log n)^{r-1}/(r-1)!$.

In \cite{Prodinger96c} the number
of left--to--right maxima was investigated
in the model of {\em words\/} (strings) $a_1\dots a_n$, 
where the letters $a_i\in\mathbb N$ are independently
generated according to the geometric distribution with
$ \Prob{\{X=k\}}=pq^{k-1}$, with $p+q=1$.
(We find it useful also to use the abbreviation $Q=q^{-1}$.)
The motivation for this work comes from Computer Science.
In this context records arise in the study of skip lists
\cite{PaMuPo92, KiPr94} and probabilistic counting 
\cite{FlMa85, KiPr93}.
Also, since equal letters are now allowed, there are two
versions that should be considered in parallel, the standard
version, and the weak version, where `$<$' is replaced
by `$\le$,' which means that a new maximum  only
has to be larger or equal to the previous ones. 
The paper \cite{Prodinger96c} 
contains asymptotic results about the
average and the variance of the
 number
of left--to--right maxima in the context of geometric random
variables.
(H.--K.~Hwang and his collaborators obtained further
results about the limiting behaviour in \cite{BaHwLi98}.)

Motivated by Wilf's study we consider here the two 
parameters `value' and `position' of the 
$r$th left--to--right maximum
for geometric random variables. 
Summarizing our results, we obtain the 
asymptotic
formul{\ae}
$\frac rp$ and 
$\frac{1}{(r-1)!}\big(\frac pq\log_Qn\big)^{r-1}$
resp. 
$\frac {rq}p$ and 
$\frac{1}{(r-1)!}\big(p\log_Qn\big)^{r-1}$
in the weak case. 

A certain knowledge of \cite{Prodinger96c}
might be beneficial to understanding the present
derivations.

It should be noted that not all 
random strings of length $n$
{\em have\/} $r$
left--to--right maxima.

Let us start with the {\em value.} 
The generating function of interest is
\begin{equation}
\text{{\sf Value}}(z,u):=
\frac{1}{1-z}
\prod_{i=1}^{h-1}\left\{
1+\frac{pq^{i-1}zu}{1-(1-q^i)z}\right\}
zpq^{h-1},
\end{equation}
which originates from the (unique) decomposition of a string
as $a_1w_1\dots a_{r-1}w_{r-1}a_r w$ where
$a_1,\dots, a_r$ are the left--to--right maxima, 
the $w_i$ are the strings between them, and $w$ can be anything.
Note that if $a_k=l$, then this corresponds to a term
$pq^{l-1}zu$.
Any letter in $w_k$ can come with the probability
$1-q^k$,
 and thus $w_k$ corresponds to $\sum_{j\ge0}(1-q^k)^jz^j=1/\big(
1-(1-q^k)z\big)$. A particular value $i$ does not necessarily occur
as a left--to--right maximum; that is reflected by the 
$1+\dots$ in the product. However, when we look for the
coefficient of $u^{r-1}$, we have seen $r-1$
 left--to--right maxima, and the $r$th has value $h$. 
What comes after that is irrelevant and covered by the
factor $1/(1-z)$.

(Compare \cite{Prodinger96c} for similar generating functions.)

In the sequel we find it useful
to use the abbreviation
$\bb{i}:=1-(1-q^i)z$.


The coefficients of $z^nu^{r-1}$ in $\text{{\sf Value}}(z,u)$, call them 
$\pi ^{(r)}_{n,h}$, are not probabilities, because there exist words of length
$n$ with fewer than $r$     left--to--right maxima,    but 
the quantities
${\pi ^{(r)}_{n,h}}\big/{\pi ^{(r)}_{n}}

$
are, 
 where $\pi ^{(r)}_{n}$ is the probability that a string of
length $n$ {\em has\/} 
$r$
left--to--right maxima. We compute
$\pi ^{(r)}_{n}$ from $\text{{\sf Value}}(z,u)$ by
summing over all values $h$;
\begin{equation}
\pi ^{(r)}_{n}:=[z^nu^{r-1}]\frac{1}{1-z}
\sum_{h\ge1}\prod_{i=1}^{h-1}\left\{
1+\frac{pq^{i-1}zu}{\bb i}\right\}
zpq^{h-1}
=\sum_{h\ge1}\pi ^{(r)}_{n,h}.
\end{equation}
			

Now we turn to the {\em position.}
Set
\begin{equation}
\sigma ^{(r)}_{n,j}:=[z^nu^{r-1}v^j]\frac{1}{1-z}\sum_{h\ge1}
\prod_{k=1}^{h-1}\left\{
1+\frac{pq^{k-1}zvu}{1-(1-q^k)zv}\right\}
zvpq^{h-1},
\end{equation}
then
${\sigma^{(r)}_{n,j}}\big/{\pi ^{(r)}_{n}}$
is the probability that a random string of length $n$ has
the $r$th left--to--right maximum in position $j$. 
It is  the same decomposition as before, however, we are
not interested in the value $h$, so we sum over it. 
On the other hand, we label the position with the variable $v$, 
so we must make sure that every $z$ that does not appear in 
the factor $1/(1-z)$ must be multiplied by a $v$.
In other words, every letter up to the $r$th 
left--to--right maximum will be marked by $v$, which
means that we have as many $v$'s as the position.

Computationally, we find it easier to work with the parameter
``position~$-r$.'' For that, we don't label the letters
which are  left--to--right maxima (there are $r$ of them)
by a $v$, so that we consequently have as many $v$'s as 
``position~$-r$'' indicates. This leads us to the generating
function
\begin{equation}
\text{{\sf Position}}(z,u,v):=
\frac{1}{1-z}\sum_{h\ge1}
\prod_{k=1}^{h-1}\left\{
1+\frac{pq^{k-1}zu}{1-(1-q^k)zv}\right\}
zpq^{h-1}.
\end{equation}
We prefer this version
since the variable $v$ appears in fewer places, and the derivative
with respect to $v$ (needed for the expected value) produces fewer
terms.

In some places we have to assume $r\ge2$. This is no 
restriction since the position of the first left--to--right maximum
is obviously 1.






\section{Some technical lemmas}

In order to read off coefficients, we state the obvious
but nevertheless very useful formula

\begin{equation*}
[w^n]\sum_ia_if(b_iw)=\sum_ia_ib_i^n\cdot [w^n]f(w).
\end{equation*}

In all our applications, $\sum_ia_ib_i^n$ can be summed in
closed form.

We must often read off coefficients in iterated sums. 
To faciliate this, we state two lemmas that deal with
all the situations we encounter. 

\begin{lemma}
Assume that we have power series 
\begin{equation*}
A^{(j)}(w)=\sum_{n\ge1} a_{n}^{(j)}w^n, \qquad j=1,\dots,s.
\end{equation*}

Then
\begin{equation*}
[w^n]\sum_{1\le i_1<i_2<\dots<i_s}
A^{(1)}(wq^{i_1})\dots

A^{(s)}(wq^{i_s})=
\sum_{0=l_0<l_1<\dots<l_{s-1}<l_s=n}
\frac{a^{(s)}_{l_1-l_0}\dots a^{(1)}_{l_s-l_{s-1}}}
{(Q^{l_1}-1)\dots(Q^{l_s}-1)}.

\end{equation*}

\end{lemma}

\begin{proof}
For the sake of clarity, we treat the case $s=3$ and leave it
to the imagination of the reader to figure out the general case;
\begin{align*}

[w^n] &\sum_{1\le i<j<h}
A(wq^{i})B(wq^{j})
C(wq^{h})=
\sum_{l} \sum_{1\le i<j<h}
[w^{n-l}]A(wq^{i})B(wq^{j})\cdot[w^l]
C(wq^{h})\\
&=\sum_{l} \frac{1}{Q^l-1}

\sum_{1\le i<j}
[w^{n-l}]A(wq^{i})B(wq^{j})\cdot[w^l]
C(w)q^{jl}\\
&=\sum_{l} \frac{c_l}{Q^l-1}
\sum_{1\le i<j}
[w^{n}]A(wq^{i})B(wq^{j})
(wq^{j})^l\\
&=\sum_{l,m} \frac{c_l}{Q^l-1}
\sum_{1\le i<j}
[w^{n-m}]A(wq^{i})\cdot [w^m]B(wq^{j})
(wq^{j})^l\\
&=\sum_{l,m} \frac{c_l}{(Q^l-1)(Q^m-1)}
\sum_{1\le i}
[w^{n-m}]A(wq^{i})q^{im}\cdot [w^m]B(w)
w^l\\
&=\sum_{l,m} \frac{c_lb_{m-l}}{(Q^l-1)(Q^m-1)}
\sum_{1\le i}
[w^{n}]A(wq^{i})(wq^{i})^m\\
&=\sum_{l,m} \frac{c_l\,b_{m-l}\,a_{n-m}}{(Q^l-1)(Q^m-1)
(Q^n-1)}.

\end{align*}







\end{proof}

\begin{lemma}
\begin{align*}
[w^n]&\sum_{1\le i_1<i_2<\dots<i_s}
A^{(1)}(wq^{i_1})\dots
A^{(s)}(wq^{i_s})\,i_s\\
&=[t]
\sum_{0=l_0<l_1<\dots<l_{s-1}<l_s=n}
{a^{(s)}_{l_1-l_0}\dots a^{(1)}_{l_s-l_{s-1}}}
\prod_{i=1}^s
\bigg(\frac1{Q^{l_i}-1}
+t\frac{Q^{l_i}}{(Q^{l_i}-1)^2}
\bigg).
\end{align*}


\end{lemma}


\begin{proof}
The proof is essentially the same as before, if we note that
\begin{equation*}
\sum_{h>j}h\,q^{hl}=q^{jl}
\bigg(
 \frac{Q^l}{(Q^l-1)^2}+\frac{j}{Q^l-1}

\bigg).
\end{equation*}



\end{proof}

Our quantities will eventually come out as alternating sums, 
and the appropriate treatment of them is Rice's method
which is surveyed in \cite{FlSe95}; the key point
is the 
following Lemma.
\begin{lemma} 
Let $\mathcal C$ be a curve surrounding the points $1,2,\dots,n$ 
in the complex plane and let $f(z)$ be analytic inside $\mathcal C$. Then
$$
\sum_{k=1}^n \binom nk \, {(-1)}^k f(k)=
-\frac 1{2\pi i} \int_{\mathcal C} [n;z] f(z) dz, 
$$
where
$$
[n;z]=\frac{(-1)^{n-1} n!}{z(z-1)\dots(z-n)}=
\frac{\Gamma(n+1)\Gamma(-z)}{\Gamma(n+1-z)}.
$$

\end{lemma}

Extending the contour of integration it turns out that 
under suitable growth conditions on $f(z)$ (compare \cite{FlSe95})
the asymptotic expansion
of the alternating sum is given by
$$ 
\sum \text {Res} \big( [n;z] f(z)\big)+\text{smaller order terms}
$$
where the sum is taken over all poles $z_0$
different from $1,\dots,n$. 
Poles that lie more to the left lead to smaller terms in the
asymptotic expansion.

 
The range $1,\dots,n$ for the summation is not sacred; 
if we sum, for example, over $k=2,\dots,n$, the contour must
encircle $2,\dots,n$, etc.



\section{The probability that there are $r$ maxima}

Now we want to read off the $n$th coefficients of the power series
of interest. For this, it is beneficial to use the following formula:

\begin{equation*}
[z^n]f(z)=(-1)^n[w^n](1-w)^{n-1}f\Big(\frac{w}{w-1}\Big).
\end{equation*}

This form can be found in \cite{KiMaPr95} and is based on
ideas concerning the Euler transform in \cite{FlRi92}.

Then the quantities come out automatically as alternating
sums, and Rice's method can be applied. 






\begin{align*}
\pi ^{(r)}_{n}&=[z^n]\frac{1}{1-z}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{pq^{i_{1}-1}z}{\bb{ i_{1}}}\dots
\frac{pq^{i_{r-1}-1}z}{\bb {i_{r-1}}}
zpq^{h-1}\\
&=
\Big(\frac{p}{q}\Big)^{r}[z^n]\frac{1}{1-z}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}z}{\bb{ i_{1}}}\dots
\frac{q^{i_{r-1}}z}{\bb {i_{r-1}}}
zq^{h}\\
&=(-1)^r
\Big(\frac{p}{q}\Big)^{r}(-1)^n[w^n](1-w)^{n-1}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}\\
&=(-1)^r
\Big(\frac{p}{q}\Big)^{r}
\sum_{k=r}^{n}\binom{n-1}{k-1}(-1)^k
[w^k]
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}.
\end{align*}
Now the evaluation of the inner sum can be done by our
Lemma; $k=n$, $r=s$, $A^{(1)}(w)=\dots=
A^{(r-1)}(w)=\frac{w}{1-w}$, $A^{(r)}(w)=w$.
Therefore
\begin{align*}
[w^k]&
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}\\
&=\sum_{0=l_0<1=l_1<l_2<\dots<l_r=k}
\frac{1}{(Q-1)(Q^{l_2}-1)\dots (Q^{l_r}-1)}\\
&=\frac qp\sum_{2\le l_2<\dots<l_r=k}
\frac{1}{(Q^{l_2}-1)\dots (Q^{l_r}-1)}.
\end{align*}

Thus

\begin{align*}
\pi ^{(r)}_{n}
=(-1)^{r-1}
\Big(\frac{p}{q}\Big)^{r-1}
\sum_{k=r-1}^{n-1}\binom{n-1}{k}(-1)^k
f(k)
\end{align*}
with

\begin{equation*}
f(k)=\sum_{2\le l_2<\dots<l_r=k+1}
\frac{1}{(Q^{l_2}-1)\dots (Q^{l_r}-1)}.
\end{equation*}

In order to apply Rice's method one needs the continuation 
of $f(k)$ to the complex plane.
Using {\em symmetric functions, } one can always 
represent such iterated summations by powersums
\cite{Knuth68}
\begin{equation*}
\vartheta (k):=\sum_{l= 2}^k\frac{1}{(Q^{l}-1)^d},
\end{equation*}

and the task is reduced to
finding an extension of  this quantity $\vartheta (k)$
valid in the the complex plane. For this, the standard way of doing
it is via
\begin{equation*}
\vartheta (z):=\sum_{l\ge 2}\frac{1}{(Q^{l}-1)^d}
-\sum_{l\ge1 }\frac{1}{(Q^{l+z}-1)^d}.
\end{equation*}








However, we only need the values
$f(0),\dots,f(r-2)$.

In \cite{GrKnPa94} we learn how such a sum should be 
interpreted: As with integrals, a (definite) sum
\begin{equation*}
\sum_{a\le k<b}g(k)
\end{equation*}

is defined by $G(b)-G(a)$, with 
an indefinite sum function.
In particular, for $a=b$ we get 0, as we should, and for instance
$\sum_{1\le k<-2}g(k)=-g(0)-g(1)-g(2)$. This idea can of course
be iterated. Computer algebra systems like Maple deal with
such ranges of summation correctly. 






 We thus find $f(1)=\dots=f(r-2)=0$
and
\begin{equation*}
f(0)=(-1)^{r}\Big(\frac{1}{Q-1}\Big)^{r-1}.
\end{equation*}

Hence Rice's method and the pole at $z=0$
give us
\begin{equation*}
\pi ^{(r)}_{n}=1+O\Big(\frac1n\Big),
\end{equation*}
which is intuitively clear.

Note that there are poles at $z=-1+2\pi ik/\log Q$,
$k\in\mathbb Z$, 
and they lead to a periodic fluctuation of order $\frac 1n$;
this phenomenon is well--known and appears in many
places (compare \cite{FlSe95} and some other references).



\section{The average value of the $r$th maximum}

Now we can safely deal with the quantities
$\pi ^{(r)}_{n,h}$ alone, and  the so computated
average value $E^{(r)}_{n}$ will be correct within an error term
of the form $1+O(\frac1n)$.
We compute



\begin{align*}
 E^{(r)}_{n}&=
\sum_{h\ge1}h[z^nu^{r-1}]\text{{\sf Value}}(z,u)\\
&=[z^n]\frac{1}{1-z}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{pq^{i_{1}-1}z}{\bb{ i_{1}}}\dots
\frac{pq^{i_{r-1}-1}z}{\bb {i_{r-1}}}
zpq^{h-1}h\\
&=
\Big(\frac{p}{q}\Big)^{r}[z^n]\frac{1}{1-z}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}z}{\bb{ i_{1}}}\dots
\frac{q^{i_{r-1}}z}{\bb {i_{r-1}}}
zq^{h}h\\
&=(-1)^r
\Big(\frac{p}{q}\Big)^{r}(-1)^n[w^n](1-w)^{n-1}
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}h\\
&=(-1)^r
\Big(\frac{p}{q}\Big)^{r}
\sum_{k=r}^{n}\binom{n-1}{k-1}(-1)^k
[w^k]
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}h.
\end{align*}
The inner sum is now evaluated by the 
(second) Lemma:




\begin{align*}
[w^k]&
\sum_{1\le i_1< \dots <i_{r-1} <h}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}
wq^{h}h\\
&=[t]\sum_{1=l_1<l_2<\dots<l_r=k}
\prod_{i=1}^r
\bigg(\frac1{Q^{l_i}-1}
+t\frac{Q^{l_i}}{(Q^{l_i}-1)^2}
\bigg).
\end{align*}
Or,

\begin{equation*}

E^{(r)}_n=
(-1)^{r-1}
\Big(\frac{p}{q}\Big)^{r}
\sum_{k=r-1}^{n-1}\binom{n-1}{k}(-1)^k
f(k)
\end{equation*}
with
\begin{equation*}
f(k)=[t]\sum_{1=l_1<l_2<\dots<l_r=k+1}
\prod_{i=1}^r
\bigg(\frac1{Q^{l_i}-1}
+t\frac{Q^{l_i}}{(Q^{l_i}-1)^2}
\bigg).
\end{equation*}

Again, $f(1)=\dots=f(r-2)=0$ and
since in general
\begin{align*}
\sum_{1=l_1<l_2<\dots<l_r=1}
a_{l_1}a_{l_2}\dots
a_{l_r}=(-1)^ra_{1}a_{1}\dots
a_{1},
\end{align*}
we find 

\begin{align*}
f(0)&=[t]\sum_{1=l_1<l_2<\dots<l_r=1}
\prod_{i=1}^r
\bigg(\frac1{Q^{l_i}-1}
+t\frac{Q^{l_i}}{(Q^{l_i}-1)^2}
\bigg)\\&=(-1)^r
[t]\bigg(\frac1{Q-1}
+t\frac{Q}{(Q-1)^2}\bigg)^r=
(-1)^rr\frac{Q}{(Q-1)^{r+1}}.
\end{align*}

Thus we have proved the following theorem

\begin{theorem}

The average value $E^{(r)}_n$ of the $r$th left--to--right maximum
in a random sequence of $n$ elements, generated by 
geometric random variables is given by
\begin{equation*}
E^{(r)}_n=\frac{r}{p}+O\Big(\frac1n\Big)
\qquad\text{for fixed $r$ and $n\to\infty.$}
\end{equation*}

\end{theorem}
A full asymptotic expansion would be available, at least in 
principle, with more involved computations, as well as the
variance.

Again, as in all the examples that will follow, the lower
order terms contain periodic fluctuations of the form
$\delta(\log_Qn)$.

In many instances, the limit $q\to1$ produces the corresponding
result for permutations. Here Theorem~1 would yield infinity. 
In the instance of permutations, as we know from \cite{Wilf95},
we have something proportional to $n$. In a sense, this in meaningful, 
since no (finite) constant would be appropriate. 



\section{The average position of the $r$th maximum}

In order to compute this parameter (or rather the modified version),
we have to differentiate the generating function 
$\text{{\sf Position}}(z,u,v)$
from the 
Introduction with respect to $v$ and plug in $v=1$.
The desired   average position of the $r$th 
left--to--right
maximum (up to an error of the form $1+O(1/n)$, as in the previous
section)
is then obtained via
\begin{align*}
&[z^nu^{r-1}]\frac{\partial}{\partial v}
\text{{\sf Position}}(z,u,v)\Big\vert_{v=1}\\
&=[z^n]\Big(\frac pq\Big)^r
\frac{1}{1-z}[t]\sum_{1\le i_1<\dots<i_{r-1}<h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}z}{\bb{i_j}}+t
\frac{q^{i_j}z(1-q^{i_j})z}{{\bb{i_j}}^2}
\bigg)zq^h\\
&=(-1)^n
[w^n](1-w)^{n-1}\Big(\frac pq\Big)^{r}(-1)^r
\times \\&\qquad\times 
[t]\sum_{1\le i_1<\dots<i_{r-1}<h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}-t
\frac{q^{i_j}w(1-q^{i_j})w}{(1- q^{i_j}w)^2}
\bigg)wq^{h}\\
&=\Big(\frac pq\Big)^{r}(-1)^{r-1}
\sum_{k=r-1}^{n-1}\binom {n-1}k(-1)^kf(k)
\end{align*}


where
\begin{equation*}
f(k)=[w^{k+1}][t]\sum_{1\le i_1<\dots<i_{r-1}<h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}-t
\frac{q^{i_j}w(1-q^{i_j})w}{(1- q^{i_j}w)^2}
\bigg)wq^{h}=f_1(k)+f_2(k)
\end{equation*}


with
\begin{equation*}
f_1(k)=[t][w^{k}]\sum_{1\le i_1<\dots<i_{r-1}<h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}-t
\frac{q^{i_j}w}{(1- q^{i_j}w)^2}
\bigg)wq^{h}
\end{equation*}
and
\begin{equation*}
f_2(k)=[t][w^{k+1}]\sum_{1\le i_1<\dots<i_{r-1}<h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}+t
\frac{(q^{i_j}w)^2}{(1- q^{i_j}w)^2}
\bigg)wq^{h}.
\end{equation*}
Now the two sums are in a form where our 
(first) technical lemma 
applies!

For $f_1(k)$ note that $A_1(w)=\dots=A_{r-1}(w)=
\frac{w}{1-w}-\frac{tw}{(1-w)^2}$ and $A_r(w)=w$.
Thus
\begin{align*}
f_1(k)&=[t]
\sum_{1=l_1<l_2<\dots<l_r=k}\frac{
\big(1-t(l_2-l_1)\big)
\dots
\big(1-t(l_r-l_{r-1})\big)
}
{(Q^{l_1}-1)\dots(Q^{l_r}-1)}\\
&=-(k-1)
\sum_{1=l_1<l_2<\dots<l_r=k}\frac{1
}
{(Q^{l_1}-1)\dots(Q^{l_r}-1)}.
\end{align*}

For $f_2(k)$ note that $A_1(w)=\dots=A_{r-1}(w)=
\frac{w}{1-w}+\frac{tw^2}{(1-w)^2}$ and $A_r(w)=w$.
Thus											
\begin{align*}
f_2(k)&=[t]
\sum_{1=l_1<l_2<\dots<l_r=k+1}\frac{
\big(1+t(l_2-l_1-1)\big)
\dots
\big(1+t(l_r-l_{r-1}-1)\big)
}
{(Q^{l_1}-1)\dots(Q^{l_r}-1)}\\
&=(k-r)
\sum_{1=l_1<l_2<\dots<l_r=k+1}\frac{1
}
{(Q^{l_1}-1)\dots(Q^{l_r}-1)}.
\end{align*}
As we know from before, it is the ``value'' (the behaviour)
of $f(0)$ that is required. 
It is $f_1(0)$ that is dominant here:
Since in general
\begin{equation*}
\sum_{2\le l_2<\dots<l_{r-1}<0}a_{l_2}\dots
a_{l_{r-1}}=(-1)^r\frac{a_0^{r-1}-a_1^{r-1}}{a_0-a_1},
\end{equation*}


we find that as $z\to 0$
\begin{equation*}
f(z)\sim \frac{(-1)^r}{(Q-1)(Q^z-1)^{r-1}}.
\end{equation*}


In \cite{FlSe95} it is explained in detail what kind of contribution an
$r$th order pole at $z=0$ gives. The sum from Example 1 (loc. cit. on
page 107) is what we need here;
\begin{equation*}
\sum_{k=1}^n\binom nk\frac{(-1)^k}{k^m}=\frac{\log^mn}{m!}+
O(\log^{m-1}n).
\end{equation*}




Therefore we obtain the following theorem. 



\begin{theorem}

The average position of the $r$th left--to--right maximum
in a random sequence of $n$ elements, generated by 
geometric random variables is given by
\begin{equation*}
\frac{1}{(r-1)!}\Big(\frac pq\log_Qn\Big)^{r-1}
+O\big(\log^{r-2}n\big)
\qquad\text{for fixed $r\ge2$ and $n\to\infty.$}
\end{equation*}


\end{theorem}

Here, the limit $q\to1$ produces the correct expression
\begin{equation*}
\frac{(\log n)^{r-1}}{(r-1)!}
\end{equation*}

that holds in the instance of permutations. (See \cite{Wilf95}.)








\section{Weak left--to--right maxima; the value}

We mention here briefly the analogous developments for the 
instance of weak left--to--right maxima.



The generating function of interest is
\begin{equation*}
\frac{1}{1-z}
\prod_{i=1}^{h-1}
\bigg\{{1-\frac{pq^{i-1}zu}{\bb{i-1}}}\bigg\}^{-1}
pq^{h-1}z,
\end{equation*}
and the coefficient of $u^{r-1}$ therein is
\begin{align*}
&\frac{1}{1-z}\sum_{1\le i_1\le \dots\le i_{r-1}\le h}
\frac{pq^{i_{1}-1}z}{\bb{i_1-1}}\dots
\frac{pq^{i_{r-1}-1}z}{\bb{i_{r-1}}}pq^{h-1}z\\
&=p^r\frac{1}{1-z}\sum_{0\le i_1\le \dots\le i_{r-1}\le h}
\frac{q^{i_{1}}z}{\bb{i_1}}\dots
\frac{q^{i_{r-1}}z}{\bb{i_{r-1}}}q^{h}z.
\end{align*}

The technical lemmas that we need now are




\begin{lemma}
\begin{equation*}
[w^n]\sum_{0\le i_1\leq i_2\leq \dots \leq i_s}
A^{(1)}(wq^{i_1})\dots
A^{(s)}(wq^{i_s})=
\sum_{0=l_0<l_1<\dots<l_{s-1}<l_s=n}
\frac{a^{(s)}_{l_1-l_0}\dots a^{(1)}_{l_s-l_{s-1}}}
{(1-q^{l_1})\dots(1-q^{l_s})}
\end{equation*}
and
\begin{align*}
[w^n]&\sum_{0\le i_1 \leq i_2\leq \dots\leq i_s}
A^{(1)}(wq^{i_1})\dots
A^{(s)}(wq^{i_s})\,(i_s+1)\\
&=[t]
\sum_{0=l_0<l_1<\dots<l_{s-1}<l_s=n}
{a^{(s)}_{l_1-l_0}\dots a^{(1)}_{l_s-l_{s-1}}}
\prod_{i=1}^s
\bigg(\frac1{1-q^{l_i}}
+t\frac{q^{l_i}}{(1-q^{l_i})^2}
\bigg).
\end{align*}


\end{lemma}

We find


\begin{equation*}
E^{(r)}_n=
(-1)^{r-1}
p^{r}
\sum_{k=r-1}^{n-1}\binom{n-1}{k}(-1)^k
f(k)
\end{equation*}
with
\begin{equation*}
f(k)=[t]\sum_{1=l_1<l_2<\dots<l_r=k+1}
\prod_{i=1}^r
\bigg(\frac1{1-q^{l_i}}
+t\frac{q^{l_i}}{(1-q^{l_i})^2}
\bigg).
\end{equation*}

Also, $f(0)=(-1)^rr\frac{q}{(1-q)^{r+1}}$
and thus



\begin{theorem}

The average value $E^{(r)}_n$ of the $r$th left--to--right maximum
(in the weak sense)
in a random sequence of $n$ elements, generated by 
geometric random variables is given by
\begin{equation*}
E^{(r)}_n=\frac{r\,q}{p}+O\Big(\frac1n\Big)
\qquad\text{for fixed $r$ and $n\to\infty.$}
\end{equation*}








\end{theorem}


\section{Weak left--to--right maxima; the position}

The probability generating funtion of interest (up to normalization
by a factor that is basically $1$, as before)
is given by

\begin{equation*}
\frac{1}{1-z}\sum_{h\ge1}
\prod_{i=1}^{h-1}\left\{
1-\frac{pq^{i-1}zvu}{1-(1-q^i)zv}\right\}^{-1}
zvpq^{h-1},
\end{equation*}
and the desired expectated value is

\begin{align*}
[z^n] &p^r \frac{1}{1-z}
\sum_{0\leq i_1\leq \dots\leq i_{r-1}\leq h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}z}{\bb{i_j}}+t

\frac{q^{i_j}z(1-q^{i_j})z}{{\bb{i_j}}^2}
\bigg)zq^h\\

&=p^r(-1)^{r-1}\sum_{k=r-1}^{n-1}\binom{n-1}{k}(-1)^kf(k)

\end{align*}
with $f(k)=f_1(k)+f_2(k)$ and


\begin{equation*}
f_1(k)=[t][w^{k}]\sum_{0\le i_1\le \dots\le i_{r-1}\le h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}-t
\frac{q^{i_j}w}{(1- q^{i_j}w)^2}
\bigg)wq^{h}
\end{equation*}
and
\begin{equation*}
f_2(k)=[t][w^{k+1}]\sum_{0\le i_1\le \dots\le i_{r-1}\le h}
\prod_{j=1}^{r-1}
\bigg(
\frac{q^{i_j}w}{1- q^{i_j}w}+t
\frac{(q^{i_j}w)^2}{(1- q^{i_j}w)^2}
\bigg)wq^{h}.
\end{equation*}
We find

\begin{align*}
f_1(k)=-(k-1)
\sum_{1=l_1<l_2<\dots<l_r=k}\frac{1
}
{(1-q^{l_1})\dots(1-q^{l_r})}
\end{align*}
and
\begin{align*}
f_2(k)=(k-r)
\sum_{1=l_1<l_2<\dots<l_r=k+1}\frac{1
}
{(1-q^{l_1})\dots(1-q^{l_r})}.
\end{align*}



As $z\to 0$
\begin{equation*}
f(z)\sim \frac{(-1)^r}{(1-q)(1-q^z)^{r-1}},
\end{equation*}
and thus


\begin{theorem}

The average position of the $r$th left--to--right maximum
(in the weak sense)
in a random sequence of $n$ elements, generated by 
geometric random variables is given by
\begin{equation*}
\frac{1}{(r-1)!}\big(p\log_Qn\big)^{r-1}
+O\big(\log^{r-2}n\big)
\qquad\text{for fixed $r\ge2$ and $n\to\infty.$}
\end{equation*}


\end{theorem}








\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{BaHwLi98}
Z.-D. Bai, H.-K. Hwang, and W.-Q. Liang.
\newblock Normal approximations of the number of records in geometrically
  distributed random variables.
\newblock {\em Random Structures and Algorithms}, 13:319--334, 1998.

\bibitem{FlMa85}
P.~Flajolet and G.~N. Martin.
\newblock Probabilistic counting algorithms for data base applications.
\newblock {\em Journal of Computer and System Sciences}, 31:182--209, 1985.

\bibitem{FlRi92}
P.~Flajolet and B.~Richmond.
\newblock Generalized digital trees and their difference--differential
  equations.
\newblock {\em Random Structures and Algorithms}, 3:305--320, 1992.

\bibitem{FlSe95}
P.~Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: Finite differences and {R}ice's
  integrals.
\newblock {\em Theoretical Computer Science}, 144:101--124, 1995.

\bibitem{Glick78}
N.~Glick.
\newblock Breaking records and breaking boards.
\newblock {\em American Mathematical Monthly}, 85:2--26, 1978.

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.

\bibitem{KiMaPr95}
P.~Kirschenhofer, C.~Mart{\'{\i}}nez, and H.~{P}rodinger.
\newblock Analysis of an optimized search algorithm for skip lists.
\newblock {\em Theoretical Computer Science}, 144:199--220, 1995.

\bibitem{KiPr93}
P.~Kirschenhofer and H.~{P}rodinger.
\newblock A result in order statistics related to probabilistic counting.
\newblock {\em Computing}, 51:15--27, 1993.

\bibitem{KiPr94}
P.~Kirschenhofer and H.~{P}rodinger.
\newblock The path length of random skip lists.
\newblock {\em Acta Informatica}, 31:775--792, 1994.

\bibitem{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Third edition, 1997.

\bibitem{PaMuPo92}
T.~Papadakis, I.~Munro, and P.~Poblete.
\newblock Average search and update costs in skip lists.
\newblock {\em BIT}, 32:316--332, 1992.

\bibitem{Prodinger96c}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables:
  Left-to-right maxima.
\newblock {\em Discrete Mathematics}, 153:253--270, 1996.

\bibitem{Renyi62}
A.~R\'enyi.
\newblock Th\'eorie des \'el\'ements saillants d'une suite d'observations.
\newblock {\em Ann. Fac. Sci. Univ. Clermont-Ferrand}, 8:7--13, 1962.

\bibitem{Wilf95}
H.~Wilf.
\newblock On the outstanding elements of permutations.
\newblock {\em {\tt http://www.cis.upenn.edu/$\sim$wilf}}, 1995.

\end{thebibliography}




%\bibliography{C:/texfiles/pro_bib}
\end{document}

