\documentclass[12pt]{amsart}%{article}
\usepackage{a4ams}
\usepackage{amsfonts,amsmath,amssymb}

\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}
\numberwithin{equation}{section}

\def\Prob{\mathbb{P}}
\def\eps{\varepsilon}

\newcommand{\Res}[2]{\mathop{\textrm{Res}}\nolimits\left.#2\right|_{#1}}
                                                   % 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}}
\newcommand{\loq}{\log_{\frac1q}}
% other useful commands


\newcommand{\etal}{\emph{et al\@.}\xspace}
\newcommand{\key}[1]{\mathbf{#1}}
\renewcommand{\th}[1]{\ensuremath{#1^{\text{th}}}}
\newcommand{\Leaf}{\qedsymbol}

\title[Run statistics]
{Combinatorics of geometrically distributed random
variables: Run statistics}

\author[P. J. Grabner]{Peter J. Grabner$^\dag{}$}
\address{Peter Grabner\\
Institut f\"ur Mathematik A\\
Technische Universit\"at Graz\\
Steyrergasse 30\\
8010 Graz\\
Austria}
\email{grabner@weyl.math.tu-graz.ac.at}
\thanks{$^\dag{}$This author is supported by the START-project Y96-MAT of the
Austrian Science Foundation}
\thanks{ Part of this work was done during the first author's visit to the
Centre for Applicable Analysis and Number Theory at the University of the
Witwatersrand, Johannesburg, South Africa}


\author[A. Knopfmacher]{Arnold Knopfmacher}
\address{Arnold Knopfmacher\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\
Department of Computational and Applied Mathematics\\
University of the Witwatersrand, P.~O. Wits\\ 
2050 Johannesburg, South Africa}
\email{arnoldk@gauss.cam.wits.ac.za}


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


\date{\today}
\subjclass{Primary: 05A15; Secondary: 60C05}
\keywords{geometric random variables, generating function, limiting
  distribution, runs, quasi-power theorem}

\begin{document}
\begin{abstract}
For words of length $n$, generated by independent geometric random variables,
we consider the mean and variance, and thereafter the distribution of the
number of runs of equal letters in the words. In addition, we consider the
mean length of a run as well as the length of the longest run over all words
of length $n$.
\end{abstract}


\maketitle

\section{Introduction}
\label{sec:intro}
Let $X$ denote a geometrically distributed random variable, i.~e.
$\mathbb{P}\{X=k\}=pq^{k-1}$ for $k\in\mathbb{N}$ and $q=1-p$. The
combinatorics of $n$ geometrically distributed independent random variables
$X_1,\ldots,X_n$ has attracted recent interest, especially because of
applications in computer science. We mention just two areas, the skip list
\cite{Devroye92,PaMuPo92,Pugh90,KiPr94} and probabilistic counting
\cite{FlMa85,KiPr90,KiPr93,KiPrSz96}.

In \cite{Prodinger96c} the number of left-to-right maxima was investigated
for words $a_1\ldots a_n$, where the letters $a_i$ are independently
generated according to the geometric distribution. In \cite{KnPr00} the study
of left-to-right maxima was continued, but now the parameters studied were
the mean value and mean position of the $r$-th maximum.

In this article we study runs of consecutive equal letters in a string
of $n$ geometrically distributed independent random letters. For example
in $w=22211114431$ we have $5$ runs of equal letters of respective lengths
$3,4,2,1,1$. In the sequel we denote by $R_n(w)$ the number of runs in the
word $w$, where $w$ is of length $n$.

In section~\ref{sec:mom} we study the mean and variance of $R_n$.
Thereafter, in section~\ref{sec:distr} we
study the distribution of the number of runs, which turns out to be Gaussian.
Subsequently, in section~\ref{sec:length} we study the average length of the
runs per word. Finally, in section~\ref{sec:max} we determine the mean and
variance of the length of the longest run in a word of length $n$.
The treatment follows to some extent the classical paper \cite{Knuth78};
compare also \cite{GuOd80} for such longest run statistics in a slightly
different context.


\section{Moments of number of runs}
\label{sec:mom}              
In order to determine the mean and variance of the number of runs
we will make use of the following decomposition of the set of all (non-empty)
words. Here $\{\ge\mathbf{k}\}$ denotes the set $\{k,k+1,\ldots\}$; for a
given set $A$ we denote
\begin{equation*}
A^+=\bigcup_{k=1}^\infty A^k,\quad A^\ast=\eps\cup A^+,
\end{equation*}
where $\eps$ stands for the empty word.
We decompose the set of non-empty words according to runs of $1$'s, separated
by words consisting of larger  digits only
\begin{equation}\label{eq:decomp}
\{\ge \mathbf{1}\}^+=(\eps+\mathbf{1}^+)\bigl(\{\ge \mathbf{2}\}^+
\mathbf{1}^+\bigr)^\ast\{\ge \mathbf{2}\}^+(\eps+\mathbf{1}^+)+
\mathbf{1}^+~;
\end{equation}
here we find it more convenient to write $+$ instead of $\cup$.

We consider a probability generating function $F(z,u)$, where
$z$ labels the length of the word, and $u$ counts the number of runs.
We should always have $F(z,1)=\frac z{1-z}$, and a replacement
of $z$ by $qz$, if we increase all letters by 1.

Then \eqref{eq:decomp} translates into the  functional equation
\begin{equation}\label{eq:func}
F(z,u)=\frac{F(qz,u)}{1-F(qz,u)\dfrac{pzu}{1-pz}}
\Big(\frac{pzu}{1-pz}+1\Big)^2+\frac{pzu}{1-pz}~.
\end{equation}

Now we differentiate it w.~r.~t. $u$, plug in $u=1$, set 
$G(z)=\frac{\partial }{\partial u}F(z,1)$, and get


\begin{equation*}
G(z)=G(qz)\frac{(1-qz)^2}{(1-z)^2}+\frac{pz(1-pz)}{(1-z)^2}~.
\end{equation*}

Setting $H(z)=(1-z)^2G(z)$ yields
\begin{equation*}
H(z)=H(qz)+{pz(1-pz)}~.
\end{equation*}
Comparing coefficients, we see that
\begin{align*}
[z]H(z)&=1~,\\
[z^2]H(z)&=-\frac{p^2}{1-q^2}=-\frac{p}{1+q}~,
\end{align*}
and that the other coefficients are zero. Consequently,
\begin{equation*}
H(z)=z-\frac{p}{1+q}{z^2}~,
\end{equation*}
and
\begin{equation*}
G(z)=\frac{z-\frac{p}{1+q}z^2}{(1-z)^2}~.
\end{equation*}
This leads to
\begin{prop}\label{prop:mu}
The mean value of the number of runs for $n\ge1$ is given by
\begin{equation*}
\mu_n=\mathbb{E}R_n=[z^n]G(z)=\frac{2q}{1+q}n+\frac{p}{1+q}.
\end{equation*}
\end{prop}


Now that we see such a simple result, we are tempted to look for a
simple proof as well. Indeed, since the expectation is additive,
we have $n-1$ times the expectation of having unequal digits
at two adjacent random variables, plus $1$. This expectation is given by

\begin{equation*}
\sum_{i\not=j}pq^{i-1}\, pq^{j-1}=\frac{2q}{1+q}.
\end{equation*}
Then the expected number of runs is given by
\begin{equation*}
(n-1)\frac{2q}{1+q}+1=\frac{2q}{1+q}n+\frac{p}{1+q}.
\end{equation*}

If we want to compute the variance, such a simple argument seems to be
out of reach. Henceforth, we differentiate \eqref{eq:func}
twice, and use the notation $V(z)=\frac{\partial ^2}{\partial u^2}F(z,1)$.

We see
\begin{align}
\begin{split}
V(z)&=V(qz)\frac{(1-qz)^2}{(1-z)^2}+\frac{8q^2}{(1+q)^2(1-z)^3}+
\frac{8pq^2z^2}{(1+q)^2(1-z)^2}\\
&+\frac{4p^2qz^2}{(1+q)(1-z)^2}+\frac{2p^3qz^3}{(1+q)^2(1-z)^2}-
\frac{8q^2}{(1+q)^2(1-qz)(1-z)^2}
\end{split}
\end{align}
or, with $W(z)=(1-z)^2V(z)$,
\begin{align*}
W(z)&=W(qz)+\frac{8q^2}{(1+q)^2(1-z)}+
\frac{8pq^2z^2}{(1+q)^2}\\
&+\frac{4p^2qz^2}{(1+q)}+\frac{2p^3qz^3}{(1+q)^2}-
\frac{8q^2}{(1+q)^2(1-qz)}~.
\end{align*}
From this we see that (with $w_n:=[z^n]W(z)$) for $n\ge4$, 
\begin{equation*}
w_n=q^nw_n+\frac{8q^2}{(1+q)^2}\big[1-q^n\big]~,
\end{equation*}
or
\begin{equation*}
w_n=\frac{8q^2}{(1+q)^2}~.
\end{equation*}
Furthermore we see that
\begin{equation*}
w_0=w_1=0,\quad
w_2=\frac{4q}{1+q},\quad \text{and }\quad
w_3=\frac{2q(1+q+4q^2)}{(1+q)(1+q+q^2)}~.
\end{equation*}
Hence
\begin{equation*}
V(z)=\frac{4q}{1+q}\frac{z^2}{(1-z)^2}+
\frac{2q(1+q+4q^2)}{(1+q)(1+q+q^2)}\frac{z^3}{(1-z)^2}
+\frac{8q^2}{(1+q)^2}\frac{z^4}{(1-z)^3}
\end{equation*}
and
\begin{equation*}
[z^n]V(z)=\frac{4q^2}{(1+q)^2}(n-2)(n-3)+
\frac{2q(1+q+4q^2)}{(1+q)(1+q+q^2)}(n-2)+\frac{4q}{1+q}(n-1).
\end{equation*}
Adding the expectation and subtracting the square of the expectation, we
obtain the variance.


\begin{prop}\label{prop:sigma}
The variance of the number of runs is given for $n\ge2$
by
\begin{equation*}
\sigma^2_n=\mathbb{V}R_n=\frac{2q(1-q)^2(2+q^2)}{(1+q)^2(1-q^3)}n-
\frac{2q(1-q)^2(3-q+q^2)}{(1+q)^2(1-q^3)}~.
\end{equation*}
\end{prop}

It is a folklore result that the limit $q\to1$ maps the model of words,
generated by geometrically distributed random variables to 
the model of random
permutations. For permutations, there are obviously $n$ runs, and
the expected value confirms that, with the variance being exactly zero, 
as it should.


\section{Distribution of the number of runs}\label{sec:distr}
In this section we prove a central limit theorem for the distribution of the
number of runs. In order to do this, we have to extract further information
from the functional equation \eqref{eq:func}. We observe that the terms
on the right-hand side are all simple rational functions, except for the terms
containing $F(qz,u)$. From the definition of $F(z,u)$ it is clear that $F(z,u)$
can be written as
$$F(z,u)=\sum_{n\geq1}z^nf_n(u)$$
for polynomials $f_n(u)$ with $\deg f_n=n$, whose coefficients are positive and
$\leq1$. Therefore we have
\begin{equation}
  \label{eq:fn}
  |f_n(u)|\leq\frac{|u|^{n+1}-1}{|u|-1},\quad\text{for }|u|>1.
\end{equation}

Using $q<1$ and \eqref{eq:fn} we obtain that $F(qz,u)$ is holomorphic in
$|z|<\frac1{\sqrt q}$, $|u|<\frac1{\sqrt q}$. Since for $u=z=1$ we have
$$1-F(q,1)\frac p{1-p}=0,\quad\text{and }
\left.\frac{\partial}{\partial z}\left(1-F(qz,u)\frac{pzu}{1-pz}\right)
\right|_{z=1,u=1}\not=0$$
there exists a function $f(u)$ holomorphic in a neighbourhood of $u=1$ such
that $z=f(u)^{-1}$ solves
$$1-F(qz,u)\frac{pzu}{1-pz}=0$$
and satisfies $f(1)=1$. Furthermore, $|f(e^{it})|<1$ for $0<|t|<\eps$ for some
$\eps>0$ by an application of Rouch\'e's theorem. Thus we can write 
\begin{equation}
  \label{eq:Fzu}
  F(z,u)=\frac{g(z,u)}{1-f(u)z}+R(z,u),
\end{equation}
where $g(z,u)$ and $R(z,u)$ are holomorphic in $|z|<1+\delta$, $|u-1|<\delta$
for some $\delta>0$. Now we are in the general framework of Hwang's quasi-power
theorem (cf.~\cite{Hwang98}) and can deduce the following theorem.
\begin{theorem}\label{thm:runs}
The number of runs in words of length $n$ produced by independent geometric
random variables obeys a central limit law, more precisely
\begin{equation}
  \label{eq:central}
  \mathbb{P}\left(R_n\leq
  \frac{2q}{1+q}n+
  t\sqrt{\frac{2q(2+q^2)}{1-q^3}}\frac{1-q}{1+q}\sqrt{n}\right)=\Phi(t)+
  \mathcal{O}(n^{-\frac12});
\end{equation}
the error term is uniform in $t$.
\end{theorem}

\section{Average length of runs}\label{sec:length}
Given a string $w$ of geometric random variables of length $n$ with $k$ runs
we define the average length of a run to be $L_n(w)=\frac nk$. It is of
interest to determine the moments and the distribution of this parameter over
all strings of length $n$. Intuitively, one expects that the mean length of a
run should be close to $n$ divided by the mean number of runs, which is
\begin{equation*}
\frac{n}{\frac{2q}{1+q}n+\frac{p}{1+q}}=\frac{1+q}{2q}-
\frac{1-q^2}{4q^2}\frac1n+\mathcal{O}\big(\frac1{n^2}\big).
\end{equation*}
In fact we obtain
\begin{prop}\label{length}
For $n\geq1$ the mean and variance of $L_n$ are given respectively by
\begin{equation*}
\frac{1+q}{2q}+\mathcal{O}(\frac1n),\quad
\frac{(1-q^2)^2(2+q^2)}{8q^3(1-q^3)}\frac1n+\mathcal{O}(\frac1{n^2}).
\end{equation*}
Moreover, $L_n$ obeys a central limit theorem:
\begin{equation*}
\Prob\left(L_n-\frac{1+q}{2q}\leq\frac{(1-q^2)\sqrt{2+q^2}}
{\sqrt{8q^3(1-q^3)}}\frac t{\sqrt{n}}\right)=\Phi(t)+
\mathcal{O}(n^{-\frac12}).
\end{equation*}
\end{prop}
\begin{proof}
The proof will make use of the distribution obtained for the number of
runs in Theorem~\ref{thm:runs}. We first write $R_n=\mu_n+\sigma_nX_n$, where
$X_n$ is a sequence of random variables with asymptotically normal
distribution, and $\mu_n$ and $\sigma_n$ are given by
Propositions~\ref{prop:mu},~\ref{prop:sigma}. Then we can write
\begin{equation}\label{eq:taylor}
\frac n{R_n}=\frac n{\mu_n}\frac1{1+\frac{\sigma_n}{\mu_n}X_n}=
\frac n{\mu_n}-\frac{n\sigma_n}{\mu_n^2}X_n+
\mathcal{O}\left(\frac{n\sigma_n^2}{\mu_n^3}|X_n|^2\right).
\end{equation}
We observe that by \eqref{eq:central} and
$1-\Phi(t)\sim\frac1{\sqrt{2\pi}x}\exp(-\frac{x^2}2)$ (cf.~\cite{Feller50})
we have
$$\Prob\left(|X_n|>\log n\right)=\mathcal{O}(n^{-\frac12}).$$
This gives an error term of $\mathcal{O}(n^{-1}\log n)$ in \eqref{eq:taylor}
and yields the desired result.
\end{proof}

\section{Longest runs}\label{sec:max}
In this section we study the mean of the longest run $M_n$ of
equal digits in a string of length $n$. For this purpose we introduce the
probability generating function $G_h$ of all strings that have runs only of
length less than $h$. Similar arguments as in the proof of \eqref{eq:func} show
that $G_h$ satisfies
\begin{equation}
  \label{eq:hfunc}
  G_h(z)=\left(\frac{1-(pz)^h}{1-pz}\right)^2
\frac{G_h(qz)}{1-G_h(qz)\frac{pz}{1-pz}\left(1-(pz)^{h-1}\right)}+
pz\frac{1-(pz)^{h-1}}{1-pz}.
\end{equation}
In order to extract the asymptotic behaviour of the probability that a string
of length $n$ has runs of length at most $h$, we have to find the singularities
of $G_h(z)$. We start with simple a priori estimates for the power series
coefficients of $G_h$:
\begin{equation}
  \label{eq:est}
  \frac{z}{1-z}-\frac1{(1-z)^2}\sum_{k=0}^\infty\frac{(pq^kz)^h}{1-pq^kz}
\preceq G_h(z)\preceq \frac{z}{1-z},
\end{equation}
where
$$A(z)\preceq B(z)\Leftrightarrow\forall n\in\mathbb{N}:
[z^n]A(z)\leq[z^n]B(z).$$
The left hand side of \eqref{eq:est} is obtained by subtracting all strings
which contain at least one run of $1$'s of length $\geq h$, or one run of $2$'s
of length $\geq h$, and so on; clearly this is not a disjoint union, therefore
it only gives an estimate. The upper estimate is trivial.

Now we investigate the solution of the equation
\begin{equation}
  \label{eq:rhoh}
  1-G_h(qz)\frac{pz}{1-pz}\left(1-(pz)^{h-1}\right)=0.
\end{equation}
Since all the occurring power series have positive coefficients, we could apply
Rouch\'e's theorem to conclude that the positive real root $\rho_h$ of
\eqref{eq:rhoh}  is the root of smallest modulus. Then inserting the two
estimates \eqref{eq:est} and multiplying out, we obtain
\begin{equation*}
1+q\rho_h(p\rho_h)^h\leq \rho_h\leq 1+q\rho_h(p\rho_h)^h+
\frac{p\rho_h-(p\rho_h)^h}{1-q\rho_h}
\sum_{k=1}^\infty\frac{(pq^k\rho_h)^h}{1-pq^k\rho_h}.
\end{equation*}
By bootstrapping we easily see that this implies
$\rho_h=1+pq^h+\mathcal{O}((pq)^h)$. Since the poles of the other terms in
\eqref{eq:hfunc} are $\frac1p$ and $\frac1q$, $\rho_h$ is the dominant
singularity of the function $G_h$. Furthermore, we have
\begin{eqnarray*}
&&G_h(q\rho_h)=\frac qp+\mathcal{O}(q^h),
\quad G_h'(q\rho_h)=\frac1{p^2}+\mathcal{O}(hq^h)\\
&&\left.\frac{d}{dz}\left(1-G_h(qz)\frac{pz}{1-pz}\left(1-(pz)^{h-1}\right)
\right)\right|_{z=\rho_h}=-\frac1{pq}+\mathcal{O}(hp^h).
\end{eqnarray*}

Putting everything together we obtain
\begin{equation}
  \label{eq:asym}
  \Prob\left(M_n<h\right)=(1-pq^h)^n+\mathcal{O}(hq^h)+
\mathcal{O}(hq^h).
\end{equation}

Using \eqref{eq:asym} and Abel summation we derive that the first and second
moment of the longest run are given by
\begin{equation}
\label{eq:moments}
\begin{aligned}
\mathbb{E}&M_n=\sum_{h\geq1}\left(1-\Prob\left(M_n<h\right)\right)=
\sum_{h\geq1}\left(1-(1-pq^h)^n\right)+\mathcal{O}(1)\\
\mathbb{E}&M_n^2=2\sum_{h\geq1}h\left(1-\Prob\left(M_n<h\right)\right)-
\mathbb{E}M_n=\\
&\sum_{h\geq1}(2h-1)\left(1-(1-pq^h)^n\right)+\mathcal{O}(1).
\end{aligned}
\end{equation}
In order to compute the asymptotic behaviour of these two moments, we use the
now classical exponential approximation technique (cf.~\cite{Galambos87}).
We replace the terms $(1-pq^h)^n$ in the two sums by $\exp(-npq^h)$ and
estimate the error. For this purpose we split the range of summation into three
parts: $h<\frac34\loq n$, $|h-\loq n|\leq\frac14\loq n$, and $h>\frac54\loq n$.

In the range $h<\frac34\loq n$ we estimate
$$\left(1-pq^h\right)^n\leq\left(1-pn^{-\frac14}\right)^n\leq
\exp\left(-pn^{\frac34}\right)\quad
\text{and }\exp\left(-npq^h\right)\leq\exp\left(-pn^{\frac34}\right),$$
which yields
\begin{equation}
\label{eq:r1}
\left|\left(1-pq^h\right)^n-\exp\left(-npq^h\right)\right|\leq
\exp\left(-pn^{\frac34}\right).
\end{equation}
In the range $|h-\loq n|\leq\frac14\loq n$ we write $h=\loq n+t$ and
approximate by the Taylor expansion to obtain
$$\left(1-pq^h\right)^n=\exp\left(n\log\left(1-\frac pnq^t\right)\right)=
\exp\left(-pq^t+\mathcal{O}(\frac{q^{2t}}n)\right).$$
Observing that the error term in this equation tends to $0$ we obtain
\begin{equation}
\label{eq:r2}
\left|\left(1-pq^h\right)^n-\exp\left(-npq^h\right)\right|=
\mathcal{O}\left(\frac{q^{2t}}n\right)=\mathcal{O}(n^{-\frac12}).
\end{equation}
For the range $h>\frac54\loq n$ we use the Taylor expansion again to obtain
\begin{equation}
\label{eq:r3}
\left|\left(1-pq^h\right)^n-\exp\left(-npq^h\right)\right|=
\mathcal{O}(nq^{2h}).
\end{equation}

Inserting \eqref{eq:r1}, \eqref{eq:r2}, and \eqref{eq:r3} into
\eqref{eq:moments} we obtain
\begin{equation}
\label{eq:momasy}
\mathbb{E}M_n=\sum_{h\geq 1}\left(1-\exp(-npq^h)\right)+\mathcal{O}(1)
\mathcal{O}\left(e^{-n^{\frac34}}\log n\right)+\mathcal{O}(n^{-\frac12}\log n)+
\mathcal{O}(n^{-\frac32}).
\end{equation}

We now apply the Mellin transform (cf.~\cite{Doetsch55,FlGoDu95}) to the
function $f(t)=\sum_{h\geq1}(1-\exp(-tpq^h))$. This yields the transformed
function
\begin{equation}
\label{eq:mellin}
f^*(s)=-\Gamma(s)p^{-s}\frac1{q^s-1},\quad\text{for }
-1<\Re s<0.
\end{equation}
Application of the Mellin inversion formula, shifting the line of integration
to the right and collecting residues yields
\begin{eqnarray}
\label{eq:f1}
f(t)&=&-\frac1{2\pi i}\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\Gamma(s)p^{-s}\frac1{q^s-1}t^{-s}\,ds=
-\sum_{k\in\mathbb{Z}}\Res{s=\frac{2k\pi i}{\log\frac1q}}{f_1^*(s)t^{-s}}\\
&-&\frac1{2\pi i}\int\limits_{\frac12-i\infty}^{\frac12+i\infty}
\Gamma(s)p^{-s}\frac1{q^s-1}t^{-s}\,ds.\notag
\end{eqnarray}
The residues are easily computed to be
\begin{equation}
\label{eq:res}
\begin{aligned}
\Res{s=0}{\Gamma(s)p^{-s}\frac1{q^s-1}t^{-s}}&=\loq t-
\frac{\log p}{\log q}-\frac12-\frac\gamma{\log q}\\
\Res{s=\frac{2k\pi i}{\log\frac1q}}
{\Gamma(s)p^{-s}\frac1{q^s-1}t^{-s}}&=
\Gamma\left(\frac{2k\pi i}{\log\frac1q}\right)
(pt)^{-\frac{2k\pi i}{\log\frac1q}}\frac1{\log q}.
\end{aligned}
\end{equation}
This yields
\begin{equation}
\label{eq:f1a}
f(n)=\mathbb{E}M_n+\mathcal{O}(1)=\loq n+\mathcal{O}(1).  
\end{equation}

Similarly, we can obtain an expression for the second moment
\begin{equation}
\label{eq:f2a}
\mathbb{E}M_n^2+\mathcal{O}(1)=\loq^2 n+\mathcal{O}(\log n)
\end{equation}
by applying the same analysis to the function
$\sum_{h\geq1}(2h-1)(1-(1-pq^h)^n)$. Unfortunately, the error term in
\eqref{eq:moments} is too weak to obtain the main term in the asymptotic of the
variance of $M_n$.

\begin{prop}\label{prop:long}
The mean value of the length of the longest run $M_n$ in a string of $n$
geometric random variables satisfies
$$\mathbb{E}M_n=\loq n+\mathcal{O}(1).$$
\end{prop}


{\bf Acknowledgement.} This work was done during the first author's visit to
the Centre for Applicable Analysis and Number Theory at the University of the
Witwatersrand, Johannesburg, South Africa. He is indebted to Arnold
Knopfmacher, Doron S.~Lubinsky and Helmut Prodinger for their great
hospitality.

\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{Devroye92}
L.~Devroye, \emph{A limit theory for random skip lists}, Annals of Applied
  Probability \textbf{2} (1992), 597--609.

\bibitem{Doetsch55}
G.~Doetsch, \emph{Handbuch der laplace transformation}, Birkh\"auser, Basel,
  1955.

\bibitem{Feller50}
W.~Feller, \emph{An introduction to probability theory and its applications},
  vol.~1, J. Wiley, 1950.

\bibitem{FlGoDu95}
P.~Flajolet, X.~Gourdon, and P.~Dumas, \emph{Mellin transforms and asymptotics:
  {H}armonic sums}, Theoretical Computer Science \textbf{144} (1995), 3--58.

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

\bibitem{Galambos87}
J.~Galambos, \emph{The asymptotics of extreme order statistics}, J. Wiley,
  1987.

\bibitem{GuOd80}
L.~J. Guibas and A.~M. Odlyzko, \emph{Long repetitive patterns in random
  sequences}, Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie \textbf{53}
  (1980), 241--262.

\bibitem{Hwang98}
H.-K. Hwang, \emph{On convergence rates in the central limit theorems for
  combinatorial structures}, European Journal of Combinatorics \textbf{19}
  (1998), 329--343.

\bibitem{KiPr90}
P.~Kirschenhofer and H.~{P}rodinger, \emph{On the analysis of probabilistic
  counting}, Number--theoretic Analysis (E.~Hlawka and R.~F. Tichy, eds.),
  Lecture Notes in Mathematics, vol. 1452, 1990, pp.~117--120.

\bibitem{KiPr93}
\bysame, \emph{A result in order statistics related to probabilistic counting},
  Computing \textbf{51} (1993), 15--27.

\bibitem{KiPr94}
\bysame, \emph{The path length of random skip lists}, Acta Informatica
  \textbf{31} (1994), 775--792.

\bibitem{KiPrSz96}
P.~Kirschenhofer, H.~{P}rodinger, and W.~Szpankowski, \emph{Analysis of a
  splitting process arising in probabilistic counting and other related
  algorithms}, Random Structures and Algorithms \textbf{9} (1996), 379--401.

\bibitem{KnPr00}
A.~Knopfmacher and H.~Prodinger, \emph{Combinatorics of geometrically
  distributed random variables: Value and position of the $r$th left-to-right
  maximum}, Discrete Mathematics (to appear).

\bibitem{Knuth78}
D.~E. Knuth, \emph{The average time for carry propagation}, Indagationes
  Mathematicae \textbf{40} (1978), 238--242.

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

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

\bibitem{Pugh90}
W.~Pugh, \emph{Skip lists: a probabilistic alternative to balanced trees},
  Communications of the ACM \textbf{33} (1990), 668--676.

\end{thebibliography}


%\bibliography{runbib}
\end{document}

