\documentclass[12pt,a4paper,reqno]{amsart}%{article}
%\section{packages}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{theorem}
\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}
\def\O{\mathcal{O}}
\allowdisplaybreaks
\newcommand{\qf}[2]{(#1;q)_{#2}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\def\eps{\varepsilon}
\def\la{\lambda}
\def\CO{\mathbb{C}}
\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 large
left--to--right maxima]
{Combinatorics of geometrically distributed random
variables:\\
Value and position of large
left--to--right maxima}
\author{Helmut Prodinger}
\address{ Helmut Prodinger,
The John Knopfmacher Centre for Applicable Analysis and Number Theory,
School of Mathematics,
University of the Witwatersrand, P.~O. Wits,
2050 Johannesburg, South Africa, email:
{\tt helmut@gauss.cam.wits.ac.za},\newline
homepage:
{\tt http://www.wits.ac.za/helmut/index.htm}.
}
%\date{March 7, 2000}
\date{\today}
\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
{\it counted from the right,} for
fixed $r$ and $n\to \infty$. This complements previous research
\cite{KnPr00} where the analogous questions were considered
for the $r$th left--to--right maximum
{\it counted from the left.}
\end{abstract}
\maketitle
\section{Introduction}
\label{sec:intro}
In this paper we study sequences with respect
to the {\em left--to--right maxima\/} of the elements of
the sequence.
This paper is a companion paper to \cite{KnPr00}, and these
two papers should be read together.
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
\begin{equation}\label{geom}
\Prob{\{X=k\}}=pq^{k-1}, \qquad\text{where $p+q=1$.}
\end{equation}
(An element is a left--to--right maximum if it is
larger than all the elements to the left. The version
where `larger' is replaced by `larger or equal' would
be also of interest but is not considered here.)
In \cite{KnPr00} we considered the two
parameters `value' and `position' of the
$r$th left--to--right maximum
for geometric random variables and
obtained the
asymptotic
formul{\ae}
$\frac rp$ and
$\frac{1}{(r-1)!}\big(\frac pq\log_Qn\big)^{r-1}$.
These results cover the instances of small
left--to--right maxima; therefore we investigate
here the instance of {\it large\/} left--to--right maxima.
We say that the last left--to--right maximum is the
instance $r=1$, the previous left--to--right maximum
is the instance $r=2$, and so on.
As can be seen in the forthcoming book \cite{FlSe05},
in the limit $q\to1$ the model becomes the model
of {\it random permutations.} The concept of `value' does
not carry over, but the concept of `position' does.
The largest element in a random permutation of $n$ elements
(which is $n$) is expected to be in the middle.
The second largest is then expected to be in the middle
of the first half, and so on. In general, the average
position should be about $\frac{n}{2^r}$.
We find it useful to use the additional
notations $Q:=q^{-1}$, $L:=\log Q$,
and
$\bb{i}:=1-(1-q^i)z$.
In \cite{Prodinger96c}, compare also
\cite{SzRe90}, the average value of the {\it height\/}
was considered. The average height
is asymptotic to $\log_Qn$. The same formula comes out
for the instance $r=1$ of the average value
of left--to--right maxima, counted from the right.
Intuitively, for fixed $r$, the same asymptotic
formula is to be expected, the depency of $r$ only
appearing in the lower order terms.
It should be noted that not all
random strings of length $n$
{\em have\/} $r$
left--to--right maxima.
However, as explained already in \cite{KnPr00},
this happens with low probability and can be ignored.
\section{The average value of the $r$th left--to--right
maximum from the right}
The following expression for
the average value of the $r$th left--to--right
maximum from the right is obtained as in
\cite{KnPr00}; just observe that we assume that it
is $h$, and that $r-1$ more left--to--right
maxima follow to the right, whereas to the left
everything is smaller than $h$:
\begin{align*}
E^{(r)}_{n}&=[z^n]
\sum_{1\le h< i_1< \dots