%Discrete Mathematics
\input amstex
\documentstyle{amsppt}
\headline={ \hfil}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13
\hsize=15truecm
\vsize=20.5truecm
\hfuzz=10pt
\document
\NoRunningHeads
\TagsOnRight
\topmatter
\title
Combinatorics of Geometrically Distributed Random Variables:\\
Left-to-Right Maxima
\endtitle
\author Helmut Prodinger \endauthor
\affil
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress
\email proding\@email.tuwien.ac.at
\endemail
\abstract Assume that the numbers $x_1,\dots,x_n$ are the output of $n$
independent geometrically distributed random variables. The number
$x_i$ is a left-to-right maximum if it is greater (or equal, for a variation,)
than $x_1,\dots,x_{i-1}$. A precise average case analysis is performed
for the parameter `number of left-to-right maxima'. The methods include
generating functions and a technique from complex analysis, called
Rice's method. Some additional results are also given.
\endabstract
\endtopmatter
\redefine\P{\Bbb P}
\head 1. Introduction \endhead
Let $X$ denote a geometrically distributed random variable, i.e.
$\P\{X=k\}=pq^{k-1}$ for $k\in\Bbb N$ and $q=1-p$.
The combinatorics of $n$ geometrically distributed independent variables
$X_1,\dots,X_n$
becomes more and more important, especially because of applications
in Computer science. We just mention two areas: The {\bf skiplist}
(\cite{2}, \cite{14}, \cite{15})
and {\bf probabilistic counting} (\cite{4}, \cite{8},
\cite{9}, \cite{10}).
{\textfont0=\eightrm
\scriptfont0=\sixrm\scriptscriptfont0=\fiverm
\textfont1=\eighti
\scriptfont0=\seveni\scriptscriptfont0=\fivei
\def\klein{\fam0 \eightrm}
\klein
\narrower\narrower\bigskip\noindent
The skip list is a data structure for searching. To each
of the $n$ elements that are stored there will be some pointer fields,
and the number of those is chosen according to a
geometric random variable. Furthermore,
the `horizontal search costs' of a particular element are just the
number of left-to-right maxima of the truncated and reversed sequence.
\smallskip\noindent
In the case of probabilistic counting we think about $p=q=\frac12$.
The parameter of interest is then the smallest natural number that does
not appear as an output of any of the $X_i$'s.
\bigskip}
We will cite one particular result, since we can use the corresponding
asymptotic formula in the sequel for our own findings.
\proclaim{Theorem 1} {\rm [Szpankowski and Rego, \cite{17}]} \quad
The expected value $E_n$
of $\max\left\{X_1,\dots,X_n\right\}$ is given by
$$
E_n=\sum_{k\ge 0}\left[1-\left(1-q^k\right)^n\right]
= \log_Qn+\frac{\gamma}{L}+\frac 12-\delta\left(\log_Qn\right)
+O\big(\frac 1n\big).
\tag 1.1
$$
Here and in the whole paper, $Q=q^{-1}$ and $L=\log Q$; $\gamma$ is
Euler's constant and $\delta(x)$ is a periodic function of period 1 and mean
0 which is given by the Fourier series
$$
\delta(x)=\frac{1}{L}\sum_{k\ne 0}\Gamma\left(-\chi_k\right)
e^{2k\pi ix}. \tag 1.2
$$
The complex numbers $\chi_k$ are given by $\chi_k=2k\pi i/L$.
\endproclaim
It should be mentioned that the asymptotic evaluation of the series in
\thetag {1.1} is by now a ``folklore theorem''; it appears e.g. in Knuth's book
\cite{12} or in \cite{6}.
In this paper we want to concentrate on the {\sl number of left-to-right
maxima}. This is a well studied parameter in the context of random
permutations; practically every text dealing with the analysis of algorithms
devotes a section to it (\cite{11}, \cite{7}, \cite{6}, \cite
{16}).
As is easy to guess by the name, this parameter counts how often we
meet a number that is larger than all the elements to the left.
The results for random permutations are: The harmonic number $H_n$ for the
expectation and $H_n-H_n^{(2)}$ for the variance;
here, $H_n^{(2)}=1+\frac14+\dots+\frac{1}{n^2}$ denotes the $n$-th
harmonic number of second order .
There are 2 meaningful ways to define left-to-right maxima:
A number is a left-to-right maximum if it is strictly larger than
the elements to left (the ``strict'' sense) or a
number is a left-to-right maximum if it is larger or equal than
the elements to left (the ``loose'' sense). On might call the first
variant ``without repetitions'' and the second ``with repetitions'';
with respect to the computations involved the terms ``easy'' and
``not quite easy'' might also be in order.
(Or ``strong'' versus ``weak''.)
Of course, for random permutations
this distinction does not make a difference.
The next two sections deal with the expectations; they are followed by two
sections on the variances. In the next two sections we study a related
model (again with 2 variants), namely: The random variable $X$ takes
the values $1,\dots,M$, each with probability $\frac 1M$.
(The uniform distribution.)
Finally, we come back to the original model of geometrically distributed
variables and consider left-to-right {\sl minima}. This makes no difference for
random permutations and equidistribution, but here it is different!
However, the computations for the {\sl maxima\/} require ``higher mathematics''
(Mellin transforms or Rice's method), and some periodicity phenomena
are encountered, whereas the calculations for the {\sl minima\/} are quite
elementary.
It is interesting to note that the concept of left-to-right maxima appears
also as ``records'', compare\cite1.
To obtain the leading terms of the asymptotic expansions in Theorems 2
and 3 (namely $p\log_Qn$ and $\frac pq\log_Qn$) is not a big deal; however
it quite surprising (and non trivial)
that the lower order terms contain ``fluctuations'' (see below for details).
Since we are considering, assuming different models, the analogous
quantities
over and over, we decided to stay with the same notations. So the reader
is warned that the same notations might have different meanings in
different sections.
\head 2. The expectation in the strict model \endhead
Our approach will be by generating functions; to find them, we set up a
certain ``language'' $\Cal L$
and translate it to enumerating generating functions.
We give two references for such a procedure: \cite{13} and
\cite{6}.
To avoid confusion, we denote the ``letters'' by $\bold 1,\bold 2,\dots\,$.
We decompose all sequences $x_1x_2\dots$ in a canonical way as follows:
We combine each left-to-right maximum
$\bold k$ with the following (smaller or equal) elements.
Such a part is decribed by
$$
\Cal A_k:=\bold k \{\bold 1, \dots , \bold{k}\}^*.\tag 2.1
$$
Such a group may be present or not. This observation gives the desired
``language'', where $\varepsilon$ denotes the ``empty word'':
$$
\Cal L:=\big(\Cal A_1+\varepsilon\big)\cdot\big(\Cal A_2+\varepsilon\big)\cdot
\big(\Cal A_3+\varepsilon\big)\dots \tag 2.2
$$
It is important not to confuse $\varepsilon$ with something like a letter
$\bold0$ (not being present here).
Now we want to mark each letter by a ``$z$'' and each left-to-right maximum
by a ``$y$''. The probability $pq^{k-1}$ for a letter $\bold k$ should
of course not being forgotten.
$\{\bold 1, \dots , \bold{k}\}$ maps into $z(1-q^k)$ and its star
$\{\bold 1, \dots , \bold{k}\}^*$ into $1\big/\big(1-z(1-q^k)\big)$.
So we obtain the generating function $F(z,y)$ as an infinite product:
$$
F(z,y)=\prod_{k\ge1}\left(1+\frac{yzpq^{k-1}}{1-z(1-q^k)}\right)
\tag 2.3
$$
To be explicit, the coefficient of $z^ny^k$ in $F(z,y)$
is the probability that
$n$ random variables have $k$ left-to-right maxima.
Observe that, as it is to be expected,
$F(z,1)=\frac{1}{1-z}$, as it is then a telescoping product.
Let $f(z)=\frac{\partial F(z,y)}{\partial y}\big|_{y=1}$. It is the
generating function for the expected values $E_n$, i.e. the $E_n=
[z^n]f(z)$. Performing this differentiation we obtain
$$
f(z)=\frac{pz}{1-z}\sum_{k\ge 0}\frac{q^k}{1-z(1-q^k)},\tag 2.4
$$
which is also, by partial fraction decomposition,
$$
f(z)=p\sum_{k\ge 0}\left[\frac{1}{1-z}-\frac1{1-z(1-q^k)}\right].\tag 2.5
$$
From this the coefficients $E_n$ are easy to see, because there are only
geometric series:
$$
E_n=
[z^n]f(z)=p\sum_{k\ge 0}\left[1-\left(1-q^k\right)^n\right]\tag 2.6
$$
But, as announced earlier, apart from the factor $p$,
the asymptotic evaluation of this is well known,
and we have obtained the following result.
\proclaim{Theorem 2} The average number $E_n$ of left-to-right maxima
(strict model)
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion
$$
E_n=
p\left[\log_Qn+\frac{\gamma}{L}+\frac 12-\delta\left(\log_Qn\right)\right]
+O\big(\frac 1n\big)\tag 2.7
$$
with the periodic function $\delta(x)$ from \thetag{1.2}.
\endproclaim
Observe that the factor of the leading term, $p/\log Q=(q-1)/\log q$,
goes monotonically from 0 to 1 as $q$ varies between 0 and 1. So the
logarithmic term disappears for $q\to 0$, which is intuitively clear,
since the result of the ``random variables'' is then the sequence
$\bold{111}\dots\bold1$, with only one left-to-right maximum.
\head 3. The expectation in the loose model \endhead
Again, we are defining an appropriate ``language'' $\Cal L$ from which
a bivariate generating function $F(z,y)$ can be derived. Set\quad
$
\Cal A_k:=\bold k \{\bold 1,\dots,\bold{k-1}\}^*$,
\quad then\quad
$
\Cal L:=\Cal A_1^*\cdot\Cal A_2^*\cdot\Cal A_3^*\dots
$,\quad
and
$$
F(z,y)=\prod_{k\ge 1}\frac{1}{1-\frac{yzpq^{k-1}}{1-z(1-q^{k-1})} }=
\prod_{k\ge0}\frac{1-z(1-q^k)}{1-z+zq^k(1-py)}.\tag 3.1
$$
Therefore
$$
f(z)=\frac{\partial F(z,y)}{\partial y}\bigg|_{y=1}
=\frac{pz}{1-z}\sum_{k\ge 0}\frac{q^k}{1-z(1-q^{k+1})}
=\frac pq\sum_{k\ge 1}\left[\frac{1}{1-z}-\frac{1}{1-z(1-q^k)}\right]
\tag 3.2
$$
and
$$
E_n=[z^n]f(z)=\frac pq\sum_{k\ge 1}
\left[1-\left(1-q^k\right)^n\right].\tag 3.3
$$
By virtue of Theorem 1 we therefore obtain
\proclaim{Theorem 3} The average number $E_n$ of left-to-right maxima
(loose model)
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion
$$
E_n=
\frac pq
\left[\log_Qn+\frac{\gamma}{L}-\frac 12-\delta\left(\log_Qn\right)\right]
+O\big(\frac 1n\big)\tag 3.4
$$
with
$\delta(x)$ from Theorem 1 (and Theorem 2).
\endproclaim
The function $q\to p/q\log Q$ (the factor of the leading coefficient $\log n$)
is monotone decreasing from infinity to zero as $q$ varies from 0 to 1.
\head 4. The variance in the strict model \endhead
We start from $F(z,y)$ from equation \thetag{2.3}
and observe (following e.g. \cite{11}) that the variance
$V_n$ may be obtained by
$$
V_n=[z^n]\frac{\partial^2 F(z,y)}{\partial y^2}\bigg|_{y=1}+E_n-E_n^2.
\tag 4.1
$$
Therefore, we consider
$$
\frac{\partial^2 F(z,y)}{\partial y^2}\bigg|_{y=1}=g(z)+h(z).\tag 4.2
$$
We use Leibniz' formula to differentiate a product; then
$g(z)$ comprises all terms where different factors are differentiated once
and $h(z)$ comprises all terms where one factor is differentiated twice.
In this (easier) instance, $h(z)=0$.
$$
\aligned
g(z)&=\frac{2}{1-z}\sum_{1\le ij}\frac{1}{Q^h-1}\left(1-q^j\right)^n.\tag4.7
$$
We want to apply {\sl Rice's method}, which we cite as follows:
(compare, e.g. \cite{5}, \cite{6})
\proclaim{Lemma}
Let $\Cal C$ be a curve surrounding the points $1,2,\dots,n$
in the complex plane and let $f(z)$ be analytic inside $\Cal C$. Then
$$
\sum_{k=1}^n \binom nk \, {(-1)}^k f(k)=
-\frac 1{2\pi i} \int_{\Cal C} [n;z] f(z) dz, \tag4.8
$$
where
$$
[n;z]=\frac{(-1)^{n-1} n!}{z(z-1)\dots(z-n)}=
\frac{\Gamma(n+1)\Gamma(-z)}{\Gamma(n+1-z)}.\qed\tag4.9
$$
\endproclaim
Extending the contour of integration it turns out that
under suitable growth conditions on $f(z)$ (compare \cite5)
the asymptotic expansion
of the alternating sum is given by
$$
\sum \text {Res} \big( [n;z] f(z)\big)+\text{smaller order terms}\tag4.10
$$
where the sum is taken over all poles $z_0$
different from $1,\dots,n$.
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.
\bigskip
Therefore we rewrite the terms of \thetag {4.7} as alternating sums.
$$
\sum_{j\ge1}j\left[1-\left(1-q^j\right)^n\right]=
-\sum_{k=1}^n\binom nk(-1)^k\sum_{j\ge 1}jq^{jk}=
\sum_{k=1}^n\binom nk(-1)^k\varphi(z)
\tag 4.11
$$
with
$$
\varphi(z)=-\frac{Q^z}{(Q^z-1)^2}.\tag4.12
$$
The other sum from \thetag {4.7} is
$$
\sum_{j\ge1}\sum_{h>j}\frac{1}{Q^h-1}\left(1-q^j\right)^n
=\sum_{k=0}^n\binom nk(-1)^k\sum_{h>j\ge 1}\frac{1}{Q^h-1}Q^{-jk}
=\sum_{k=0}^n\binom nk(-1)^k\psi(k),
\tag4.13
$$
with
$$
\psi(z)
=\sum_{m\ge1}\sum_{h>j\ge 1}Q^{-hm-jz}
=\sum_{m,s,j\ge1}Q^{-sm-jm-jz}
=\sum_{m\ge1}\frac{1}{Q^m-1}\cdot\frac{1}{Q^{m+z}-1}.
\tag 4.14
$$
Now we turn to the computation of the residues and concentrate first on
\thetag {4.11}. There is a triple pole at $z=0$ and double poles at
$z=2k\pi i/L$, $k\in\Bbb Z$, $k\ne 0$.
An easy computation gives the local expansion at $z=0$;
$$
-[n;z]\frac{Q^z}{(Q^z-1)^2}\sim\frac{1}{L^2z^3}
\left(1-\frac{L^2z^2}{12}\right)
\left(1+zH_n+z^2\frac{H_n^2+H_n^{(2)}}{2}\right)\tag4.15
$$
and thus the residue is
$$
\frac{1}{L^2}
\left(-\frac{L^2}{12}+\frac{H_n^{2}}{2}+\frac{H_n^{(2)}}{2}\right).
\tag4.16
$$
The computations for the double poles $z=\chi_k$ are similar and we
just give the results that are collected into the 2 periodic functions
$\delta_1(x)$ and $\delta_2(x)$.
The contribution of the other sum is only $O(n^{-1})$. Using the expansion
$H_n\sim\log n+\gamma$, we have
$$
g_n\sim p^2\bigg(\log_Q^2n+\frac{2\gamma}{L}\log_Qn+\frac{\gamma^2}{L^2}
+\frac{\pi^2}{6L^2}-\frac16
+\log_Qn\cdot\delta_1\left(\log_Qn\right)+\delta_2\left(\log_Qn\right)
\bigg),
\tag4.17
$$
with \quad
$
\delta_1(x)=-2\delta(x)$\quad and \quad$\displaystyle{
\delta_2(x)=\frac{2}{L^2}\sum_{k\ne 0}\Gamma'\!\left(-\chi_k\right)
e^{2k\pi ix} }$.
Now, for the variance $V_n$, we must collect $g_n+E_n-E_n^2$. After some
simplifications we obtain
\proclaim{Theorem 4}The variance $V_n$ of the number of
left-to-right maxima
(strict model)
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion for $n\to\infty$
$$
V_n=pq\log_Qn+p^2\left(-\frac5{12}+\frac{\pi^2}{6L^2}-\frac\gamma L
-\left[\delta^2\right]_0\right)
+p\left(\frac\gamma L+\frac12\right)+ \delta_3(\log_Qn)+O\big(\frac 1n
\big)\tag4.18
$$
Here, $\left[\delta^2\right]_0$ is the mean of the square of $\delta^2(x)$, a very
small quantity that can be neglected for numerical purposes. Furthermore,
$\delta_3(x)$ is a periodic function with mean 0; its Fourier
coefficients
could be described if needed.
\endproclaim
The function $q\to pq/\log Q$ goes monotonically from 0 to 1 as $q$
varies between 0 and 1.
\head 5. The variance in the loose model \endhead
We start from $F(z,y)$ from equation \thetag{3.3}
and observe that the variance
$V_n$ may be obtained by
$$
V_n=[z^n]\frac{\partial^2 F(z,y)}{\partial y^2}\bigg|_{y=1}+E_n-E_n^2.
\tag 5.1
$$
Therefore we consider
$$
\frac{\partial^2 F(z,y)}{\partial y^2}\bigg|_{y=1}=g(z)+h(z).\tag5.2
$$
$g(z)$ comprises all terms where different factors are differentiated once
and $h(z)$ comprises all terms where one factor is differentiated twice.
This gives
$$
g(z)=\frac{2p^2}{q^2}\frac{z^2}{1-z}\sum_{1\le i