%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