\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_1j}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