%This is an AmS-TeX file
%producing 9 pages of output

\input amstex
\documentstyle{amsppt}



\NoRunningHeads


\TagsOnRight
\NoBlackBoxes
\define\lk{[\! [}
\define\[{[\! [}
\define\rk{]\! ]}
\define\]{]\! ]}

\topmatter
\title
combinatorial problems related to geometrically distributed random variables
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address 
\flushpar TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\email proding\@rsmb.tuwien.ac.at
\endemail







\endtopmatter
\redefine\P{\Bbb P}
\document

\head 1. Introduction \endhead

Motivated from Computer Science problems we consider the following situation
(compare \cite2 and \cite3). In these papers the reader will find a
more complete
description as well as additional references.

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$. Assume that we have
$n$
independent random variables $X_1,\dots,X_n$ according to this distribution.

The first parameter of interest is the {\sl number of 
left-to-right maxima\/},
where we say that $X_i$ is a left-to-right maximum (in the strict sense)
if it is strictly larger than the elements to left. A left-to-right maximum 
in the loose sense is defined analogously but ``larger'' is replaced by
``larger or equal''.

The second parameter of interest is the {\sl (horizontal) path length\/},
i.e. the sum of the left-to-right maxima in the loose sense of all the
sequences $X_i,\dots,X_n$, where $i$ is running from 1 to $n$.

{\bf Example.} Consider the sequence $4,5,2,3,5$. It has 2 
left-to-right maxima in the strict sense (4--5) and
3 left-to-right maxima in the loose sense (4--5--5).
For the path length we must consider the subsequences
$$\align
&4,5,2,3,5\\
&5,2,3,5\\
&2,3,5\\
&3,5\\
&5
\endalign
$$
with respectively $3, 2, 3, 2, 1$ left-to-right maxima. Therefore the
path length is $3+2+3+2+1=11$.

\head{2. Left-to-right maxima in the strict sense}\endhead

We can find a probability generating function by considering an 
appropriate ``language''.

The ``letters'' will be denoted 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}\}^*.
$$
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 
$$
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)
$$
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)=\dfrac{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 are led to
$$
f(z)=\frac{pz}{1-z}\sum_{k\ge 0}\frac{q^k}{1-z(1-q^k)},
$$
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].
$$
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]
=p\sum_{k=1}^n\binom nk(-1)^{k-1}\frac{1}{1-q^k}
$$

The asymptotic evaluation of such an alternating sum is conveniently
performed by {\sl Rice's method\/}, which we cite as a lemma.

\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, 
$$
where
$$
[n;z]=\frac{(-1)^{n-1} n!}{z(z-1)\dots(z-n)}=
\frac{\Gamma(n+1)\Gamma(-z)}{\Gamma(n+1-z)}=B(n+1,-z).\qed
$$
\endproclaim

Extending the contour of integration it turns out that 
under suitable growth conditions on $f(z)$ 
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$. 
 
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

\proclaim{Theorem 1} 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)
$$
where $Q=q^{-1}$,
$L=\log Q$, $\gamma$ is Euler's constant and $\delta$ is a periodic function
of period 1, mean zero and small amplitude. Its Fourier series is 
given by
$$
\delta(x)=\frac{1}{L}\sum_{k\ne 0}\Gamma\left(-\chi_k\right)
e^{2k\pi ix}.
$$
\endproclaim

The variance can also be computed, by considering the second derivative
of $F(z,y)$ with respect to $y$. 

\proclaim{Theorem 2}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_1(\log_Qn)+O\big(\frac 1n
\big).
$$
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_1(x)$ is a periodic function with mean 0; its Fourier
coefficients
could be described if needed.
\endproclaim


\head{3. Left-to-right maxima in the loose sense}\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-\dfrac{yzpq^{k-1}}{1-z(1-q^{k-1})} }=
\prod_{k\ge0}\frac{1-z(1-q^k)}{1-z+zq^k(1-py)}.
$$
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]
$$
and
$$
E_n=[z^n]f(z)=\frac pq\sum_{k\ge 1}
\left[1-\left(1-q^k\right)^n\right].
$$

\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).
$$
\endproclaim


\proclaim{Theorem 4}The variance $V_n$ of the number of 
left-to-right maxima
(loose model)
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion for $n\to\infty$
$$
V_n=\frac{p}{q^2}\log_Qn+
\frac{p^2}{q^2}\left(-\frac5{12}+\frac{\pi^2}{6L^2}+\frac\gamma L-\frac 2L
-\left[\delta^2\right]_0\right)
+\frac pq\left(\frac\gamma L-\frac12\right)+ \delta_2(\log_Qn)+O\big(\frac 1n
\big).
$$
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_2(x)$ is a periodic function with mean 0; its Fourier
coefficients
could be described if needed.
\endproclaim

\head 4. Path length  \endhead


If we denote the path length of a ``word'' $\omega$ by $a(\omega)$, then
we have the following recursion formula
$$
a(\omega)=a(\rho m \sigma)=a(\rho)+a( \sigma)+1 +|\rho|
$$
with $\rho\in\{\bold 1,\dots,\bold m\}^*$ and $\sigma\in\{\bold 1,\dots,
\bold m-1\}^*$.
From this we get a functional equation for the generating functions.
(The upper index `$=m$' e.g. refers to all sequences where the maximal
element is $m$.)
$$
P^{=m}(z,y)=pq^{m-1}zyP^{\le m}(zy,y)P^{<m}(z,y)
$$
It is not likely that this formidable equation can be solved explicitly.
However it contains enough information to obtain the generating functions
for the expectations (and the variance, too).
For the expectation we have to differentiate
 with respect to $y$ and then set
$y=1$. Denoting the corresponding functions by
$F^*(z)$, we get
$$\align
\frac{F^{=m}(z)}{pq^{m-1}z}&=P^{\le m}(z,1)P^{<m}(z,1)\\ &
+\left[z\frac{\partial }{\partial z}P^{\le m}(z,1)+F^{\le m}(z)\right]
P^{<m}(z,1)
+P^{\le m}(z,1)F^{<m}(z).\endalign
$$
Since
$\quad
P^{\le m}(z,1)=\dfrac{1}{1-z(1-q^m)}=:\dfrac{1}{{\lk}m{\rk}}\quad
$
and
$\quad
\dfrac{\partial }{\partial z}P^{\le m}(z,1)=\dfrac{1-q^m}{{\lk}m{\rk}^2},
\quad
$
we obtain
$$
F^{\le m}(z)
{\lk}m{\rk} ^2=
F^{<m}(z)
{\lk}m-1{\rk}^2+
\frac{pq^{m-1}z}{{\lk}m{\rk}},
$$
which we can solve by iteration:
$$
F^{\le m}(z)=\frac{p}{q}\frac z
{{\lk}m{\rk}^2}\sum_{i=1}^m
\frac{q^{i}}{{\lk}i{\rk}}
$$
The limit for $m\to\infty$ is the generating function for the expectations:
$$
F(z)=\frac pq\frac z
{(1-z)^2}\sum_{i\ge1}
\frac{q^i}{{\lk}i{\rk}}
$$
From this it is easy to get the coefficients $E_n$
$$
E_n=[z^n]F(z)=\frac pq
\sum_{k=2}^{n+1}\binom{n+1}k(-1)^k\frac{1}{Q^{k-1}-1}
$$

\proclaim{Theorem 5}  The expected path length $E_n$ 
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion
$$
E_n=(Q-1)n\Big(\log_Qn+\frac{\gamma-1}{L}-\frac12+\frac 1L
\delta_3(\log_Qn)\Big)+O(\log n)
$$
with
$\qquad
\delta_3(x)=\sum\limits_{k\ne0}\Gamma(-1-\frac{2k\pi i}{L})e^{2k\pi ix}.
$
\endproclaim

To deal with the variance, we have to differentiate the functional equation
twice.
Denoting the resulting generating function by $H(z)$, we finally find
$$
\aligned
&{H(z)}
={2\frac pq}\frac z{(1-z)^2}\sum_{i\ge1}\frac{q^{i}}{{\lk}i{\rk}^2}\\
&-{2\frac pq}\frac z{(1-z)^2}\sum_{i\ge1}\frac{q^{i}}{{\lk}i{\rk}}\\
&-{2\big(\frac pq\big)^2}\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}\frac{q^{i+j}}{{\lk}i{\rk}{\lk}j{\rk}}\\
&+4\big({\frac pq}\big)^2\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}
\frac{q^{i+j}}{{\lk}i{\rk}^2{\lk}j{\rk}}\\
&+{2\big(\frac pq\big)^2}\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}\frac{q^{i+j}
}{{\lk}i{\rk}{\lk}j{\rk}^2}\\
&+{2\big(\frac pq\big)^2} \frac{z^2}{(1-z)^2}\sum_{1\le j<i}\frac{q^{i+j}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}}\\
&+2\big(\frac {p}q\big)^3\frac{z^3}{(1-z)^2}
\sum_{i\ge1}\sum_{1\le j\le i}\sum_{1\le h<i}
\frac{q^{i+j+h}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}{\lk}h{\rk}}
\endaligned
$$
To get the coefficient of $z^n$ in an efficient way we use to following
principle (used recently by Flajolet and Richmond).

$$
A(z)=\sum_{n\ge 0}a_nz^n\longleftrightarrow
\frac{1}{1-w}A\Big(\frac{w}{1-w}\Big)=
\sum_{n\ge0}\bigg(
\sum_{k=0}^n\binom nk a_k\bigg) w^n
$$
Of course this relation can be inverted to read
$$
A(z)=\sum_{n\ge0}\bigg(
\sum_{k=0}^n\binom nk (-1)^kf(k)\bigg) z^n\longleftrightarrow
\frac{1}{1-w}A\Big(\frac{w}{w-1}\Big)=\sum_{n\ge 0}f(n)w^n.
$$

That means that if we find the coefficients in the ``$w$--world''
we {\sl automatically\/} have the coefficients in the ``$z$--world''
as {\sl alternating sums\/}!

This is especially convenient, since the expressions become nicer
if we substitute $z=\dfrac w{w-1}$, because $
\dfrac{1}{\[i\]}=\dfrac{1-w}{1-wq^i}
$.

Consider as an example the 
first one, namely\quad
$\displaystyle{
A(z)=\frac{z}{(1-z)^2}\sum_{i\ge 1}\frac{q^i}{\[i\]^2}}$.\newline

\flushpar
We easily find that
$$
\frac{1}{1-w}A\Big(\frac{w}{w-1}\Big)=-(1-w)^2\sum_{i\ge1}
\frac{wq^i}{\big(1-wq^i\big)^2}.
$$
Let us forget the extra factor $-(1-w)^2$ for a moment. We find for
$n\ge1$
$$
[w^n]\sum_{i\ge1}
\frac{wq^i}{\big(1-wq^i\big)^2}=
\sum_{i\ge1}q^{in}\cdot [w^n]\frac{w}{(1-w)^2}=\frac{n}{Q^n-1}.
$$
But because $(1-w)^2=\dfrac{w^2}{z^2}$, the extra factor just works as
a {\sl shift\/} on both sides, so that we find
\flushpar{\bf Sum 1.}
$$
[z^n]\frac{z}{\left(1-z\right)^2}
\sum _{i\ge1}
\frac{q^{i}}{{\lk}i{\rk}^2}
=-\sum_{k=3}^{n+2}\binom{n+2}k(-1)^k\frac{k-2}{Q^{k-2}-1}
$$






In this way we find for the coefficients of $z^n$ in the
other sums in $H(z)$ the following expressions as alternating sums.

\flushpar
{\bf Sum 2.}
$$
[z^n]\frac{z}{\left(1-z\right)^2}
\sum _{i\ge1}
\frac{q^{i}}{{\lk}i{\rk}}
=\sum_{k=2}^{n+1}\binom{n+1}k(-1)^k\frac{1}{Q^{k-1}-1}
$${\bf Sum 3.}
$$
[z^n]\frac{z^2}{\left(1-z\right)^2}
\sum _{1\le j\le i}
\frac{q^{i+j}}{{\lk}i{\rk}{\lk}j{\rk}}
=-\sum_{k=3}^{n+1}\binom{n+1}k(-1)^k\frac{1}{Q^{k-1}-1}
\left[k-2+\sum_{m=1}^{k-2}\frac{1}{Q^m-1}
\right]
$${\bf Sum 4.}
$$
[z^n]\frac{z^2}{\left(1-z\right)^2}
\sum _{1\le j\le i}
\frac{q^{i+j}}{{\lk}i{\rk}^2{\lk}j{\rk}}
=\sum_{k=4}^{n+2}\binom{n+2}k(-1)^k\frac{1}{Q^{k-2}-1}
\left[\binom{k-2}2+\sum_{m=1}^{k-3}\frac{m}{Q^m-1}
\right]
$${\bf Sum 5.}
$$
\gather
[z^n]\frac{z^2}{\left(1-z\right)^2}
\sum _{1\le j\le i}
\frac{q^{i+j}}{{\lk}i{\rk}{\lk}j{\rk}^2}\\
=\sum_{k=4}^{n+2}\binom{n+2}k(-1)^k\frac{1}{Q^{k-2}-1}
\left[\binom{k-2}2+(k-2)\sum_{m=1}^{k-3}\frac{1}{Q^m-1}
-\sum_{m=1}^{k-3}\frac{m}{Q^m-1}
\right]
\endgather
$$
{\bf Sum 6.}
$$
[z^n]\frac{z^2}{\left(1-z\right)^2}
\sum _{1\le j<i}
\frac{q^{i+j}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}}
=\sum_{k=4}^{n+2}\binom{n+2}k(-1)^k\frac{k-3}{(Q-1)\left(Q^{k-2}-1\right)}
$${\bf Sum 7.}
$$
\gather
[z^n]\frac{z^3}{\left(1-z\right)^2}
\sum \Sb i\ge1\\1\le j\le i\\1\le h<i \endSb
\frac{q^{i+j+h}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}{\lk}h{\rk}}\\
=-\sum_{k=5}^{n+2}\binom{n+2}k(-1)^k\frac{1}{(Q-1)\left(Q^{k-2}-1\right)}
\left[\binom{k-3}2+\frac{k-4}{Q-1}+
\sum_{m=2}^{k-3}\frac{m-2}{Q^m-1}
\right]
\endgather
$$

This gives finally the following result:
\proclaim{Theorem 6} The variance $V_n$ of the 
path length 
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion
$$
\aligned
V_n&=(Q-1)^2n^2\Bigg\{
\frac{Q+1}{2(Q-1)L}
+\frac{1}{L^2}-\frac{\pi^2}{6L^2}
+\frac{8\pi^2}{L^2}h\Big(\frac{4\pi^2}{L}\Big)-\alpha_1+
\delta_4(\log_Qn)\Bigg\}\\
& +O\big(n^{1+\varepsilon}\big),\qquad \varepsilon>0,
\endaligned
$$
where $\displaystyle{
h(x)=\sum_{k\ge1}\frac{e^{kx}}{\big(e^{kx}-1\big)^2}
}$,\ 
$\displaystyle{
\alpha_1=L\sum_{k\ge1}\frac{1}{k(L^2+4k^2\pi^2)\sinh (2k\pi^2/L)}}$
and
 $\delta_4(x)$ is again  continuous, periodic of period 1 and mean zero.
\endproclaim

Both, $h(\cdot)$ and $\alpha_1$ are very small quantities, so that a
less accurate but more readible formula is
$$
V_n\sim(Q-1)^2n^2\bigg\{
\frac{Q+1}{2(Q-1)L}
+\frac{1}{L^2}-\frac{\pi^2}{6L^2}
\bigg\}.
$$

\head 5. A combinatorial interpretation of Euler's partition identities
\endhead

The identities in question are (compare \cite{1})
$$
\prod_{n\ge0}\big(1+tq^n\big)=\sum_{n\ge0}\frac{t^nq^{\binom n2}}{Q_n(q)}
$$
and
$$
\prod_{n\ge0}\frac 1{1-tq^n}=\sum_{n\ge0}\frac{t^n}{Q_n(q)},
$$
where
$$
Q_n(q)=\big(1-q^{1}\big)\big(1-q^{2}\big)\dots\big(1-q^{n}\big).
$$
Now consider
$$
\Bbb P\big\{X_1<\dots<X_n\big\}
$$
and its generating function
$$
M_{<}(z)=\sum_{n\ge0}\Bbb P\big\{X_1<\dots<X_n\big\}z^n
$$
resp. the analogous quantities
$$
\Bbb P\big\{X_1\le\dots\le X_n\big\}
$$
and 
$$
M_{\le}(z)=\sum_{n\ge0}\Bbb P\big\{X_1<\dots<X_n\big\}z^n.
$$
Then we can set up appropriate languages
$$
\Cal M_{<}=\big(\varepsilon+\bold 1\big)\big(\varepsilon+\bold 2\big)\dots
$$
and
$$
\Cal M_{\le}=\bold1^\ast\cdot\bold2^\ast\dots,
$$
so that
$$
M_{<}(z)=\prod_{k\ge1} \big(1+pq^{k-1}z\big)
$$
resp.
$$
M_{\le}(z)=\prod_{k\ge1}\frac{1}{1-pq^{k-1}z}.
$$
Using the identities we can further write
$$
M_{<}(z)=\prod_{k\ge0} \big(1+pq^{k}z\big)=
\sum_{n\ge0}\frac{p^nz^nq^{\binom n2}}{Q_n(q)}
$$
and
$$
M_{\le}(z)=\prod_{k\ge0}\frac{1}{1-pq^{k}z}=
\sum_{n\ge0}\frac{p^nz^n}{Q_n(q)},
$$
so that we have the {\sl explicit\/} formul\ae
$$
\Bbb P\big\{X_1<\dots<X_n\big\}=\frac{p^nq^{\binom n2}}{Q_n(q)}
$$
and
$$
\Bbb P\big\{X_1\le\dots\le X_n\big\}=\frac{p^n}{Q_n(q)}.
$$






\Refs


\ref \no1 \by G.~Andrews\book The Theory of Partitions\publ Addison-Wesley
\publaddr Reading, Mass. \yr 1976
\endref


\ref \no 2
\paper The path length of random skip lists
\jour Acta Informatica \by P.~Kirschenhofer and {H.~Prodinger} 
\yr 1994\vol 31\pages 775--792
\endref

\ref \no 3  \by H.~Prodinger\paper
Combinatorics of 
geometrically distributed random variables: Left-to-right maxima
\jour 5th conference on Formal Power Series and Algebraic
Combinatorics, Firenze (Discrete Mathematics, to appear) \yr 1993 \endref



\endRefs







\enddocument

