\documentclass[12pt,reqno,a4paper]{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}   

%\numberwithin{equation}{article}


\newcommand{\stwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newtheorem{theorem}{Theorem}

\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}%[section]


\newtheorem{prop}{Proposition}
\numberwithin{equation}{section}

\def\Prob{\mathbb{P}}
\def\prob{\mathbb{P}}
\def\expect{\mathbb{E}}
\def\shuffle{\sqcup\kern-0.07cm\sqcup}

\def\eps{\varepsilon}

\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}}
% other useful commands


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

%\section{preamble}
\title[Length of ascending runs]
{Combinatorics of geometrically distributed random variables:\\
Length of ascending runs}

\author{Helmut Prodinger}
\thanks{This research was partially
conducted while the author was
a guest of the projet Algo at INRIA, Rocquencourt. The funding
came from the Austrian--French ``Amad\'ee'' cooperation.}


\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},\newline
homepage: {\tt http://www.wits.ac.za/helmut/index.htm}.
}


\date{\today}


\begin{document}

\begin{abstract}
For $n$ independently distributed geometric random variables we
consider the average length of the $m$--th run, for fixed $m$
and $n\to\infty$. One particular result is that this parameter
approaches $1+q$. 

In the limiting case $q\to1$ we thus rederive known results
about runs in permutations.
\end{abstract}


\maketitle

\section{Introduction}

Knuth in \cite{Knuth98} has considered the average length
$L_k$ of the $k$th ascending run in random  permutations
of $n$ elements
(for simplicity, mostly the instance $n\to \infty$ was discussed).

This parameter has important impact on the behaviour of
several sorting algorithms. 

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$. 

In a series of papers we have dealt with the combinatorics
of geometric random variables, and it turned out 
that in the limiting case $q\to1$ the results
(when they made sense) 
 where the same as
in the instance of permutations. Therefore we study the concept of
ascending runs in this setting. 
We are considering infinite words, with letters $1,2,\cdots$,
and they appear with probabilities $p,pq,pq^2,\cdots$.
If we decompose a word
into ascending runs
\begin{equation*}
a_1<\dots< a_r \ge b_1<\dots< b_s \ge c_1<\dots< c_t\ge\cdots,
\end{equation*}

then $r$ is the length of the first, $s$ of the second, $t$ of
the third run, and so on. 



We are interested in the averages of these parameters.

\section{Words with exactly $m$ runs}
As a preparation, we consider the probability that a random 
word of length $n$ has $m$ ascending runs. For $m=1$, 
this is given by
\begin{equation*}
[z^n]\prod_{i\ge1}(1+pq^{i-1}z) \quad\text{for $n\ge1$}.
\end{equation*}

But the product involved here 
is well known in the theory of partitions;
the usual notation is
\begin{gather*}
(a)_n=(a;q)_n=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^{n-1})
\quad\text{and}\\
(a)_\infty=(a;q)_\infty=(1-a)(1-aq)(1-aq^2)\cdots .
\end{gather*}

Therefore

\begin{equation*}
\prod_{i\ge1}(1+pq^{i-1}z)=(-pz)_\infty=
\sum_{n\ge0}\frac{p^nq^{\binom n2}z^n}{(q)_n},
\end{equation*}

the last equality being the celebrated identity of Euler
\cite{Andrews76}. This was already noted in 
\cite{Prodinger93b}.					
If we set
\begin{equation*}
\Lambda_m(z)=\sum_{n\ge0}[\text{Probability
that a word of length $n$ has (exactly) $m$ ascending runs}]z^n,
\end{equation*}

then $\Lambda_0(z)=1$ and $\Lambda_1(z)=(-pz)_\infty-1$. 							


Now for general $m$ we should consider $(-pz)_\infty^m$.
Indeed, words with exactly $m$ ascending runs have a unique
representation in this product. However, this product contains
also words with {\sl less\/}
 than $m$ runs, and we have to subtract that.

A word with $m-1$ ascending runs 
is $n+1$ times as often contained as in 
$\Lambda_{m-1}(z)$. This is so because we can choose any
gap between two letters (also on the border) in $n+1$ ways.
Such a gap means that we deliberately cut a run into   pieces.
Then, however, everything is unique. In terms of generating
functions, this is $D(z\Lambda_{m-1}(z))$. (We write
$D=\frac{d}{dz}$.) For $m-2$ ascending
runs, we can select 2 gaps in $\binom {n+2}{2}$ ways, 
which amounts to $\frac12D(z^2\Lambda_{m-2}(z))$,
and so on. 


Therefore we have the following recurrence:

\begin{align}\label{recursion}
\Lambda_m(z)=P^m-\sum_{k=1}^m\frac1{k!}D^k\big(z^k
\Lambda_{m-k}(z)\big),\qquad\Lambda_0(z)=1;
\end{align}
here are the first few values. We use the abbreviations
$P=(-pz)_\infty$ and
$P_k=z^kD^kP$.
\begin{align*}
\Lambda_0&=1,\\
\Lambda_1&=P-1\\
\Lambda_2&=(P-1)P-P_1,\\
\Lambda_3&=(P-1)P^2+P_1-2PP_1+\frac12P_2,\\
\Lambda_4&=(P-1)P^3
+2PP_1-\frac12P_2-3P^2P_1+P_1^2+PP_2-\frac16P_3.\\
\end{align*}

In the limiting case $q\to1$ we can specify these quantities
explicitly.
This  was obtained by experiments after
a few keystrokes with trusty Maple.---Instead of $P$ we just
have $e^z$, and that definitely makes life much easier, since
all the derivatives are still $P$. 

\begin{theorem}The sequence $\Lambda_m(z)$ is defined as follows,
\begin{align*}
\Lambda_m(z):=e^{mz}-\sum_{k=1}^m\frac1{k!}D^k\big(z^k
\Lambda_{m-k}(z)\big),\qquad
\Lambda_0(z):=1.
\end{align*}
Then we have for $m\ge1$
\begin{equation*}
\Lambda_m(z)=\sum_{j=0}^me^{jz}
\frac{z^{m-j-1}(-1)^{m-j}j^{m-j-1}\big(j(z-1)+m\big)}{(m-j)!}.
\end{equation*}
\end{theorem}

{\bf Proof.}
First notice that 
if we write 
\begin{equation*}
\lambda_m(z)=\sum_{j=0}^me^{jz}
\frac{(-jz)^{m-j}}{(m-j)!},
\end{equation*}
for $m\ge0$,
then $\Lambda_m(z)=\lambda_m(z)-\lambda_{m-1}(z)$.
And the equivalent formula is
			
								
\begin{equation*}
\sum_{k=0}^m\frac1{k!}D^k\big(z^k\lambda_{m-k}(z)\big)=
\sum_{j=1}^me^{jz},
\end{equation*}
which we will prove by induction, the basis being trivial
(as usual).
Now


\begin{multline*}
\sum_{k=0}^m\frac1{k!}D^k\big(z^k\lambda_{m-k}(z)\big)
=\sum_{k=0}^m\frac1{k!}D^k\sum_{j=1}^{m-k}e^{jz}z^{m-j}
\frac{(-j)^{m-k-j}}{(m-k-j)!}\\
=\sum_{k=0}^m\frac1{k!}\sum_{i=0}^k
\binom{k}{i}\sum_{j=1}^{m-k}j^{k-i}e^{jz}z^{m-j-i}
\frac{(m-j)!}{(m-j-i)!}
\frac{(-j)^{m-k-j}}{(m-k-j)!},\\
\end{multline*}
and we have to prove that the 
 coefficient of $e^{jz}$ therein is 1. 
Writing  $M:=m-j$ it is
\begin{align*}
&\sum_{k=0}^{M}\frac1{k!}\sum_{i=0}^k
\binom{k}{i}j^{k-i}z^{M-i}
\frac{M!}{(M-i)!}
\frac{(-j)^{M-k}}{(M-k)!}\\
&=\sum_{i=0}^{M}\frac{M!}{(M-i)!}(jz)^{M-i}
\sum_{k=i}^{M}\frac1{k!}
\binom{k}{i}\frac{(-1)^{M-k}}{(M-k)!}\\
&=\sum_{i=0}^{M}\binom Mi(jz)^{M-i}
\frac1{(M-i)!}\sum_{k=i}^{M}\binom{M-i}{k-i}
(-1)^{M-k}\\
&=\sum_{i=0}^{M}\binom Mi(jz)^{M-i}
\frac{(-1)^{M-i}}{(M-i)!}\delta_{M,i}=1.
\end{align*}

Thus
\begin{align*}
\sum_{k=1}^m\frac1{k!}D^k\big(z^k\Lambda_{m-k}(z)\big)
&=\sum_{k=1}^m\frac1{k!}D^k\big(z^k\lambda_{m-k}(z)\big)-
\sum_{k=1}^m\frac1{k!}D^k\big(z^k\Lambda_{m-1-k}(z)\big)\\
&=\sum_{j=1}^me^{jz}-\lambda_m(z)-
\sum_{j=1}^{m-1}e^{jz}+\lambda_{m-1}(z)=
e^{mz}-\Lambda_m(z),
\end{align*}
and the result follows. \qed


{\bf Remark.} Since every word has {\sl some\/} number of
ascending runs, we must have that
\begin{equation*}
\sum_{m\ge0}\Lambda_m(z)=\frac1{1-z}.
\end{equation*}


In the limiting case $q\to 1$ we will give an independent
proof. For the general case, see the next sections.



Consider
\begin{equation*}
\Lambda_0(z)+\Lambda_1(z)+\dots+\Lambda_m(z)=
\lambda_m(z);
\end{equation*}
for $m=6$ we get e.~g.

\begin{equation*}
\lambda_6(z)=1+z+{z}^{2}+{z}^{3}+{z}^{4}+{z}^{5}+{z}^{6}+{\tfrac {5039}{5040}}{z}^{
7}+{\tfrac {5009}{5040}}{z}^{8}+{\tfrac {38641}{40320}}{z}^{9}+O\left (
{z}^{10}\right ).
\end{equation*}

Now this is no coincidence since we will prove that





\begin{equation*}
[z^n]\lambda_m(z)=1\quad\text{for }n\le m.
\end{equation*}



This amounts to prove that\footnote{A gifted former student
of electrical engineering (Hermann A.) contacted me years after
he was in my Discrete Mathematics course, telling me that he
found this (or an equivalent) formula, but could not prove it.
 He was quite excited, but after I emailed him how to prove it, 
I never heared from him again. }
\begin{equation*}
\frac1{n!}\sum_{k=0}^n\binom nk(m-k)^n(-1)^k=1.
\end{equation*}
Notice that
\begin{equation*}
\stwo{h}{n}=\frac1{n!}\sum_{k=0}^n\binom nk(-1)^{n-k}k^h
\end{equation*}
are Stirling subset numbers, and they are zero for $h<n$.
Therefore, upon
expanding $(m-k)^n$ by the binomial theorem, almost
all the terms are annihilated, only $(-k)^n$ survives. But then
it is a Stirling number $\stwo nn=1$. 
It is not too hard to turn this proof involving ``discrete convergence''
into one with ``ordinary convergence.'' 
\qed

\section{The average length of the $m$th run}

We consider the parameter
``combined lengths'' of the first $m$
runs in infinite strings and its probability generating function.
 
Note carefully

that now the probability space are infinite words, as opposed to 
the previous chapter where we had words of length $n$. This is 
not unlike the situation in the paper \cite{FlGaTh92}.

To say that this parameter is larger or equal to $n$ is the same 
as to say that a word of length $n$ (the first $n$ letters of the 
infinite word) has $\le m$ ascending runs. Therefore the
sought probability generating function is
\begin{equation*}
F_m(z)=
\frac{z-1}{z}\big(\Lambda_0(z) +\dots+\Lambda_m(z) \big)+\frac1z.
\end{equation*}
Now 
		

\begin{equation*}
F'_m(1)=
\Lambda_0(1) +\dots+\Lambda_m(1) -1=\Lambda_1(1) +\dots+\Lambda_m(1)
\end{equation*}
is the expected value of the combined lengths
of the first $m$
runs. Thus 
$\Lambda_m(1)$
is the expected value of the length of the $m$th run
($m\ge1$).

In the limiting case $q\to 1$ we can say more since we
know $\Lambda_m(z)$ explicitly:





\begin{equation*}
L_m=\Lambda_m(1)=
m\sum_{j=0}^m\frac{(-1)^{m-j}j^{m-j-1}}{(m-j)!}e^j,
\end{equation*}
and this is exactly the formula that appears in \cite{Knuth98} for
the instance of permutations. 

There, we also learn that $L_m\to2$;
in  the general case,
we will see in the next sections
that $L_m\to1+q$.




\section{Solving the recursion}


The effect of the operator $\frac1{k!}D^k(z^kf)$ can also be
described by the {\sl Hadamard product\/}
(see \cite{Comtet74} for definitions) of $f$ with the series
$$
T_k=\sum_n \binom {n+k}{n}z^n.
$$


The reformulation of the recursion is then


$$
P^m=\sum_{k=0}^mT_k\odot \Lambda_{m-k}.
$$
We want to invert this relation to get the $\Lambda_m(z)$'s from the
powers of $P$.
We get
$$
\Lambda_m(z)=\sum_{k=0}^m U_k\odot P^{m-k},
$$
where
$$
U_k=[w^k]\ \ 1\Big/\sum_{j\ge0}T_jw^j.
$$
\begin{lemma}
$$
U_k=(-1)^k\sum_n \binom {n+1}{k}z^n.
$$
\end{lemma}


{\bf Proof}. Since
$$
U_n=-\sum_{k=0}^{n-1}U_kT_{n-k},
$$
it is best to prove the formula by induction, the instance $n=0$,
i.e. $U_0=1/(1-z)$ being obvious. 

The righthandside multiplies the coefficient of $z^n$ by 
\begin{align*}
-\sum_{k=0}^{n-1}(-1)^l\binom{n+1}{l}\binom{n+k-l}{n}=
(-1)^{k+1}\sum_{l=0}^{k-1}\binom{n+1}{l}\binom{-n-1}{k-l}
=(-1)^k\binom{n+1}{k},
\end{align*}
which finishes the proof.

Therefore we get the formula
\begin{proposition}\label{sol}
$$
[z^n]\Lambda_m(z)=[z^n]\sum_{k=0}^m(-1)^k\binom{n+1}kP^{m-k};
$$
for $n<m$ this is zero by the combinatorial interpretation or
directly. 
\end{proposition}

Now this form definitely looks like an outcome of the
inclusion--exclusion
principle. Indeed, there are $n+1$ gaps between the $n$ letters, 
and one can pick $k$ of them where the condition that a new run should
start is {\sl violated.} Since we don't need that, we confine
ourselves
to this brief remark.




Let us prove that
$$
\sum_{m\ge0}\Lambda_m(z)=\frac1{1-z}:
$$
\begin{align*}
[z^n]\sum_{m\ge0}\Lambda_m(z)&=
[z^n]\sum_{0\le k\le m\le n}(-1)^k\binom{n+1}kP^{m-k}\\
&=[z^n]\sum_{k=1}^n(-1)^{n-k}\binom{n+1}{k+1}\sum_{i=0}^kP^{i}\\
&=[z^n]\sum_{k=1}^n(-1)^{n-k}\binom{n+1}{k+1}\sum_{i=0}^k\sum_{j=0}^i\binom
ij(P-1)^{i}\\ &=[z^n](P-1)^n=1. \end{align*} (Note that $P-1=z+\dots$.)

Let us also rederive the formula for $\Lambda_m(1)$ in the limiting
case $q\to1$;
since

$$
[z^n]\Lambda_m(z)=\sum_{k=0}^m(-1)^{m-k}\binom{n+1}{m-k}\frac{k^n}{n!}
$$
we have

\begin{align*}
\sum_{n\ge0}[z^n]\Lambda_m(z)
&=\sum_{k=0}^m\frac{(-1)^{m-k}}{(m-k)!}\sum_{n\ge0}\Big(\frac{1}{(n-m+k)!}+
\frac{m-k}{(n+1-m+k)!} \Big)k^n\\
&=\sum_{k=0}^m\frac{(-1)^{m-k}}{(m-k)!}\big(k^{m-k}+(m-k)k^{m-k-1}\big)e^k\\
&=m\sum_{k=0}^m\frac{(-1)^{m-k}}{(m-k)!}k^{m-k-1}e^k. \end{align*}


\section{A double generating function}


From Proposition \ref{sol} we infer that
\begin{align*}
\Lambda_m(z)&=\sum_{k=0}^m\frac{(-1)^k}{k!}D^k(zP^{m-k})\\
&=\sum_{k=0}^m\frac{(-1)^k}{k!}\big(zD^kP^{m-k}+kD^{k-1}P^{m-k}\big)\\
&=z\sum_{k=0}^m\frac{(-1)^k}{k!}D^kP^{m-k}
-\sum_{k=0}^{m-1}\frac{(-1)^k}{k!}D^{k}P^{m-1-k}.\\
\end{align*}

Now these forms look like convolutions, and thus we introduce
the double generating function

$$
R(w,z)=\sum_{m\ge0}\Lambda_m(z)w^m.
$$
Upon summing we find


\begin{align*}
R(w,z)=ze^{-wD}\frac{1}{1-wP}-we^{-wD}\frac{1}{1-wP}
=\frac{z-w}{1-w\big(-p(z-w)\big)_\infty};
\end{align*}
the last step was by noticing that $e^{aD}$ is the shift operator
$E^a$ (see e.~g. \cite{Aigner97}).

It is tempting to plug in $w=1$, because of the summation of the
$\Lambda_m(z)$'s, but this is forbidden, because of
divergence.


The instance ($q\to1$)

\begin{align*}
R(w,1)
=\frac{1-w}{1-we^{1-w}}
\end{align*}
differs from Knuth's

\begin{align*}
\frac{w(1-w)}{e^{w-1}-w}+w
\end{align*}
just by $1$, because in \cite{Knuth98} $L_0=0$, whereas here it
is $L_0=1$. 


\begin{theorem}
The generating function of the numbers $L_m$ is given by
$$
\frac{1-w}{1-w\prod\limits_{i\ge0}\big(1-(w-1)pq^i\big)}.
$$
\end{theorem}

The dominant singularity is at $w=1$, and the local expansion starts
as
$$
\frac{1+q}{1-w}+\cdots.
$$
From this, singularity analysis \cite{FlOd90} entails that
$$
L_m=1+q+O(\rho^{-m})
$$
for some $\rho>1$ that depends on $q$.

Experiments indicate the expansion ($m\to\infty$)
\begin{align*}
L_m=1+q-q^{m+1}+2mq^{m+2}-(1+2m^2)q^{m+3}
-\tfrac{2m^4+10m^2-15m+9}{3}q^{m+4}+\cdots ,
\end{align*}
so that it seems that one could take $\rho=\frac1q-\epsilon$.
However, that would require a proof.


\section{Weakly ascending runs}

Relaxing the conditions, we might now say that
$\dots >a_1\le\dots\le a_r>\cdots$
is a run (of length $r$). 

Many of the previous considerations carry over, so we only give a
few remarks. 

The recursion (\ref{recursion}) stays the same, but with 
$P=1/(pz)_\infty$.

With this choice of $P$ the formula
$$
[z^n]\Lambda_m(z)=[z^n]\sum_{k=0}^m(-1)^k\binom{n+1}kP^{m-k}
$$
still holds.

The bivariate generating function is
\begin{align*}
\frac{z-w}{1-w/\big(p(z-w)\big)_\infty}.
\end{align*}

The poles of interest are the solutions of 

\begin{equation*}
\prod_{i\ge 0}\big(1+(w-1)pq^i\big)=w;
\end{equation*}

the dominant one is $w=1$ with a local expansion


\begin{equation*}
\Big(1+\frac1q\Big)\frac{1}{1-w}+\cdots,
\end{equation*}
from which we can conclude that $L_m\to1+\frac1q$.


And the experiments indicate that
\begin{equation*}
L_m=1+\tfrac1q -(-1)^mq^{2m-1}\Big(1-2(m-1)q+(2m^2-5m+4)q^2+
\cdots\Big).
\end{equation*}















   \bibliographystyle{plain}
%\bibliography{pro_bib}
\begin{thebibliography}{1}

\bibitem{Aigner97}
M.~Aigner.
\newblock {\em Combinatorial Theory}.
\newblock Springer, 1997.
\newblock Reprint of the 1979 edition.

\bibitem{Andrews76}
G.~E. Andrews.
\newblock {\em The Theory of Partitions}, volume~2 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Addison--Wesley, 1976.

\bibitem{Comtet74}
L.~Comtet.
\newblock {\em Advanced Combinatorics}.
\newblock Reidel, Dordrecht, 1974.

\bibitem{FlGaTh92}
P.~Flajolet, D.~Gardy, and L.~Thimonier.
\newblock Birthday paradox, coupon collectors, caching algorithms, and
  self--organizing search.
\newblock {\em Discrete Applied Mathematics}, 39:207--229, 1992.

\bibitem{FlOd90}
P.~Flajolet and A.~Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3:216--240, 1990.

\bibitem{Knuth98}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.
\newblock Second edition, 1998.

\bibitem{Prodinger93b}
H.~Prodinger.
\newblock Combinatorial problems of geometrically distributed random variables
  and applications in computer science.
\newblock In V.~Strehl and R.~K{\"o}nig, editors, {\em Publications de l'IRMA
  (Stra\ss bourg)}, volume~30, pages 87--95, 1993.

\end{thebibliography}










































							
											
		
	
\end{document}	
																							