\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 $h1$ 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}