COMBINATORICS OF GEOMETRICALLY DISTRIBUTED RANDOM VARIABLES: VALUE AND POSITION OF THE rTH LEFT–TO–RIGHT MAXIMUM

ARNOLD KNOPFMACHER AND HELMUT PRODINGER

Abstract. For words of length n, generated by independent geometric random variables, we consider the average value and the average position of the rth left–to–right maximum, for fixed r and n → ∞.

1. Introduction

For a permutation σ_{1}σ_{1} … σ_{n}, a left–to–right maximum (outstanding element, record, …) is an element σ_{j} with σ_{j} > σ_{i} for all i = 1, …, j − 1. The number of left–to– right maxima was first studied by Rényi [13], compare also [10]. A survey of results on this topic can be found in [5]. In particular the study of records has applications to observations of extreme weather problems, test of randomness, determination of minimal failure, stresses of electronic components, etc.

Recently Wilf in [14] proved the formula (1 − 2^{−r})n for the average value of the rth left–to–right maximum, for fixed r and n → ∞; for the average position he obtained the asymptotic formula (log n)^{r−1}/(r − 1)!.

In [12] the number of left–to–right maxima was investigated in the model of words (strings) a_{1} … a_{n}, where the letters a_{i} ∈ ℕ are independently generated according to the geometric distribution with ℙ{X = k} = pq^{k−1}, with p + q = 1. (We find it useful also to use the abbreviation Q = q^{−1}.) The motivation for this work comes from Computer Science. In this context records arise in the study of skip lists [11, 9] and probabilistic counting [2, 8]. Also, since equal letters are now allowed, there are two versions that should be considered in parallel, the standard version, and the weak version, where ‘<’ is replaced by ‘≤,’ which means that a new maximum only has to be larger or equal to the previous ones. The paper [12] contains asymptotic results about the average and the variance of the number of left–to–right maxima in the context of geometric random variables. (H.–K. Hwang and his collaborators obtained further results about the limiting behaviour in [1].)

Motivated by Wilf’s study we consider here the two parameters ‘value’ and ‘position’ of the rth left–to–right maximum for geometric random variables. Summarizing our results, we obtain the asymptotic formulæ \frac{r}{p} and \frac{1}{(r−1)!}(\frac{p}{q} log_{Q} n)^{r−1} resp. \frac{rq}{p} and

\frac{1}{(r−1)!}(p log_{Q} n)^{r−1} in the weak case.

Date: September 6, 1999.

A certain knowledge of [12] might be beneficial to understanding the present derivations.

It should be noted that not all random strings of length n have r left–to–right maxima.

Let us start with the value. The generating function of interest is

Value(z, u) := \frac{1}{1 − z} ∏_{i=1}^{h−1} \{1 + \frac{pq^{i−1}zu}{1 − (1 − q^{i})z} \} zpq^{h−1},  (1)

which originates from the (unique) decomposition of a string as a_{1}w_{1} … a_{r−1}w_{r−1}a_{r}w where a_{1}, …, a_{r} are the left–to–right maxima, the w_{i} are the strings between them, and w can be anything. Note that if a_{k} = l, then this corresponds to a term pq^{l−1}zu. Any letter in w_{k} can come with the probability 1 − q^{k}, and thus w_{k} corresponds to ∑_{j≥0}(1 − q^{k})^{j}z^{j} = 1/(1 − (1 − q^{k})z). A particular value i does not necessarily occur as a left–to–right maximum; that is reflected by the 1 + … in the product. However, when we look for the coefficient of u^{r−1}, we have seen r − 1 left–to–right maxima, and the rth has value h. What comes after that is irrelevant and covered by the factor 1/(1 − z).

(Compare [12] for similar generating functions.)

In the sequel we find it useful to use the abbreviation [[i]] := 1 − (1 − q^{i})z.

The coefficients of z^{n}u^{r−1} in Value(z, u), call them π_{n,h}^{(r)}, are not probabilities, because there exist words of length n with fewer than r left–to–right maxima, but the quantities π_{n,h}^{(r)}/π_{n}^{(r)} are, where π_{n}^{(r)} is the probability that a string of length n has r left–to–right maxima. We compute π_{n}^{(r)} from Value(z, u) by summing over all values h;

π_{n}^{(r)} := [z^{n}u^{r−1}]\frac{1}{1 − z} ∑_{h≥1} ∏_{i=1}^{h−1} \{1 + \frac{pq^{i−1}zu}{[[i]]}\} zpq^{h−1} = ∑_{h≥1} π_{n,h}^{(r)}.  (2)

Now we turn to the position. Set

σ_{n,j}^{(r)} := [z^{n}u^{r−1}v^{j}]\frac{1}{1 − z} ∑_{h≥1} ∏_{k=1}^{h−1} \{1 + \frac{pq^{k−1}zvu}{1 − (1 − q^{k})zv} \} zvpq^{h−1},  (3)

then σ_{n,j}^{(r)}/π_{n}^{(r)} is the probability that a random string of length n has the rth left– to–right maximum in position j. It is the same decomposition as before, however, we are not interested in the value h, so we sum over it. On the other hand, we label the position with the variable v, so we must make sure that every z that does not appear in the factor 1/(1 − z) must be multiplied by a v. In other words, every letter up to the rth left–to–right maximum will be marked by v, which means that we have as many v’s as the position. Computationally, we find it easier to work with the parameter “position −r.” For that, we don’t label the letters which are left–to–right maxima (there are r of them) by a v, so that we consequently have as many v’s as “position −r” indicates. This leads us to the generating function

Position(z, u, v) := \frac{1}{1 − z} ∑_{h≥1} ∏_{k=1}^{h−1} \{1 + \frac{pq^{k−1}zu}{1 − (1 − q^{k})zv} \} zpq^{h−1}.  (4)

We prefer this version since the variable v appears in fewer places, and the derivative with respect to v (needed for the expected value) produces fewer terms.

In some places we have to assume r ≥ 2. This is no restriction since the position of the first left–to–right maximum is obviously 1.

2. Some technical lemmas

In order to read off coefficients, we state the obvious but nevertheless very useful formula

[w^{n}] ∑_{i} a_{i}f(b_{i}w) = ∑_{i} a_{i}b_{i}^{n} · [w^{n}]f(w).

In all our applications, ∑_{i} a_{i}b_{i}^{n} can be summed in closed form.

We must often read off coefficients in iterated sums. To faciliate this, we state two lemmas that deal with all the situations we encounter.

Lemma 1. Assume that we have power series

A^{(j)}(w) = ∑_{n≥1} a_{n}^{(j)}w^{n}, j = 1, …, s.

Then

[w^{n}] ∑_{1≤i_{1}<i_{2}<···<i_{s}} A^{(1)}(wq^{i_{1}}) … A^{(s)}(wq^{i_{s}}) = ∑_{0=l_{0}<l_{1}<···<l_{s−1}<l_{s}=n} \frac{a_{l_{1}−l_{0}}^{(s)} … a_{l_{s}−l_{s−1}}^{(1)}}{(Q^{l_{1}} − 1) … (Q^{l_{s}} − 1)}.

Proof. For the sake of clarity, we treat the case s = 3 and leave it to the imagination of the reader to figure out the general case;

[w^{n}] ∑_{1≤i<j<h} A(wq^{i})B(wq^{j})C(wq^{h}) = ∑_{l} ∑_{1≤i<j<h}[w^{n−l}]A(wq^{i})B(wq^{j}) · [w^{l}]C(wq^{h})

= ∑_{l} \frac{1}{Q^{l} − 1} ∑_{1≤i<j}[w^{n−l}]A(wq^{i})B(wq^{j}) · [w^{l}]C(w)q^{jl}

= ∑_{l} \frac{c_{l}}{Q^{l} − 1} ∑_{1≤i<j}[w^{n}]A(wq^{i})B(wq^{j})(wq^{j})^{l}

= ∑_{l,m} \frac{c_{l}}{Q^{l} − 1} ∑_{1≤i<j}[w^{n−m}]A(wq^{i}) · [w^{m}]B(wq^{j})(wq^{j})^{l}

= ∑_{l,m} \frac{c_{l}}{(Q^{l} − 1)(Q^{m} − 1)} ∑_{1≤i}[w^{n−m}]A(wq^{i})q^{im} · [w^{m}]B(w)w^{l}

= ∑_{l,m} \frac{c_{l}b_{m−l}}{(Q^{l} − 1)(Q^{m} − 1)} ∑_{1≤i}[w^{n}]A(wq^{i})(wq^{i})^{m}

= ∑_{l,m} \frac{c_{l} b_{m−l} a_{n−m}}{(Q^{l} − 1)(Q^{m} − 1)(Q^{n} − 1)}.

Lemma 2.

[w^{n}] ∑_{1≤i_{1}<i_{2}<···<i_{s}} A^{(1)}(wq^{i_{1}}) … A^{(s)}(wq^{i_{s}}) i_{s}

= [t] ∑_{0=l_{0}<l_{1}<···<l_{s−1}<l_{s}=n} a_{l_{1}−l_{0}}^{(s)} … a_{l_{s}−l_{s−1}}^{(1)} ∏_{i=1}^{s} (\frac{1}{Q^{l_{i}} − 1} + t\frac{Q^{l_{i}}}{(Q^{l_{i}} − 1)^{2}} ).

Proof. The proof is essentially the same as before, if we note that

∑_{h>j} h q^{hl} = q^{jl}(\frac{Q^{l}}{(Q^{l} − 1)^{2}} + \frac{j}{Q^{l} − 1}).

Our quantities will eventually come out as alternating sums, and the appropriate treatment of them is Rice’s method which is surveyed in [4]; the key point is the following Lemma.

Lemma 3. 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,

where

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

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

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

where the sum is taken over all poles z_{0} different from 1, …, n. Poles that lie more to the left lead to smaller terms in the asymptotic expansion.

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.

3. The probability that there are r maxima

Now we want to read off the nth coefficients of the power series of interest. For this, it is beneficial to use the following formula:

[z^{n}]f(z) = (−1)^{n}[w^{n}](1 − w)^{n−1}f(\frac{w}{w − 1}).

This form can be found in [7] and is based on ideas concerning the Euler transform in [3]. Then the quantities come out automatically as alternating sums, and Rice’s method can be applied.

π_{n}^{(r)} = [z^{n}]\frac{1}{1 − z} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{pq^{i_{1}−1}z}{[[i_{1}]]} … \frac{pq^{i_{r−1}−1}z}{[[i_{r−1}]]} zpq^{h−1}

= (\frac{p}{q})^{r}[z^{n}]\frac{1}{1 − z} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}z}{[[i_{1}]]} … \frac{q^{i_{r−1}}z}{[[i_{r−1}]]}zq^{h}

= (−1)^{r}(\frac{p}{q})^{r}(−1)^{n}[w^{n}](1 − w)^{n−1} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}

= (−1)^{r}(\frac{p}{q})^{r} ∑_{k=r}^{n} \binom{n − 1}{k − 1}(−1)^{k}[w^{k}] ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}.

Now the evaluation of the inner sum can be done by our Lemma; k = n, r = s, A^{(1)}(w) = ⋯ = A^{(r−1)}(w) = \frac{w}{1−w}, A^{(r)}(w) = w. Therefore

[w^{k}] ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}

= ∑_{0=l_{0}<1=l_{1}<l_{2}<···<l_{r}=k} \frac{1}{(Q − 1)(Q^{l_{2}} − 1) … (Q^{l_{r}} − 1)}

= \frac{q}{p} ∑_{2≤l_{2}<···<l_{r}=k} \frac{1}{(Q^{l_{2}} − 1) … (Q^{l_{r}} − 1)}.

Thus

π_{n}^{(r)} = (−1)^{r−1}(\frac{p}{q})^{r−1} ∑_{k=r−1}^{n−1} \binom{n − 1}{k}(−1)^{k}f(k)

with

f(k) = ∑_{2≤l_{2}<···<l_{r}=k+1} \frac{1}{(Q^{l_{2}} − 1) … (Q^{l_{r}} − 1)}.

In order to apply Rice’s method one needs the continuation of f(k) to the complex plane. Using symmetric functions, one can always represent such iterated summations by powersums [10]

ϑ(k) := ∑_{l=2}^{k} \frac{1}{(Q^{l} − 1)^{d}} ,

and the task is reduced to finding an extension of this quantity ϑ(k) valid in the the complex plane. For this, the standard way of doing it is via

ϑ(z) := ∑_{l≥2} \frac{1}{(Q^{l} − 1)^{d}} − ∑_{l≥1} \frac{1}{(Q^{l+z} − 1)^{d}} .

However, we only need the values f(0), …, f(r − 2).

In [6] we learn how such a sum should be interpreted: As with integrals, a (definite) sum

∑_{a≤k<b} g(k)

is defined by G(b) − G(a), with an indefinite sum function. In particular, for a = b we get 0, as we should, and for instance ∑_{1≤k<−2} g(k) = −g(0) − g(1) − g(2). This idea can of course be iterated. Computer algebra systems like Maple deal with such ranges of summation correctly.

We thus find f(1) = ⋯ = f(r − 2) = 0 and

f(0) = (−1)^{r}(\frac{1}{Q − 1})^{r−1}.

Hence Rice’s method and the pole at z = 0 give us

π_{n}^{(r)} = 1 + O(\frac{1}{n}),

which is intuitively clear.

Note that there are poles at z = −1 + 2πik/ log Q, k ∈ ℤ, and they lead to a periodic fluctuation of order \frac{1}{n}; this phenomenon is well–known and appears in many places (compare [4] and some other references).

4. The average value of the rth maximum

Now we can safely deal with the quantities π_{n,h}^{(r)} alone, and the so computated average value E_{n}^{(r)} will be correct within an error term of the form 1 + O(\frac{1}{n}). We compute

E_{n}^{(r)} = ∑_{h≥1} h[z^{n}u^{r−1}]Value(z, u)

= [z^{n}]\frac{1}{1 − z} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{pq^{i_{1}−1}z}{[[i_{1}]]} … \frac{pq^{i_{r−1}−1}z}{[[i_{r−1}]]} zpq^{h−1}h

= (\frac{p}{q})^{r}[z^{n}]\frac{1}{1 − z} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}z}{[[i_{1}]]} … \frac{q^{i_{r−1}}z}{[[i_{r−1}]]}zq^{h}h

= (−1)^{r}(\frac{p}{q})^{r}(−1)^{n}[w^{n}](1 − w)^{n−1} ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}h

= (−1)^{r}(\frac{p}{q})^{r} ∑_{k=r}^{n} \binom{n − 1}{k − 1}(−1)^{k}[w^{k}] ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}h.

The inner sum is now evaluated by the (second) Lemma:

[w^{k}] ∑_{1≤i_{1}<···<i_{r−1}<h} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}wq^{h}h

= [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=k} ∏_{i=1}^{r} (\frac{1}{Q^{l_{i}} − 1} + t\frac{Q^{l_{i}}}{(Q^{l_{i}} − 1)^{2}} ).

Or,

E_{n}^{(r)} = (−1)^{r−1}(\frac{p}{q})^{r} ∑_{k=r−1}^{n−1} \binom{n − 1}{k}(−1)^{k}f(k)

with

f(k) = [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=k+1} ∏_{i=1}^{r} (\frac{1}{Q^{l_{i}} − 1} + t\frac{Q^{l_{i}}}{(Q^{l_{i}} − 1)^{2}} ).

Again, f(1) = ⋯ = f(r − 2) = 0 and since in general

∑_{1=l_{1}<l_{2}<···<l_{r}=1} a_{l_{1}}a_{l_{2}} … a_{l_{r}} = (−1)^{r}a_{1}a_{1} … a_{1},

we find

f(0) = [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=1} ∏_{i=1}^{r} (\frac{1}{Q^{l_{i}} − 1} + t\frac{Q^{l_{i}}}{(Q^{l_{i}} − 1)^{2}} )

= (−1)^{r}[t](\frac{1}{Q − 1} + t\frac{Q}{(Q − 1)^{2}} )^{r} = (−1)^{r}r\frac{Q}{(Q − 1)^{r+1}} .

Thus we have proved the following theorem

Theorem 1. The average value E_{n}^{(r)} of the rth left–to–right maximum in a random sequence of n elements, generated by geometric random variables is given by

E_{n}^{(r)} = \frac{r}{p} + O(\frac{1}{n}) for fixed r and n → ∞.

A full asymptotic expansion would be available, at least in principle, with more involved computations, as well as the variance.

Again, as in all the examples that will follow, the lower order terms contain periodic fluctuations of the form δ(log_{Q} n).

In many instances, the limit q → 1 produces the corresponding result for permutations. Here Theorem 1 would yield infinity. In the instance of permutations, as we know from [14], we have something proportional to n. In a sense, this in meaningful, since no (finite) constant would be appropriate.

5. The average position of the rth maximum

In order to compute this parameter (or rather the modified version), we have to differentiate the generating function Position(z, u, v) from the Introduction with respect to v and plug in v = 1. The desired average position of the rth left–to–right maximum (up to an error of the form 1 + O(1/n), as in the previous section) is then obtained via

[z^{n}u^{r−1}]\frac{∂}{∂v} Position(z, u, v)|_{v=1}

= [z^{n}](\frac{p}{q})^{r} \frac{1}{1 − z} [t] ∑_{1≤i_{1}<···<i_{r−1}<h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}z}{[[i_{j}]]} + t\frac{q^{i_{j}}z(1 − q^{i_{j}})z}{[[i_{j}]]^{2}} )zq^{h}

= (−1)^{n}[w^{n}](1 − w)^{n−1}(\frac{p}{q})^{r}(−1)^{r} ×

× [t] ∑_{1≤i_{1}<···<i_{r−1}<h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} − t\frac{q^{i_{j}}w(1 − q^{i_{j}})w}{(1 − q^{i_{j}}w)^{2}})wq^{h}

= (\frac{p}{q})^{r}(−1)^{r−1} ∑_{k=r−1}^{n−1} \binom{n − 1}{k}(−1)^{k}f(k)

where

f(k) = [w^{k+1}][t] ∑_{1≤i_{1}<···<i_{r−1}<h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} − t\frac{q^{i_{j}}w(1 − q^{i_{j}})w}{(1 − q^{i_{j}}w)^{2}})wq^{h} = f_{1}(k) + f_{2}(k)

with

f_{1}(k) = [t][w^{k}] ∑_{1≤i_{1}<···<i_{r−1}<h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} − t\frac{q^{i_{j}}w}{(1 − q^{i_{j}}w)^{2}} )wq^{h}

and

f_{2}(k) = [t][w^{k+1}] ∑_{1≤i_{1}<···<i_{r−1}<h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} + t\frac{(q^{i_{j}}w)^{2}}{(1 − q^{i_{j}}w)^{2}} )wq^{h}.

Now the two sums are in a form where our (first) technical lemma applies!

For f_{1}(k) note that A_{1}(w) = ⋯ = A_{r−1}(w) = \frac{w}{1−w} − \frac{tw}{(1−w)^{2}} and A_{r}(w) = w. Thus

f_{1}(k) = [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=k} \frac{(1 − t(l_{2} − l_{1})) … (1 − t(l_{r} − l_{r−1}))}{(Q^{l_{1}} − 1) … (Q^{l_{r}} − 1)}

= −(k − 1) ∑_{1=l_{1}<l_{2}<···<l_{r}=k} \frac{1}{(Q^{l_{1}} − 1) … (Q^{l_{r}} − 1)}.

For f_{2}(k) note that A_{1}(w) = ⋯ = A_{r−1}(w) = \frac{w}{1−w} + \frac{tw^{2}}{(1−w)^{2}} and A_{r}(w) = w. Thus

f_{2}(k) = [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=k+1} \frac{(1 + t(l_{2} − l_{1} − 1)) … (1 + t(l_{r} − l_{r−1} − 1))}{(Q^{l_{1}} − 1) … (Q^{l_{r}} − 1)}

= (k − r) ∑_{1=l_{1}<l_{2}<···<l_{r}=k+1} \frac{1}{(Q^{l_{1}} − 1) … (Q^{l_{r}} − 1)}.

As we know from before, it is the “value” (the behaviour) of f(0) that is required. It is f_{1}(0) that is dominant here: Since in general

∑_{2≤l_{2}<···<l_{r−1}<0} a_{l_{2}} … a_{l_{r−1}} = (−1)^{r} \frac{a_{0}^{r−1} − a_{1}^{r−1}}{a_{0} − a_{1}} ,

we find that as z → 0

f(z) ∼ \frac{(−1)^{r}}{(Q − 1)(Q^{z} − 1)^{r−1}} .

In [4] it is explained in detail what kind of contribution an rth order pole at z = 0 gives. The sum from Example 1 (loc. cit. on page 107) is what we need here;

∑_{k=1}^{n} \binom{n}{k}\frac{(−1)^{k}}{k^{m}} = \frac{log^{m} n}{m!} + O(log^{m−1} n).

Therefore we obtain the following theorem.

Theorem 2. The average position of the rth left–to–right maximum in a random sequence of n elements, generated by geometric random variables is given by

\frac{1}{(r − 1)!}(\frac{p}{q} log_{Q} n)^{r−1} + O( log^{r−2} n) for fixed r ≥ 2 and n → ∞.

Here, the limit q → 1 produces the correct expression

\frac{(log n)^{r−1}}{(r − 1)!}

that holds in the instance of permutations. (See [14].)

6. Weak left–to–right maxima; the value

We mention here briefly the analogous developments for the instance of weak left–to– right maxima.

The generating function of interest is

\frac{1}{1 − z} ∏_{i=1}^{h−1} \{1 − \frac{pq^{i−1}zu}{[[i − 1]]}\}^{−1}pq^{h−1}z,

and the coefficient of u^{r−1} therein is

\frac{1}{1 − z} ∑_{1≤i_{1}≤···≤i_{r−1}≤h} \frac{pq^{i_{1}−1}z}{[[i_{1} − 1]]} … \frac{pq^{i_{r−1}−1}z}{[[i_{r−1}]]} pq^{h−1}z

= p^{r} \frac{1}{1 − z} ∑_{0≤i_{1}≤···≤i_{r−1}≤h} \frac{q^{i_{1}}z}{[[i_{1}]]} … \frac{q^{i_{r−1}}z}{[[i_{r−1}]]}q^{h}z.

The technical lemmas that we need now are

Lemma 4.

[w^{n}] ∑_{0≤i_{1}≤i_{2}≤···≤i_{s}} A^{(1)}(wq^{i_{1}}) … A^{(s)}(wq^{i_{s}}) = ∑_{0=l_{0}<l_{1}<···<l_{s−1}<l_{s}=n} \frac{a_{l_{1}−l_{0}}^{(s)} … a_{l_{s}−l_{s−1}}^{(1)}}{(1 − q^{l_{1}}) … (1 − q^{l_{s}})}

and

[w^{n}] ∑_{0≤i_{1}≤i_{2}≤···≤i_{s}} A^{(1)}(wq^{i_{1}}) … A^{(s)}(wq^{i_{s}}) (i_{s} + 1)

= [t] ∑_{0=l_{0}<l_{1}<···<l_{s−1}<l_{s}=n} a_{l_{1}−l_{0}}^{(s)} … a_{l_{s}−l_{s−1}}^{(1)} ∏_{i=1}^{s} (\frac{1}{1 − q^{l_{i}}} + t\frac{q^{l_{i}}}{(1 − q^{l_{i}})^{2}} ).

We find

E_{n}^{(r)} = (−1)^{r−1}p^{r} ∑_{k=r−1}^{n−1} \binom{n − 1}{k}(−1)^{k}f(k)

with

f(k) = [t] ∑_{1=l_{1}<l_{2}<···<l_{r}=k+1} ∏_{i=1}^{r} (\frac{1}{1 − q^{l_{i}}} + t\frac{q^{l_{i}}}{(1 − q^{l_{i}})^{2}} ).

Also, f(0) = (−1)^{r}r\frac{q}{(1−q)^{r+1}} and thus

Theorem 3. The average value E_{n}^{(r)} of the rth left–to–right maximum (in the weak sense) in a random sequence of n elements, generated by geometric random variables is given by

E_{n}^{(r)} = \frac{r q}{p} + O(\frac{1}{n}) for fixed r and n → ∞.

7. Weak left–to–right maxima; the position

The probability generating funtion of interest (up to normalization by a factor that is basically 1, as before) is given by

\frac{1}{1 − z} ∑_{h≥1} ∏_{i=1}^{h−1} \{1 − \frac{pq^{i−1}zvu}{1 − (1 − q^{i})zv} \}^{−1} zvpq^{h−1},

and the desired expectated value is

[z^{n}]p^{r} \frac{1}{1 − z} ∑_{0≤i_{1}≤···≤i_{r−1}≤h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}z}{[[i_{j}]]} + t\frac{q^{i_{j}}z(1 − q^{i_{j}})z}{[[i_{j}]]^{2}} )zq^{h}

= p^{r}(−1)^{r−1} ∑_{k=r−1}^{n−1} \binom{n − 1}{k}(−1)^{k}f(k)

with f(k) = f_{1}(k) + f_{2}(k) and

f_{1}(k) = [t][w^{k}] ∑_{0≤i_{1}≤···≤i_{r−1}≤h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} − t\frac{q^{i_{j}}w}{(1 − q^{i_{j}}w)^{2}} )wq^{h}

and

f_{2}(k) = [t][w^{k+1}] ∑_{0≤i_{1}≤···≤i_{r−1}≤h} ∏_{j=1}^{r−1} (\frac{q^{i_{j}}w}{1 − q^{i_{j}}w} + t\frac{(q^{i_{j}}w)^{2}}{(1 − q^{i_{j}}w)^{2}} )wq^{h}.

We find

f_{1}(k) = −(k − 1) ∑_{1=l_{1}<l_{2}<···<l_{r}=k} \frac{1}{(1 − q^{l_{1}}) … (1 − q^{l_{r}})}

and

f_{2}(k) = (k − r) ∑_{1=l_{1}<l_{2}<···<l_{r}=k+1} \frac{1}{(1 − q^{l_{1}}) … (1 − q^{l_{r}})}.

As z → 0

f(z) ∼ \frac{(−1)^{r}}{(1 − q)(1 − q^{z})^{r−1}} ,

and thus

Theorem 4. The average position of the rth left–to–right maximum (in the weak sense) in a random sequence of n elements, generated by geometric random variables is given by

\frac{1}{(r − 1)!}(p log_{Q} n)^{r−1} + O( log^{r−2} n) for fixed r ≥ 2 and n → ∞.

References

[1] Z.-D. Bai, H.-K. Hwang, and W.-Q. Liang. Normal approximations of the number of records in geometrically distributed random variables. Random Structures and Algorithms, 13:319–334, 1998.

[2] P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31:182–209, 1985.

[3] P. Flajolet and B. Richmond. Generalized digital trees and their difference–differential equations. Random Structures and Algorithms, 3:305–320, 1992.

[4] P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: Finite differences and Rice’s integrals. Theoretical Computer Science, 144:101–124, 1995.

[5] N. Glick. Breaking records and breaking boards. American Mathematical Monthly, 85:2–26, 1978.

[6] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[7] P. Kirschenhofer, C. Martínez, and H. Prodinger. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science, 144:199–220, 1995.

[8] P. Kirschenhofer and H. Prodinger. A result in order statistics related to probabilistic counting. Computing, 51:15–27, 1993.

[9] P. Kirschenhofer and H. Prodinger. The path length of random skip lists. Acta Informatica, 31:775–792, 1994.

[10] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1968. Third edition, 1997.

[11] T. Papadakis, I. Munro, and P. Poblete. Average search and update costs in skip lists. BIT, 32:316–332, 1992.

[12] H. Prodinger. Combinatorics of geometrically distributed random variables: Left-to-right maxima. Discrete Mathematics, 153:253–270, 1996.

[13] A. Rényi. Théorie des éléments saillants d’une suite d’observations. Ann. Fac. Sci. Univ. Clermont-Ferrand, 8:7–13, 1962.

[14] H. Wilf. On the outstanding elements of permutations. http://www.cis.upenn.edu/∼wilf, 1995.

Arnold Knopfmacher, Centre for Applicable Analysis and Number Theory, Department of Applied Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa, email: arnoldk@gauss.cam.wits.ac.za.

Helmut Prodinger, 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.