COMBINATORICS OF GEOMETRICALLY

DISTRIBUTED RANDOM VARIABLES:

LEFT-TO-RIGHT MAXIMA

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. Assume that the numbers x_{1}, …, 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}, …, 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.

1. Introduction

Let X denote a geometrically distributed random variable, i.e. ℙ{X = k} = pq^{k−1} for k ∈ ℕ and q = 1 − p.

The combinatorics of n geometrically distributed independent variables X_{1}, …, X_{n} becomes more and more important, especially because of applications in Computer science. We just mention two areas: The skiplist ([2], [14], [15]) and probabilistic counting ([4], [8], [9], [10]).

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. In the case of probabilistic counting we think about p = q = \frac{1}{2}. The parameter of interest is then the smallest natural number that does not appear as an output of any of the X_{i}’s.

We will cite one particular result, since we can use the corresponding asymptotic formula in the sequel for our own findings.

Theorem 1. [Szpankowski and Rego, [17]] The expected value E_{n} of max {X_{1}, …, X_{n}} is given by

E_{n} = ∑_{k≥0} [1 − (1 − q^{k})^{n}] = log_{Q} n + \frac{γ}{L} + \frac{1}{2} − δ (log_{Q} n) + O(\frac{1}{n}).  (1.1)

Here and in the whole paper, Q = q^{−1} and L = log Q; γ is Euler’s constant and δ(x) is a periodic function of period 1 and mean 0 which is given by the Fourier series

δ(x) = \frac{1}{L} ∑_{k≠0} Γ (−χ_{k}) e^{2kπix}.  (1.2)

The complex numbers χ_{k} are given by χ_{k} = 2kπi/L.

It should be mentioned that the asymptotic evaluation of the series in (1.1) is by now a “folklore theorem”; it appears e.g. in Knuth’s book [12] or in [6].

In this paper we want to concentrate on the 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 ([11], [7], [6], [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 + \frac{1}{4} + ⋯ + \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, …, M, each with probability \frac{1}{M}. (The uniform distribution.)

Finally, we come back to the original model of geometrically distributed variables and consider left-to-right minima. This makes no difference for random permutations and equidistribution, but here it is different! However, the computations for the maxima require “higher mathematics” (Mellin transforms or Rice’s method), and some periodicity phenomena are encountered, whereas the calculations for the minima are quite elementary.

It is interesting to note that the concept of left-to-right maxima appears also as “records”, compare[1].

To obtain the leading terms of the asymptotic expansions in Theorems 2 and 3 (namely p log_{Q} n and \frac{p}{q} log_{Q} n) 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.

2. The expectation in the strict model

Our approach will be by generating functions; to find them, we set up a certain “language” L and translate it to enumerating generating functions. We give two references for such a procedure:

[13] and [6].

To avoid confusion, we denote the “letters” by 1, 2, . . .. We decompose all sequences x_{1}x_{2} … in a canonical way as follows: We combine each left-to-right maximum k with the following (smaller or equal) elements. Such a part is decribed by

A_{k} := k{1, …, k}^{∗}.  (2.1)

Such a group may be present or not. This observation gives the desired “language”, where ε denotes the “empty word”:

L := (A_{1} + ε) · (A_{2} + ε) · (A_{3} + ε) …  (2.2)

It is important not to confuse ε with something like a letter 0 (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 k should of course not being forgotten. {1, …, k} maps into z(1−q^{k}) and its star {1, …, k}^{∗} into 1/(1 − z(1 − q^{k})). So we obtain the generating function F (z, y) as an infinite product:

F (z, y) = ∏_{k≥1} (1 + \frac{yzpq^{k−1}}{1 − z(1 − q^{k})})  (2.3)

To be explicit, the coefficient of z^{n}y^{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{∂F (z,y)}{∂y} |_{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} ∑_{k≥0} \frac{q^{k}}{1 − z(1 − q^{k})},  (2.4)

which is also, by partial fraction decomposition,

f(z) = p ∑_{k≥0} [\frac{1}{1 − z} − \frac{1}{1 − z(1 − q^{k})}] .  (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 ∑_{k≥0} [1 − (1 − q^{k})^{n}]  (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.

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 [log_{Q} n + \frac{γ}{L} + \frac{1}{2} − δ (log_{Q} n)] + O(\frac{1}{n})  (2.7)

with the periodic function δ(x) from (1.2).

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 → 0, which is intuitively clear, since the result of the “random variables” is then the sequence 111 … 1, with only one left-to-right maximum.

3. The expectation in the loose model

Again, we are defining an appropriate “language” L from which a bivariate generating function F (z, y) can be derived. Set A_{k} := k{1, …, k − 1}^{∗}, then L := A_{1}^{∗} · A_{2}^{∗} · A_{3}^{∗} …, and

F (z, y) = ∏_{k≥1} \frac{1}{1 − \frac{yzpq^{k−1}}{1−z(1−q^{k−1})}} = ∏_{k≥0} \frac{1 − z(1 − q^{k})}{1 − z + zq^{k}(1 − py)}.  (3.1)

Therefore

f(z) = \frac{∂F (z, y)}{∂y}|_{y=1} = \frac{pz}{1 − z} ∑_{k≥0} \frac{q^{k}}{1 − z(1 − q^{k+1})} = \frac{p}{q} ∑_{k≥1} [\frac{1}{1 − z} − \frac{1}{1 − z(1 − q^{k})}]  (3.2)

and

E_{n} = [z^{n}]f(z) = \frac{p}{q} ∑_{k≥1} [1 − (1 − q^{k})^{n}] .  (3.3)

By virtue of Theorem 1 we therefore obtain

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{p}{q} [log_{Q} n + \frac{γ}{L} − \frac{1}{2} − δ (log_{Q} n)] + O(\frac{1}{n})  (3.4)

with δ(x) from Theorem 1 (and Theorem 2).

The function q → 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.

4. The variance in the strict model

We start from F (z, y) from equation (2.3) and observe (following e.g. [11]) that the variance V_{n} may be obtained by

V_{n} = [z^{n}]\frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} + E_{n} − E_{n}^{2}.  (4.1)

Therefore, we consider

\frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} = g(z) + h(z).  (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.

\begin{aligned}g(z) & = \frac{2}{1 − z} ∑_{1≤i<j} \frac{zpq^{i−1}}{1 − z(1 − q^{i−1})} · \frac{zpq^{j−1}}{1 − z(1 − q^{j−1})} \\ & = 2p^{2} ∑_{0≤i<j} [\frac{1}{1 − z} + \frac{1}{q^{i−j} − 1} · \frac{1}{1 − z(1 − q^{i})} + \frac{1}{q^{j−i} − 1} · \frac{1}{1 − z(1 − q^{j})}] \end{aligned}  (4.3)

and

g_{n} := [z^{n}]g(z) = 2p^{2} ∑_{0≤i<j} [1 + \frac{1}{q^{i−j} − 1} · (1 − q^{i})^{n} + \frac{1}{q^{j−i} − 1} · (1 − q^{j})^{n}] .  (4.4)

This time we cannot resort to earlier results from the literature, whence we have to derive the asymptotic equivalent for g_{n} from scratch.

Decompositions of the double sums must be done with some care because of convergence problems. The second sum is easy:

∑_{0≤i<j} \frac{1}{q^{i−j} − 1} · (1 − q^{i})^{n} = ∑_{i≥0} (1 − q^{i})^{n} · ∑_{h≥1} \frac{1}{q^{−h} − 1} = α · ∑_{i≥0} (1 − q^{i})^{n}  (4.5)

with the traditional abbreviation α = α_{Q} = ∑_{h≥1} \frac{1}{Q^{h} − 1}. Now consider the other part:

\begin{matrix}∑_{0≤i<j} [1 + \frac{1}{q^{j−i} − 1} · (1 − q^{j})^{n}] = ∑_{j≥1} [j + ∑_{h=1}^{j} \frac{1}{q^{h} − 1} (1 − q^{j})^{n}] \\ = ∑_{j≥1} [j − (j + ∑_{h=1}^{j} \frac{1}{Q^{h} − 1}) (1 − q^{j})^{n}] = ∑_{j≥1} j [1 − (1 − q^{j})^{n}] − ∑_{j≥1} ∑_{h=1}^{j} \frac{1}{Q^{h} − 1} (1 − q^{j})^{n} \end{matrix}

(4.6)

Collecting the terms we find

\frac{g_{n}}{2p^{2}} = ∑_{j≥1} j [1 − (1 − q^{j})^{n}] + ∑_{j≥1} ∑_{h>j} \frac{1}{Q^{h} − 1} (1 − q^{j})^{n} .  (4.7)

We want to apply Rice’s method, which we cite as follows: (compare, e.g. [5], [6])

Lemma. Let C be a curve surrounding the points 1, 2, …, n in the complex plane and let f(z) be analytic inside C. Then

∑_{k=1}^{n} \binom{n}{k} (−1)^{k}f(k) = −\frac{1}{2πi} ∫_{C}[n; z]f(z)dz,  (4.8)

where

[n; z] = \frac{(−1)^{n−1}n!}{z(z − 1) … (z − n)} = \frac{Γ(n + 1)Γ(−z)}{Γ(n + 1 − z)}. □  (4.9)

Extending the contour of integration it turns out that under suitable growth conditions on f(z) (compare [5]) the asymptotic expansion of the alternating sum is given by

∑ Res([n; z]f(z)) + smaller order terms  (4.10)

where the sum is taken over all poles z_{0} different from 1, …, n.

The range 1, …, n for the summation is not sacred; if we sum, for example, over k = 2, …, n, the contour must encircle 2, …, n, etc.

Therefore we rewrite the terms of (4.7) as alternating sums.

∑_{j≥1} j [1 − (1 − q^{j})^{n}] = − ∑_{k=1}^{n} \binom{n}{k}(−1)^{k} ∑_{j≥1} jq^{jk} = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k}φ(z)  (4.11)

with

φ(z) = −\frac{Q^{z}}{(Q^{z} − 1)^{2}} .  (4.12)

The other sum from (4.7) is

∑_{j≥1} ∑_{h>j} \frac{1}{Q^{h} − 1} (1 − q^{j})^{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k} ∑_{h>j≥1} \frac{1}{Q^{h} − 1}Q^{−jk} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}ψ(k), (4.13)

with

ψ(z) = ∑_{m≥1} ∑_{h>j≥1} Q^{−hm−jz} = ∑_{m,s,j≥1} Q^{−sm−jm−jz} = ∑_{m≥1} \frac{1}{Q^{m} − 1} · \frac{1}{Q^{m+z} − 1}.  (4.14)

Now we turn to the computation of the residues and concentrate first on (4.11). There is a triple pole at z = 0 and double poles at z = 2kπi/L, k ∈ ℤ, k ≠ 0.

An easy computation gives the local expansion at z = 0;

−[n; z]\frac{Q^{z}}{(Q^{z} − 1)^{2}} ∼ \frac{1}{L^{2}z^{3}} (1 − \frac{L^{2}z^{2}}{12} ) (1 + zH_{n} + z^{2} \frac{H_{n}^{2} + H_{n}^{(2)}}{2} )  (4.15)

and thus the residue is

\frac{1}{L^{2}} (−\frac{L^{2}}{12} + \frac{H_{n}^{2}}{2} + \frac{H_{n}^{(2)}}{2} ) .  (4.16)

The computations for the double poles z = χ_{k} are similar and we just give the results that are collected into the 2 periodic functions δ_{1}(x) and δ_{2}(x).

The contribution of the other sum is only O(n^{−1}). Using the expansion H_{n} ∼ log n+γ, we have

g_{n} ∼ p^{2}( log_{Q}^{2} n + \frac{2γ}{L} log_{Q} n + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} − \frac{1}{6} + log_{Q} n · δ_{1} (log_{Q} n) + δ_{2} (log_{Q} n) ), (4.17)

with δ_{1}(x) = −2δ(x) and δ_{2}(x) = \frac{2}{L^{2}} ∑_{k≠0} Γ′(−χ_{k}) e^{2kπix}.

Now, for the variance V_{n}, we must collect g_{n} + E_{n} − E_{n}^{2}. After some simplifications we obtain

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 → ∞

V_{n} = pq log_{Q} n + p^{2} (−\frac{5}{12} + \frac{π^{2}}{6L^{2}} − \frac{γ}{L} − [δ^{2}]_{0}) + p (\frac{γ}{L} + \frac{1}{2}) + δ_{3}(log_{Q} n) + O(\frac{1}{n}) (4.18)

Here, [δ^{2}]_{0} is the mean of the square of δ^{2}(x), a very small quantity that can be neglected for numerical purposes. Furthermore, δ_{3}(x) is a periodic function with mean 0; its Fourier coefficients could be described if needed.

The function q → pq/ log Q goes monotonically from 0 to 1 as q varies between 0 and 1.

5. The variance in the loose model

We start from F (z, y) from equation (3.3) and observe that the variance V_{n} may be obtained by

V_{n} = [z^{n}]\frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} + E_{n} − E_{n}^{2}.  (5.1)

Therefore we consider

\frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} = g(z) + h(z).  (5.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} ∑_{1≤i<j} \frac{q^{i+j}}{(1 − z(1 − q^{i}))(1 − z(1 − q^{j}))};  (5.3)

if we write it as g(z) = g_{1}(z) − g_{2}(z) with

g_{1}(z) = \frac{2p^{2}}{q^{2}} \frac{z^{2}}{1 − z} ∑_{0≤i<j} \frac{q^{i+j}}{(1 − z(1 − q^{i}))(1 − z(1 − q^{j}))}  (5.4)

and

g_{2}(z) = \frac{2p^{2}}{q^{2}} \frac{z^{2}}{1 − z} ∑_{j≥1} \frac{q^{j}}{1 − z(1 − q^{j})}  (5.5)

we see that g_{1}(z) was already studied in Section 4 (compare (4.3)) and can concentrate on g_{2}(z),

g_{2}(z) = \frac{2p^{2}}{q^{2}} ∑_{j≥1} [\frac{q^{j}}{1 − q^{j}} + \frac{1}{1 − z} − \frac{1}{1 − q^{j}} \frac{1}{1 − z(1 − q^{j})}] .  (5.6)

For n ≥ 1 we have therefore

[z^{n}]g_{2}(z) = \frac{2p^{2}}{q^{2}} ∑_{j≥1} [1 − \frac{1}{1 − q^{j}} (1 − q^{j})^{n}] = \frac{2p^{2}}{q^{2}} ∑_{j≥1} [1 − (1 − q^{j})^{n−1}]

= \frac{2p^{2}}{q^{2}} [log_{Q}(n − 1) + \frac{γ}{L} − \frac{1}{2} − δ( log_{Q}(n − 1))] + O(\frac{1}{n})

= \frac{2p^{2}}{q^{2}} [log_{Q} n + \frac{γ}{L} − \frac{1}{2} − δ(log_{Q} n)] + O(\frac{1}{n})

(5.7)

We can collect;

g_{n} = \frac{p^{2}}{q^{2}} ( log_{Q}^{2} n + \frac{2γ}{L} log_{Q} n + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} − \frac{1}{6} + log_{Q} n · δ_{1} (log_{Q} n) + δ_{2} (log_{Q} n) )

− \frac{2p^{2}}{q^{2}} (log_{Q} n + \frac{γ}{L} − \frac{1}{2} − δ(log_{Q} n)) + O(\frac{1}{n}).

(5.8)

We also find

\begin{aligned}h(z) & = \frac{2p^{2}}{q^{2}} \frac{z^{2}}{1 − z} ∑_{k≥1} \frac{q^{2k}}{(1 − z(1 − q^{k}))^{2}} \\ & = \frac{2p^{2}}{q^{2}} ∑_{k≥1} [\frac{1}{1 − z} − \frac{q^{k}}{1 − q^{k}} \frac{1}{(1 − z(1 − q^{k}))^{2}} + \frac{2q^{k} − 1}{1 − q^{k}} \frac{1}{1 − z(1 − q^{k})}] \end{aligned}  (5.9)

and therefore

\begin{aligned}h_{n} & = \frac{2p^{2}}{q^{2}} ∑_{k≥1} [1 − \frac{q^{k}}{1 − q^{k}} (n + 1)(1 − q^{k})^{n} + \frac{2q^{k} − 1}{1 − q^{k}}(1 − q^{k})^{n}] \\ & = \frac{2p^{2}}{q^{2}} ∑_{k≥1} [1 − (1 − q^{k})^{n} − n\frac{q^{k}}{1 − q^{k}} (1 − q^{k})^{n}] \end{aligned}  (5.10)

This involves a well known quantity and a new one:

\begin{aligned}l_{n} & := −n ∑_{j≥1} \frac{q^{j}}{1 − q^{j}} (1 − q^{j})^{n} = −n ∑_{j≥1} q^{j} (1 − q^{j})^{n−1} = −n ∑_{k=0}^{n−1} \binom{n − 1}{k}(−1)^{k} ∑_{j≥1} q^{j(k+1)} \\ & = ∑_{k=0}^{n−1} \binom{n}{k + 1}(k + 1)(−1)^{k+1} \frac{1}{Q^{k+1} − 1} = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k} \frac{k}{Q^{k} − 1} \end{aligned} (5.11)

Now l_{n} can be analyzed by Rice’s method. At z = 0 we have [n; z]\frac{z}{Q^{z}−1} ∼ −\frac{1}{Lz}; at z = χ_{k} we have [n; z]\frac{z}{Q^{z}−1} ∼ n^{χ_{k}}Γ(−χ_{k})\frac{χ_{k}}{L} \frac{1}{z−χ_{k}}. Therefore

l_{n} = −\frac{1}{L} − δ_{4}(log_{Q} n) + O(\frac{1}{n}) with δ_{4}(x) = \frac{1}{L} ∑_{k≠0} Γ(1 − χ_{k})e^{2kπix}.  (5.12)

We can collect the expansions (1.1) and (5.12) to get

h_{n} = \frac{2p^{2}}{q^{2}} [log_{Q} n + \frac{γ}{L} − \frac{1}{2} − \frac{1}{L} − δ(log_{Q} n) − δ_{4}(log_{Q} n)] + O(\frac{1}{n}).  (5.13)

Now we can sum up for the variance V_{n} = g_{n} + h_{n} + E_{n} − E_{n}^{2}. After some simplications we find

Theorem 5. 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 → ∞

V_{n} = \frac{p}{q^{2}} log_{Q} n + \frac{p^{2}}{q^{2}} (−\frac{5}{12} + \frac{π^{2}}{6L^{2}} + \frac{γ}{L} − \frac{2}{L} − [δ^{2}]_{0}) + \frac{p}{q} (\frac{γ}{L} − \frac{1}{2}) + δ_{5}(log_{Q} n) + O(\frac{1}{n}). (5.14)

Here, [δ^{2}]_{0} is the mean of the square of δ^{2}(x), a very small quantity that can be neglected for numerical purposes. Furthermore, δ_{5}(x) is a periodic function with mean 0; its Fourier coefficients could be described if needed.

The function q → p/q^{2} log Q goes monotonically from infinity to 0 as q varies between 0 and 1.

6. Uniform distribution: Left-to-right minima in the strict model

The ideas from Section 2 apply here mutatis mutandis. There are the letters 1, …, M, and each one can occur with probability \frac{1}{M}. Thus, let for k = 1, …, M

A_{k} := k{1, …, k}^{∗}.  (6.1)

Then

L := (A_{1} + ε) · (A_{2} + ε) … (A_{M} + ε)  (6.2)

is the desired language. Translating it gives the generating function

F (z, y) = ∏_{k=1}^{M} (1 + \frac{\frac{yz}{M}}{1 − \frac{zk}{M}} ).  (6.3)

Let f(z) = \frac{∂F (z, y)}{∂y}|_{y=1} be generating function for the expected values E_{n}. We find

f(z) = \frac{1}{M} \frac{z}{1 − z} ∑_{k=0}^{M−1} \frac{1}{1 − \frac{kz}{M}}  (6.4)

or, by partial fraction decomposition,

f(z) = ∑_{k=0}^{M−1} [\frac{1}{M − k} \frac{1}{1 − z} − \frac{1}{M − k} \frac{1}{1 − \frac{kz}{M}} ] .  (6.5)

Therefore

E_{n} = [z^{n}]f(z) = ∑_{k=0}^{M−1} \frac{1}{M − k} [1 − (\frac{k}{M} )^{n}] = ∑_{k=1}^{M} \frac{1}{k} [1 − (1 − \frac{k}{M} )^{n}] = H_{M} + O ((\frac{M − 1}{M})^{n}) .

(6.6)

Theorem 6. The expected number E_{n} of left-to-right maxima (strict model) where each element 1, …, M can occur with probability \frac{1}{M} is for n → ∞ given by

E_{n} = H_{M} + O ((\frac{M − 1}{M})^{n}) .  (6.7)

From this computation we have seen that it is not necessary to determine all terms in the partial fraction decomposition explicitely, since we are not interested to get precise expressions for the exponentially small terms. This principle will save a few unpleasant computations in the sequel. We have

\begin{aligned}g(z) & = \frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} = \frac{2}{M^{2}} \frac{z^{2}}{1 − z} ∑_{0≤i<j<M} \frac{1}{1 − \frac{iz}{M}} · \frac{1}{1 − \frac{jz}{M}} \\ & = 2 ∑_{0≤i<j<M} [\frac{1}{(M − i)(M − j)} \frac{1}{1 − z} + …] \end{aligned}  (6.8)

and therefore

g_{n} = [z^{n}]g(z) = 2 ∑_{0≤i<j<M} [\frac{1}{(M − i)(M − j)} + …] .  (6.9)

The series may be computed as follows:

2 ∑_{0≤i<j<M} \frac{1}{(M − i)(M − j)} = 2 ∑_{1≤l<k≤M} \frac{1}{kl} = H_{M}^{2} − H_{M}^{(2)}  (6.10)

For the variance we must collect the terms H_{M}^{2} − H_{M}^{(2)} + H_{M} − H_{M}^{2}. Hence we have obtained

Theorem 7. The variance V_{n} of the number of left-to-right maxima (strict model) where each element 1, …, M can occur with probability \frac{1}{M} is for n → ∞ given by

V_{n} = H_{M} − H_{M}^{(2)} + O ((\frac{M − 1}{M})^{n}) .  (6.11)

Interestingly enough, for random permutations the corresponding result is V_{n} = H_{n} − H_{n}^{(2)}.

7. Uniform distribution: Left-to-right minima in the loose model

Let, for k = 1, …, M, A_{k} := k{1, …, k − 1}^{∗}, then L := A_{1}^{∗} · A_{2}^{∗} … A_{M}^{∗} and

F (z, y) = ∏_{k=1}^{M} \frac{1}{1 − \frac{\frac{yz}{M}}{1 − z \frac{k−1}{M}}} = ∏_{k=0}^{M−1} \frac{1 − \frac{zk}{M}}{1 − \frac{zk}{M} − \frac{yz}{M}} .  (7.1)

Let f(z) = \frac{∂F (z, y)}{∂y}|_{y=1} be the generating function for the expected values E_{n}. We find

f(z) = \frac{1}{M} \frac{z}{1 − z} ∑_{k=1}^{M} \frac{1}{1 − \frac{kz}{M}} = \frac{1}{M} \frac{z}{(1 − z)^{2}} + ∑_{k=1}^{M−1} [\frac{1}{M − k} \frac{1}{1 − z} + …] .  (7.2)

This gives

E_{n} = \frac{n}{M} + ∑_{k=1}^{M−1} \frac{1}{M − k} = \frac{n}{M} + H_{M−1}.  (7.3)

Theorem 8. The expected number E_{n} of left-to-right maxima (loose model) where each element 1, …, M can occur with probability \frac{1}{M} is for n → ∞ given by

E_{n} = \frac{n}{M} + H_{M−1} + O ((\frac{M − 1}{M})^{n}) .  (7.4)

The term \frac{n}{M} has a natural interpretation, as we might expect the appearence of the largest element M about \frac{n}{M} times, and each time we count it. The term H_{M−1} has a similar explanation.

For the variance, we write traditionally \frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} = g(z) + h(z) with

g(z) = \frac{2}{M^{2}} \frac{z^{2}}{1 − z} ∑_{1≤i<j≤M} \frac{1}{1 − \frac{iz}{M}} · \frac{1}{1 − \frac{jz}{M}} and h(z) = \frac{2}{1 − z} ∑_{k=0}^{M−1} (\frac{\frac{z}{M}}{1 − \frac{z(k+1)}{M}} )^{2}. (7.5)

We must write g(z) = g_{1}(z) + g_{2}(z), where the terms for j = M are collected into g_{2}(z). We have

g_{1}(z) = ∑_{1≤i<j<M} [\frac{2}{(M − j)(M − i)} \frac{1}{1 − z} + …]  (7.6)

and therefore

[z^{n}]g_{1}(z) = ∑_{1≤i<j<M} [\frac{2}{(M − j)(M − i)} + …] = H_{M−1}^{2} − H_{M−1}^{(2)} + ….  (7.7)

Furthermore

g_{2}(z) = \frac{2}{M^{2}} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤i<M} \frac{1}{1 − \frac{iz}{M}} = ∑_{1≤i<M} [\frac{2}{M(M − i)} \frac{1}{(1 − z)^{2}} − \frac{2(2M − i)}{M(M − i)^{2}} \frac{1}{1 − z} …] ,

(7.8) and therefore

\begin{matrix}[z^{n}]g_{2}(z) = ∑_{1≤i<M} [\frac{2}{M(M − i)}(n + 1) − \frac{2(2M − i)}{M(M − i)^{2}} …] = \frac{2(n + 1)H_{M−1}}{M} − \frac{2}{M} ∑_{i=1}^{M−1} \frac{M + i}{i^{2}} \\ = \frac{2(n + 1)H_{M−1}}{M} − \frac{2}{M} (MH_{M−1}^{(2)} + H_{M−1}) = \frac{2nH_{M−1}}{M} − 2H_{M−1}^{(2)}. \end{matrix}

(7.9)

Collecting (7.7) and (7.9) we get

g_{n} = [z^{n}]g(z) = H_{M−1}^{2} − H_{M−1}^{(2)} + \frac{2nH_{M−1}}{M} − 2H_{M−1}^{(2)} = H_{M−1}^{2} − 3H_{M−1}^{(2)} + \frac{2nH_{M−1}}{M} . (7.10)

Now we turn to h(z) = \frac{2z^{2}}{M^{2}(1 − z)^{3}} + 2 ∑_{k=1}^{M−1} [\frac{1}{(M − k)^{2}} \frac{1}{1 − z} + …] and thus

h_{n} = [z^{n}]h(z) = \frac{n(n − 1)}{M^{2}} + 2H_{M−1}^{(2)}.  (7.11)

Therefore the variance is (up to the exponentially small terms)

V_{n} = H_{M−1}^{2} − 3H_{M−1}^{(2)} + \frac{2nH_{M−1}}{M} + \frac{n(n − 1)}{M^{2}} + 2H_{M−1}^{(2)} + \frac{n}{M} + H_{M−1} − (\frac{n}{M} + H_{M−1})^{2} . (7.12)

A simplification of this expression leads to

Theorem 9. The variance V_{n} of the number of left-to-right maxima (loose model) where each element 1, …, M can occur with probability \frac{1}{M} is for n → ∞ given by

V_{n} = n\frac{M − 1}{M^{2}} + H_{M−1} − H_{M−1}^{(2)} + O ((\frac{M − 1}{M})^{n}) .  (7.13)

8. Left-to-right minima in the strict model

In this and the next section we come back to the model of geometric random variables.

It is not hard to establish an appropriate “language”, as in Section 2. Let

A_{k} := k{k, k + 1, k + 2, … }^{∗}, then L := … (A_{3} + ε) · (A_{2} + ε) · (A_{1} + ε)  (8.1)

is our language, whence

F (z, y) = ∏_{k≥1} (1 + \frac{yzpq^{k−1}}{1 − zq^{k−1}} ) = ∏_{k≥0} \frac{1 − zq^{k}(1 − py)}{1 − zq^{k}}.  (8.2)

Therefore

f(z) = \frac{∂F (z, y)}{∂y}|_{y=1} = \frac{1}{1 − z} ∑_{k≥0} \frac{zpq^{k}}{1 − zq^{k+1}} = \frac{p}{q} ∑_{k≥1} \frac{q^{k}}{1 − q^{k}} [\frac{1}{1 − z} − \frac{1}{1 − zq^{k}} ]  (8.3)

and so

E_{n} = [z^{n}]f(z) = \frac{p}{q} ∑_{k≥1} \frac{1}{Q^{k} − 1} [1 − Q^{−kn}] .  (8.4)

Since the second part of the sum only produces an exponentially small contribution, we have Theorem 10. The average number E_{n} of left-to-right minima in the strict sense is for n → ∞

E_{n} = \frac{p}{q}α + O(Q^{−n}),  (8.5)

where, as before, α = α_{Q} = ∑_{k≥1} \frac{1}{Q^{k} − 1}.

Observe that the function q → \frac{p}{q}α goes monotonically from 1 to infinity as q varies between 0 and 1.

Now let us attack g(z) = \frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1}. It is easily seen to be

g(z) = \frac{2p^{2}}{q^{2}} \frac{z^{2}}{1 − z} ∑_{1≤i<j} \frac{q^{i+j}}{(1 − zq^{i})(1 − zq^{j})}.  (8.6)

Now, since we do not intend to compute the exponentially small terms explicitely, we confine ourselves with the main term 1/(1 − z) in the partial fraction decomposition.

g(z) = \frac{2p^{2}}{q^{2}} ∑_{1≤i<j} [\frac{1}{(Q^{i} − 1)(Q^{j} − 1)} · \frac{1}{1 − z} + …]  (8.7)

and

g_{n} = [z^{n}]g(z) = \frac{2p^{2}}{q^{2}} ∑_{1≤i<j} [\frac{1}{(Q^{i} − 1)(Q^{j} − 1)} …] .  (8.8)

The series is easily evaluated and gives, by symmetry, \frac{α^{2} − β}{2} , with the usual notation

β = β_{Q} = ∑_{k≥1} \frac{1}{(Q^{k} − 1)^{2}} . So the main term in the variance V_{n} is (\frac{p}{q})^{2} · (α^{2} − β) + \frac{p}{q}α − (\frac{p}{q}α)^{2} =

\frac{p}{q}α − (\frac{p}{q})^{2}β, and we have Theorem 11. The variance V_{n} of left-to-right minima in the strict sense is for n → ∞

V_{n} = \frac{p}{q}α − (\frac{p}{q})^{2}β + O(Q^{−n}).  (8.9)

Observe that q → \frac{p}{q}α − (\frac{p}{q})^{2}β goes monotonically from 0 to infinity as q varies between 0 and 1. The following alternative representation for \frac{p}{q}α − (\frac{p}{q})^{2}β might be of interest:

∑_{k≥0} \frac{1}{1 + Q + ⋯ + Q^{k}} − ∑_{k≥0} \frac{1}{(1 + Q + ⋯ + Q^{k})^{2}}  (8.10)

9. Left-to-right minima in the loose model

This time, let A_{k} := k{k + 1, k + 2, … }^{∗}, then L := … A_{3}^{∗} · A_{2}^{∗} · A_{1}^{∗} and

F (z, y) = ∏_{k≥1} \frac{1}{1 − \frac{yzpq^{k−1}}{1−zq^{k}}} = ∏_{k≥1} \frac{1 − zq^{k}}{1 − zq^{k−1}(py + q)}.  (9.1)

We obtain

\begin{aligned}f(z) & = \frac{∂F (z, y)}{∂y}|_{y=1} = \frac{1}{1 − z} ∑_{k≥1} \frac{zpq^{k−1}}{1 − zq^{k−1}} \\ & = p\frac{z}{1 − z} ∑_{k≥0} \frac{q^{k}}{1 − zq^{k}} = p\frac{z}{(1 − z)^{2}} + p ∑_{k≥1} [\frac{1}{Q^{k} − 1} · \frac{1}{1 − z} + …] , \end{aligned}  (9.2)

and

E_{n} = [z^{n}]f(z) = pn + pα + ….  (9.3)

Theorem 12. The average number E_{n} of left-to-right minima in the loose sense is for n → ∞

E_{n} = p(n + α) + O(Q^{−n}).  (9.4)

Now for the variance we write, as before, \frac{∂^{2}F (z, y)}{∂y^{2}} |_{y=1} = g(z) + h(z), with

\begin{aligned}g(z) & = 2p^{2} \frac{z^{2}}{1 − z} ∑_{0≤i<j} \frac{q^{i+j}}{(1 − zq^{i})(1 − zq^{j})} \\ & = 2p^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{j≥1} \frac{q^{j}}{1 − zq^{j}} + 2p^{2} \frac{z^{2}}{1 − z} ∑_{1≤i<j} \frac{q^{i+j}}{(1 − zq^{i})(1 − zq^{j})} \\ & = 2p^{2} ∑_{j≥1} [\frac{1}{Q^{j} − 1} · \frac{1}{(1 − z)^{2}} − (\frac{2}{Q^{j} − 1} + (\frac{1}{Q^{j} − 1})^{2}) \frac{1}{1 − z} + …] \\ & + 2p^{2} ∑_{1≤i<j} [\frac{1}{(Q^{i} − 1)(Q^{j} − 1)} \frac{1}{1 − z} + …] \end{aligned}  (9.5)

and

h(z) = 2p^{2} \frac{z^{2}}{1 − z} ∑_{k≥0} \frac{q^{2k}}{(1 − zq^{k})^{2}} = 2p^{2} \frac{z^{2}}{(1 − z)^{3}} + 2p^{2} ∑_{k≥1} [\frac{1}{(Q^{k} − 1)^{2}} · \frac{1}{1 − z} + …] .  (9.6)

Therefore

\begin{matrix}g_{n} = [z^{n}]g(z) = 2p^{2} ∑_{j≥1} [\frac{1}{Q^{j} − 1}(n + 1) − \frac{2}{Q^{j} − 1} − (\frac{1}{Q^{j} − 1})^{2}] \\ + 2p^{2} ∑_{1≤i<j} \frac{1}{(Q^{i} − 1)(Q^{j} − 1)} + O(Q^{−n}) = 2p^{2}[(n − 1)α − β] + 2p^{2} \frac{α^{2} − β}{2} + O(Q^{−n}) \end{matrix} (9.7)

and

h_{n} = [z^{n}]h(z) = 2p^{2}\binom{n}{2} + 2p^{2}β + O(Q^{−n}).  (9.8)

For the variance we must collect g_{n} + h_{n} + E_{n} − E_{n}^{2}, which is (up to exponentially small terms)

p^{2}[2(n − 1)α − 2β + α^{2} − β + n(n − 1) + 2β] + p[n + α] − p^{2}[n + α]^{2}.  (9.9)

Simplifying this expression we find Theorem 13. The variance V_{n} of left-to-right minima in the loose sense is for n → ∞

V_{n} = pqn + pα − p^{2}(2α + β) + O(Q^{−n}).  (9.10)

This time, the function q → pq has a maximum at p = q = \frac{1}{2}.

10. Conclusions

We made some numerical experiments and obtained good agreement with the predicted theoretical results.

Without going into details, probabilistic counting resembles coupon collecting (compare [3]), and we think that there is some work to be done analyzing combinatorial parameters in the context of geometrically distributed random variables. We hope to report on some other problems and results in the future.

Acknowledgments. W. Szpankowski provided additional references. P. Kirschenhofer made interesting remarks. The symbolic computation system Maple was quite helpful.

References

1. L.Devroye, Applications of the Theory of Records in the Study of Random Trees, Acta Informatica 26 (1988), 123–130.

2. L.Devroye, A limit theory for random skip lists, Annals of Applied Probability 2 (1992), 597–609.

3. P.Flajolet, D.Gardy and L.Thimonier, Probabilistic languages and random allocations, Lecture Notes in Computer Science 317 (1988), 239–253.

4. P.Flajolet and G.N.Martin, Probabilistic Counting Algorithms for Data Base Applications, J. Comp. Syst. Sci. 31 (1985), 182–209.

5. P.Flajolet and R.Sedgewick, Digital Search Trees Revisited, SIAM J. Comput. 15 (1986), 748–767.

6. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

7. R.Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, Stuttgart, 1982.

8. P.Kirschenhofer and H.Prodinger, On the Analysis of Probabilistic Counting, Lecture Notes in Mathematics (E.Hlawka, R.F.Tichy, eds.), vol. 1452, 1990, pp. 117–120.

9. P.Kirschenhofer and H.Prodinger, A Result in Order Statistics Related to Probabilistic Counting, submitted (1992).

10. P.Kirschenhofer,H.Prodinger and W.Szpankowski, How to Count Quickly and Accurately: A Unified Analysis of Probabilistic Counting and Other Related Problems, Lecture Notes in Computer Science (W.Kuich, ed.), vol. 623, 1992, pp. 211–222.

11. D.E.Knuth, The Art of Computer Science Vol.1, Addison-Wesley, Reading, MA, 1968.

12. D.E.Knuth, The Art of Computer Science Vol.3, Addison-Wesley, Reading, MA, 1973.

13. M.Lothaire, Combinatorics on Words, Addison Wesley, Reading, MA, 1982.

14. T.Papadakis, I.Munro and P.Poblete, Average search and update costs in skip lists, BIT 32 (1992), 316–332.

15. W.Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33 (1990), 668– 676.

16. R.Sedgewick, Mathematical analysis of combinatorial algorithms, Probability Theory and Computer Science (G.Louchard and G.Latouche, eds.), Academic Press, 1983, pp. 125–205.

17. W.Szpankowski and V.Rego, Yet another Application of a Binomial Recurrence: Order Statistics, Computing 43 (1990), 401–410.

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@email.tuwien.ac.at