COMBINATORICS OF GEOMETRICALLY DISTRIBUTED RANDOM VARIABLES:

VALUE AND POSITION OF LARGE LEFT–TO–RIGHT MAXIMA

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 counted from the right, for fixed r and n → ∞. This complements previous research [5] where the analogous questions were considered for the rth left–to–right maximum counted from the left.

1. Introduction

In this paper we study sequences with respect to the left–to–right maxima of the elements of the sequence.

This paper is a companion paper to [5], and these two papers should be read together.

In [6] 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},  where p + q = 1.  (1)

(An element is a left–to–right maximum if it is larger than all the elements to the left. The version where ‘larger’ is replaced by ‘larger or equal’ would be also of interest but is not considered here.)

In [5] we considered the two parameters ‘value’ and ‘position’ of the rth left–to–right maximum for geometric random variables and obtained the asymptotic formulæ \frac{r}{p} and

\frac{1}{(r−1)!}(\frac{p}{q} log_{Q} n)^{r−1}.

These results cover the instances of small left–to–right maxima; therefore we investigate here the instance of large left–to–right maxima. We say that the last left–to–right maximum is the instance r = 1, the previous left–to–right maximum is the instance r = 2, and so on.

As can be seen in the forthcoming book [4], in the limit q → 1 the model becomes the model of random permutations. The concept of ‘value’ does not carry over, but the concept of ‘position’ does.

The largest element in a random permutation of n elements (which is n) is expected to be in the middle. The second largest is then expected to be in the middle of the first half, and so on. In general, the average position should be about \frac{n}{2^{r}}.

Date: May 11, 2001.

We find it useful to use the additional notations Q := q^{−1}, L := log Q, and [[i]] := 1 − (1 − q^{i})z.

In [6], compare also [8], the average value of the height was considered. The average height is asymptotic to log_{Q} n. The same formula comes out for the instance r = 1 of the average value of left–to–right maxima, counted from the right. Intuitively, for fixed r, the same asymptotic formula is to be expected, the depency of r only appearing in the lower order terms.

It should be noted that not all random strings of length n have r left–to–right maxima. However, as explained already in [5], this happens with low probability and can be ignored.

2. The average value of the rth left–to–right maximum from the right

The following expression for the average value of the rth left–to–right maximum from the right is obtained as in [5]; just observe that we assume that it is h, and that r − 1 more left–to–right maxima follow to the right, whereas to the left everything is smaller than h:

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

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

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

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

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

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

For the computation of the inner sum we need the following formula, which can be computed by elementary manipulations. For n ≥ m we have

[w^{n}] ∑_{h≥1} \frac{hwq^{h}}{(1 − wq^{h−1})(1 − wq^{h})}(wq^{h})^{m} = \frac{q}{p} \frac{q^{m} − q^{n}}{(1 − q^{n})^{2}} .

Using this and the principle that

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

we find that

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

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

It is worthwhile to note the instance r = 1, which is the maximum:

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

This checks with previous results, see [6, 8], but it seems to be a folklore result.

Now define the function

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

With this notation, we have

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

Since our quantities come out as alternating sums, the appropriate treatment of them is Rice’s method which is surveyed in [3]; the key point is the following Lemma.

Lemma 1. 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 [3]) 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.

Therefore a key issue is to extend sequences like ϕ_{r}(k) to the complex plane, in other words, give a meaningful definition of ϕ_{r}(z), for z ∈ ℂ.

Note that

∑_{0<i_{1}<···<i_{s}<j} \frac{1}{Q^{i_{1}} − 1} … \frac{1}{Q^{i_{s}} − 1} = [x^{s}] ∏_{i=1}^{j−1} (1 + \frac{x}{Q^{i} − 1})

= [x^{s}] ∏_{i=1}^{j−1} \frac{Q^{i} − 1 + x}{Q^{i} − 1}

= [x^{s}] ∏_{i=1}^{j−1} \frac{1 − (1 − x)q^{i}}{1 − q^{i}}

= [x^{s}]\frac{((1 − x)q; q)_{j−1}}{(q; q)_{j−1}} .

In this computation we use the standard notation for q–factorials,

(a; q)_{n} := (1 − a)(1 − aq) … (1 − aq^{n−1}), (a; q)_{∞} := (1 − a)(1 − aq) …,

see e. g. [1]. In the following we need Cauchy’s theorem (q–binomial theorem), viz.

∑_{n≥0} \frac{(a; q)_{n}}{(q; q)_{n}} t^{n} = \frac{(at; q)_{∞}}{(t; q)_{∞}} .

Then

ϕ_{r}(k) = [x^{r−2}] ∑_{1≤l≤k} \frac{((1 − x)q; q)_{l−1}}{(q; q)_{l−1}} \frac{q^{l} − q^{k}}{Q^{l} − 1}

= [x^{r−2}] ∑_{1≤l≤k} \frac{((1 − x)q; q)_{l−1}}{(q; q)_{l}} (q^{2l} − q^{k+l})

= [x^{r−2}][t^{k}]\frac{1}{1 − t} ∑_{l≥1} \frac{((1 − x)q; q)_{l−1}}{(q; q)_{l}} (q^{2l} − q^{k+l})t^{l}

= [x^{r−2}][t^{k}]\frac{1}{1 − t} \frac{1}{x}( − (1 − q^{k}) + ∑_{l≥0} \frac{(1 − x; q)_{l}}{(q; q)_{l}} (q^{2l} − q^{k+l})t^{l})

= [x^{r−1}][t^{k}]\frac{1}{1 − t}( − (1 − q^{k}) + \frac{((1 − x)q^{2}t); q)_{∞}}{(q^{2}t; q)_{∞}} − q^{k} \frac{((1 − x)qt; q)_{∞}}{(qt; q)_{∞}} )

= −[x^{r−1}][t^{k}]\frac{1}{1 − t}((1 − q^{k}) + (q^{k} − 1)\frac{((1 − x)qt; q)_{∞}}{(qt; q)_{∞}} + \frac{((1 − x)q^{2}t; q)_{∞}}{(qt; q)_{∞}} xqt)

= −δ_{r1}(1 − q^{k}) − [x^{r−1}][t^{k}]((q^{k} − 1)\frac{((1 − x)qt; q)_{∞}}{(t; q)_{∞}} + \frac{((1 − x)q^{2}t; q)_{∞}}{(t; q)_{∞}} xqt)

= −δ_{r1}(1 − q^{k}) − [x^{r−1}]((q^{k} − 1)\frac{((1 − x)q; q)_{k}}{(q; q)_{k}} + xq \frac{((1 − x)q^{2}; q)_{k−1}}{(q; q)_{k−1}} )

= −δ_{r1}(1 − q^{k}) − [x^{r−1}]((q^{k} − 1)\frac{((1 − x)q; q)_{k}}{(q; q)_{k}} + \frac{xq(1 − q^{k})}{1 − (1 − x)q} \frac{((1 − x)q^{2}; q)_{k}}{(q; q)_{k}} ).

Hence

\frac{ϕ_{r}(k)}{1 − q^{k}} = −δ_{r1} + [x^{r−1}](\frac{((1 − x)q; q)_{k}}{(q; q)_{k}} − \frac{xq}{1 − (1 − x)q} \frac{((1 − x)q^{2}; q)_{k}}{(q; q)_{k}} )

and

\frac{ϕ_{r}(k)}{1 − q^{k}} |_{k=0} = −δ_{r1} + [x^{r−1}](1 − \frac{xq}{1 − (1 − x)q} )

= −[x^{r−1}]\frac{xq}{1 − (1 − x)q}

= −\frac{q}{p}[x^{r−2}]\frac{1}{1 + \frac{xq}{p}}

= (−1)^{r−1}(\frac{q}{p})^{r−1}.

To get lower order terms, we first note that

\frac{((1 − x)q; q)_{z}}{(q; q)_{z}} ∼ 1 + L ∑_{j≥1} \frac{xq^{j}}{(1 − q^{j})(1 − (1 − x)q^{j})} · z (z → 0)

and (for r ≥ 2)

[x^{r−1}]L ∑_{j≥1} \frac{xq^{j}}{(1 − q^{j})(1 − (1 − x)q^{j})} · z = L(−1)^{r} ∑_{j≥1} \frac{q^{j(r−1)}}{(1 − q^{j})^{r}} · z.

Also note that

\frac{xq}{1 − (1 − x)q} \frac{((1 − x)q^{2}; q)_{z}}{(q; q)_{z}}

∼ \frac{xq}{1 − (1 − x)q} + \frac{xq}{1 − (1 − x)q} L ∑_{j≥1} \frac{xq^{j+1}}{(1 − q^{j})(1 − (1 − x)q^{j+1})} · z

= \frac{xq}{1 − (1 − x)q} + xqL ∑_{j≥1} \frac{q^{j}}{(1 − q^{j})^{2}} [−\frac{1}{1 + \frac{qx}{p}} + \frac{1}{1 + \frac{q^{j+1}x}{1−q^{j+1}}} ] · z

and (for r ≥ 2)

[x^{r−1}]xqL ∑_{j≥1} \frac{q^{j}}{(1 − q^{j})^{2}} [−\frac{1}{1 + \frac{qx}{p}} + \frac{1}{1 + \frac{q^{j+1}x}{1−q^{j+1}}} ] · z

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

Hence

\frac{ϕ_{r}(z)}{1 − q^{z}} ∼ (−1)^{r−1}(\frac{q}{p})^{r−1} + β_{r} · z  (z → 0),

with

β_{r} = L(−1)^{r} ∑_{j≥1} \frac{q^{j(r−1)}}{(1 − q^{j})^{r}} + qL(−1)^{r} ∑_{j≥1} \frac{q^{j}}{(1 − q^{j})^{2}} [(\frac{q}{p})^{r−2} − (\frac{q^{j+1}}{1 − q^{j+1}} )^{r−2}] .

Computing the residue of

\frac{1}{z} \frac{1}{1 − q^{z}} \frac{ϕ_{r}(z)}{1 − q^{z}}

at z = 0 eventually leads to

Theorem 1. The average value of the rth left–to–right maximum from the right is given by

E_{n}^{(r)} = log_{Q} n + σ_{r} + δ_{r}(log_{Q} n) + o(1),

where δ_{r}(x) is a small periodic function of log_{Q} n (originating from the poles at 2kπi/ log Q, k ∈ ℤ \ {0}). The constant σ_{r} is given by

σ_{r} = \frac{γ}{L} + \frac{1}{2} − p^{r−1} ∑_{j≥1} \frac{q^{(j−1)(r−1)}}{(1 − q^{j})^{r}} − p ∑_{j≥1} \frac{q^{j}}{(1 − q^{j})^{2}} + p^{r−1} ∑_{j≥1} \frac{q^{j(r−1)}}{(1 − q^{j})^{2}(1 − q^{j+1})^{r−2}} .

This holds for r = 1 as well, when the 3 sums combined evaluate to 0.

For interest, let us note the following limit:

lim_{q→1}(1 − q)σ_{r} = ∑_{k=3}^{r−3}(r − 1 − k)ζ(k) + (r − 1)ζ(2) + ζ(r − 2) − ζ(r) − \frac{r(r − 3)}{2}.

3. The average position of the rth left–to–right maximum from the right

We consider the generating function

∑_{h≥1} \frac{zpq^{h−1}}{(1 − zv(1 − q^{h−1}))[[h]]} ∑_{h<i_{1}<···<i_{r−1}} \frac{zpq^{i_{1}−1}}{[[i_{1}]]} … \frac{zpq^{i_{r−1}−1}}{[[i_{r−1}]]} ,

where v marks the elements to the left of the rth left–to–right maximum from the right. The actual position is then one more than the number of v’s, but that is overshadowed by the error term anyway. To get the average, we must differentiate this with respect to v, and then replace v by 1. The result is

∑_{h≥1} \frac{zpq^{h−1}z(1 − q^{h−1})}{[[h − 1]]^{2}[[h]]} ∑_{h<i_{1}<···<i_{r−1}} \frac{zpq^{i_{1}−1}}{[[i_{1}]]} … \frac{zpq^{i_{r−1}−1}}{[[i_{r−1}]]}

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

= (−1)^{r−1}(\frac{p}{q})^{r}(1 − w) ∑_{h≥1} \frac{wq^{h}w(1 − q^{h−1})}{(1 − wq^{h−1})^{2}(1 − wq^{h})} ∑_{h<i_{1}<···<i_{r−1}} \frac{wq^{i_{1}}}{1 − wq^{i_{1}}} … \frac{wq^{i_{r−1}}}{1 − wq^{i_{r−1}}} .

Therefore

E_{n}^{(r)} = (−1)^{n}[w^{n}](−1)^{r−1}(\frac{p}{q})^{r}(1 − w)^{n} ∑_{h≥1} \frac{wq^{h}w(1 − q^{h−1})}{(1 − wq^{h−1})^{2}(1 − wq^{h})} ×

× ∑_{h<i_{1}<···<i_{r−1}} \frac{wq^{i_{1}}}{1 − wq^{i_{1}}} … \frac{wq^{i_{r−1}}}{1 − wq^{i_{r−1}}}

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

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

For the computation of the inner sum we need

[w^{k}] ∑_{h≥1} \frac{(wq^{h})^{M}}{(1 − wq^{h−1})^{2}(1 − wq^{h})}

= −\frac{q^{M+1}}{(1 − q)^{2}} \frac{1}{1 − q^{k}} + \frac{q^{M}}{1 − q} \frac{1}{1 − q^{k}} (k + 1 − M) + \frac{q^{2}}{(1 − q)^{2}} \frac{1}{Q^{k} − 1}

and also (as a consequence)

[w^{k}] ∑_{h≥1} \frac{(wq^{h})^{M}w(1 − q^{h−1})}{(1 − wq^{h−1})^{2}(1 − wq^{h})}

= −\frac{q^{m+2}}{(1 − q)^{2}} \frac{1}{1 − q^{k−1}} + \frac{q^{m+1}}{1 − q} \frac{1}{1 − q^{k−1}} (k − m − 1) + \frac{q^{2}}{(1 − q)^{2}} \frac{1}{Q^{k−1} − 1}

+ \frac{q^{m+2}}{(1 − q)^{2}} \frac{1}{1 − q^{k}} − \frac{q^{m+1}}{1 − q} \frac{1}{1 − q^{k}} (k − m − 1) − \frac{q^{2}}{(1 − q)^{2}} \frac{1}{Q^{k} − 1}.

The righthand side will be denoted by τ(k, m) and can alternatively be written as

τ(k, m) = −\frac{q^{m+2}}{p^{2}} \frac{1}{Q^{k−1} − 1} + \frac{q^{m+1}}{p} \frac{1}{Q^{k−1} − 1}(k − m − 1) + \frac{q^{2}}{p^{2}} \frac{1}{Q^{k−1} − 1}

+ \frac{q^{m+2}}{p^{2}} \frac{1}{Q^{k} − 1} − \frac{q^{m+1}}{p} \frac{1}{Q^{k} − 1}(k − m − 1) − \frac{q}{p^{2}} \frac{1}{Q^{k} − 1}.

Consequently

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

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

It is instructive to start with the case r = 1:

E_{n}^{(1)} = \frac{p}{q} ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[w^{k}] ∑_{h≥1} \frac{wq^{h}w(1 − q^{h−1})}{(1 − wq^{h−1})^{2}(1 − wq^{h})}

= \frac{p}{q} ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[\frac{q}{p} \frac{k − 1}{Q^{k−1} − 1} − \frac{q}{p} \frac{k}{Q^{k} − 1}]

= ∑_{k=2}^{n} \binom{n}{k}(−1)^{k}[\frac{k − 1}{Q^{k−1} − 1} − \frac{k}{Q^{k} − 1}].

When applying Rice’s formula, it turns out that the dominant singularity is at z = 1. This matches the intuition, since the position should be roughly at ≈ const · n.

Indeed, apart from fluctuations (coming from complex poles at z = 1 + 2kπi/ log Q, with k ∈ ℤ \ \{0\}) we get E_{n}^{(1)} ∼ n(\frac{1}{L} − \frac{q}{p}).

Formally, for q → 1, we get \frac{n}{2}, as it should.

Now, for the general case, define the function

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

We need the value ψ_{r}(1), because of the result (apart from fluctuations)

E_{n}^{(r)} ∼ (−1)^{r−1}(\frac{p}{q})^{r}ψ_{r}(1) n.  (2)

We want to study the constants in more detail. Assume r = 2. Since τ(z, z − 1) = 0, the adaequate extension is

VALUE AND POSITION OF LARGE LEFT–TO–RIGHT MAXIMA 9

ψ_{2}(z) = ∑_{l≥1} \frac{1}{Q^{l} − 1}τ(z, l) − ∑_{l≥1} \frac{1}{Q^{l+z−1} − 1}τ(z, l + z − 1).

An elementary computation yields

τ(z, l) ∼ \frac{−(l − 1)q^{l+2} + lq^{l+1} − q^{2}}{Lp^{2}} \frac{1}{z − 1}

+ \frac{q^{l+1}}{pL} + \frac{1}{2p^{3}} [−3q^{2} + q^{3} + lq^{l+1} + q^{l+2} − (l − 1)q^{l+3}] + …,

τ(z, z + l − 1) ∼ \frac{−(l − 1)q^{l+2} + lq^{l+1} − q^{2}}{Lp^{2}} \frac{1}{z − 1}

+ \frac{1}{2p^{3}} [−3q^{2} + q^{3} + 3lq^{l+1} − (4l − 3)q^{l+2} + lq^{l+3}] ,

\frac{1}{Q^{l+z−1} − 1} ∼ \frac{1}{Q^{l} − 1} + \frac{LQ^{l}}{(Q^{l} − 1)^{2}} (z − 1) + ….

Hence

ψ_{2}(1) = \frac{1}{pL} ∑_{l≥1} \frac{q^{l+1}}{Q^{l} − 1} + \frac{1}{p^{3}} ∑_{l≥1} \frac{1}{Q^{l} − 1} [−lq^{l+1} + (2l − 1)q^{l+2} − (l − 1)q^{l+3}]

+ \frac{1}{p^{2}} ∑_{l≥1} \frac{Q^{l}}{(Q^{l} − 1)^{2}} [(l − 1)q^{l+2} − lq^{l+1} + q^{2}]

= \frac{q}{pL} ∑_{l≥1} \frac{1}{Q^{l} − 1} − \frac{q^{2}}{p^{2}L} + \frac{q^{2}(q + 1)}{p^{3}} − \frac{q}{p} ∑_{l≥1} \frac{lQ^{l}}{(Q^{l} − 1)^{2}}

and thus

−\frac{p^{2}}{q^{2}} ψ_{2}(1) = −\frac{p}{qL} ∑_{l≥1} \frac{1}{Q^{l} − 1} + \frac{p}{q} ∑_{l≥1} \frac{lQ^{l}}{(Q^{l} − 1)^{2}} + \frac{1}{L} − \frac{1}{p} − \frac{q}{p}.

It is our aim to show now that for q → 1 this quantity approaches \frac{1}{4}. For this, we write q = e^{−t} and study the behaviour at t → 0. The Mellin transform allows as to write

∑_{l≥1} \frac{1}{Q^{l} − 1} = \frac{1}{2πi} ∫_{3−i∞}^{3+i∞} ζ^{2}(s)Γ(s)t^{−s}ds,
∑_{l≥1} \frac{lQ^{l}}{(Q^{l} − 1)^{2}} = \frac{1}{2πi} ∫_{3−i∞}^{3+i∞} ζ^{2}(s − 1)Γ(s)t^{−s}ds.

Shifting the line of integration and collecting residues gives us the following asymptotic expansions (see [2] for a friendly explanation of the subject):

∑_{l≥1} \frac{1}{Q^{l} − 1} = −\frac{log t}{t} + \frac{γ}{t} + \frac{1}{4} + O(t),

∑_{l≥1} \frac{lQ^{l}}{(Q^{l} − 1)^{2}} = −\frac{log t}{t^{2}} + \frac{1 + γ}{t^{2}} + O(1).

Using that, we find

−\frac{p^{2}}{q^{2}} ψ_{2}(1) = \frac{1}{4} − \frac{t}{9} + O(t^{2}) = \frac{1}{4} + \frac{1}{9} log q + O(log^{2} q).

In the general case, the suitable extension is

ψ_{r}(z) = ∑_{l≥1} g_{r−2}(l)\frac{τ(z, l)}{Q^{l} − 1} − ∑_{l≥1} g_{r−2}(l + z − 1)\frac{τ(z, l + z − 1)}{Q^{l+z−1} − 1},

with

g_{s}(l) = ∑_{1≤i_{1}<···<i_{s}<l} \frac{1}{Q^{i_{1}} − 1} … \frac{1}{Q^{i_{s}} − 1},

and the suitable extension of g_{s}(l). The latter is, at least theoretically, no problem, since we can, as already explained in [5], use powersum symmetric functions (see [7]) for the extension (or proceed as in the last section).

For instance,

g_{1}(z) = ∑_{i≥1} \frac{1}{Q^{i} − 1} − ∑_{i≥1} \frac{1}{Q^{i+z−1} − 1}

and

g_{1}(l + z − 1) = g_{1}(l) + L ∑_{i≥l} \frac{Q^{i}}{(Q^{i} − 1)^{2}} (z − 1) + …,

as z → 1.

Using this, one could write an explicit formula for ψ_{3}(1) which is already extremely messy.

Since already the quantity ψ_{2}(1) cannot be simplified, there is no hope for closed forms here.

It is possible to make the translation to permutations (the limit q → 1) at an earlier stage.

Note that

lim_{q→1}(1 − q)τ(k, m) = \frac{1}{2} − \frac{(m + 1)m}{2k} + \frac{m(m − 1)}{2(k − 1)}.

Hence the constant in (2) translates into

λ_{r} := (−1)^{r−1} ∑_{0<l_{1}<···<l_{r−1}≤k−1} \frac{1}{l_{1} … l_{r−1}} [\frac{1}{2} − \frac{(l_{r−1} + 1)l_{r−1}}{2k} + \frac{l_{r−1}(l_{r−1} − 1)}{2(k − 1)}]|_{k=1}.

Observe that

∑_{0<l_{1}<···<l_{r−2}<l} \frac{1}{l_{1} … l_{r−2}} = [x^{r−2}] ∏_{i=1}^{l−1} (1 + \frac{x}{i}) = [x^{r−2}]\frac{Γ(l + x)}{Γ(1 + x)Γ(l)}.

Hence

λ_{r} = −\frac{1}{2}[x^{r−2}] ∑_{1≤l≤k−1} \frac{Γ(l − x)}{Γ(1 − x)Γ(l)} [\frac{1}{l} − \frac{l + 1}{k} + \frac{l − 1}{k − 1}] |_{k=1}

= [x^{r−2}]\frac{1}{2x} [\frac{2Γ(k + 1 − x)}{Γ(k + 1)Γ(3 − x)} − 1] |_{k=1}

= [x^{r−2}]\frac{1}{4} \frac{1}{1 − \frac{x}{2}} = 2^{−r},

as it should be.

In this permutation case we can even do better and compute the next term (of order 1), because of

E_{n}^{(r)} ∼ (−1)^{r−1}(\frac{p}{q})^{r}(ψ_{r}(1) n − ψ_{r}(0)).

All we have to do is to compute the following quantity:

μ_{r} = (−1)^{r−1} ∑_{0<l_{1}<···<l_{r−1}≤k−1} \frac{1}{l_{1} … l_{r−1}} [\frac{1}{2} − \frac{(l_{r−1} + 1)l_{r−1}}{2k} + \frac{l_{r−1}(l_{r−1} − 1)}{2(k − 1)}]|_{k=0}

= [x^{r−2}] (\frac{1}{1 − x} − \frac{1}{4} \frac{1}{1 − \frac{x}{2}} ) = 1 − 2^{−r}.

Since there are no more poles to the left and a technical growth condition (see [3]) is satisfied, there are no more terms, and we have the exact formula for the average position of the rth left–to–right maximum, counted from the right (remember that we counted one less than the position!):

E_{n}^{(r)} + 1 = \frac{n + 1}{2^{r}}.

Theorem 2. The average position of the r–th left–to–right maximum from the right is given by

E_{n}^{(r)} = (−1)^{r}(\frac{p}{q})^{r−1}ψ_{r}(1) n + ϖ_{r}(log_{Q} n) + o(n),

where the constants are defined in the text, and ϖ_{r}(x) is a small periodic function, originating from the complex poles 1 + 2kπi/ log Q.

In the limit q → 1 (permutations), this simplifies to

E_{n}^{(r)} = \frac{n}{2^{r}} + o(n).

References

[1] G. Andrews. The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications. Addison–Wesley, 1976.

[2] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoretical Computer Science, 144:3–58, 1995.

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

[4] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2005.

[5] A. Knopfmacher and H. Prodinger. Combinatorics of geometrically distributed random variables: Value and position of the rth left-to-right maximum. Discrete Mathematics, 226:255–267, 2001.

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

[7] R. Stanley. Enumerative combinatorics. Vol. 2. Cambridge University Press, Cambridge, 1999.

[8] W. Szpankowski and V. Rego. Yet another application of a binomial recurrence. Order statistics. Computing, 43(4):401–410, 1990.

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa, email: helmut@gauss.cam.wits.ac.za,

homepage: http://www.wits.ac.za/helmut/index.htm.