COMBINATORICS OF GEOMETRICALLY DISTRIBUTED RANDOM VARIABLES: LENGTH OF ASCENDING RUNS

HELMUT PRODINGER

Abstract. For n independently distributed geometric random variables we consider the average length of the m–th run, for fixed m and n → ∞. One particular result is that this parameter approaches 1 + q.

In the limiting case q → 1 we thus rederive known results about runs in permutations.

1. Introduction

Knuth in [6] has considered the average length L_{k} of the kth ascending run in random permutations of n elements (for simplicity, mostly the instance n → ∞ was discussed).

This parameter has important impact on the behaviour of several sorting algorithms.

Let X denote a geometrically distributed random variable, i. e. ℙ{X = k} = pq^{k−1} for k ∈ ℕ 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 → 1 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, ⋯, and they appear with probabilities p, pq, pq^{2}, · · ·. If we decompose a word into ascending runs

a_{1} < ⋯ < a_{r} ≥ b_{1} < ⋯ < b_{s} ≥ c_{1} < ⋯ < c_{t} ≥ ⋯,

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.

2. 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

[z^{n}] ∏_{i≥1}(1 + pq^{i−1}z) for n ≥ 1.

Date: August 23, 1999.

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ée” cooperation.

But the product involved here is well known in the theory of partitions; the usual notation is

(a)_{n} = (a; q)_{n} = (1 − a)(1 − aq)(1 − aq^{2}) ⋯ (1 − aq^{n−1}) and
(a)_{∞} = (a; q)_{∞} = (1 − a)(1 − aq)(1 − aq^{2}) · · · .

Therefore

∏_{i≥1}(1 + pq^{i−1}z) = (−pz)_{∞} = ∑_{n≥0} \frac{p^{n}q^{\binom{n}{2}}z^{n}}{(q)_{n}} ,

the last equality being the celebrated identity of Euler [2]. This was already noted in [7]. If we set

Λ_{m}(z) = ∑_{n≥0}[Probability that a word of length n has (exactly) m ascending runs]z^{n},

then Λ_{0}(z) = 1 and Λ_{1}(z) = (−pz)_{∞} − 1.

Now for general m we should consider (−pz)_{∞}^{m}. Indeed, words with exactly m ascending runs have a unique representation in this product. However, this product contains also words with 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 Λ_{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Λ_{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 \frac{1}{2}D(z^{2}Λ_{m−2}(z)), and so on.

Therefore we have the following recurrence:

Λ_{m}(z) = P^{m} − ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−k}(z)),  Λ_{0}(z) = 1;  (2.1)

here are the first few values. We use the abbreviations P = (−pz)_{∞} and P_{k} = z^{k}D^{k}P.

Λ_{0} = 1,
Λ_{1} = P − 1
Λ_{2} = (P − 1)P − P_{1},
Λ_{3} = (P − 1)P^{2} + P_{1} − 2P P_{1} + \frac{1}{2}P_{2},
Λ_{4} = (P − 1)P^{3} + 2P P_{1} − \frac{1}{2}P_{2} − 3P^{2}P_{1} + P_{1}^{2} + P P_{2} − \frac{1}{6}P_{3}.

In the limiting case q → 1 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.

Theorem 1. The sequence Λ_{m}(z) is defined as follows,

Λ_{m}(z) := e^{mz} − ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−k}(z)), Λ_{0}(z) := 1.

Then we have for m ≥ 1

Λ_{m}(z) = ∑_{j=0}^{m} e^{jz} \frac{z^{m−j−1}(−1)^{m−j}j^{m−j−1}(j(z − 1) + m)}{(m − j)!}.

Proof. First notice that if we write

λ_{m}(z) = ∑_{j=0}^{m} e^{jz} \frac{(−jz)^{m−j}}{(m − j)!} ,

for m ≥ 0, then Λ_{m}(z) = λ_{m}(z) − λ_{m−1}(z). And the equivalent formula is

∑_{k=0}^{m} \frac{1}{k!}D^{k}(z^{k}λ_{m−k}(z)) = ∑_{j=1}^{m} e^{jz},

which we will prove by induction, the basis being trivial (as usual). Now

∑_{k=0}^{m} \frac{1}{k!}D^{k}(z^{k}λ_{m−k}(z)) = ∑_{k=0}^{m} \frac{1}{k!}D^{k} ∑_{j=1}^{m−k} e^{jz}z^{m−j} \frac{(−j)^{m−k−j}}{(m − k − j)!}

= ∑_{k=0}^{m} \frac{1}{k!} ∑_{i=0}^{k} \binom{k}{i} ∑_{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)!},

and we have to prove that the coefficient of e^{jz} therein is 1. Writing M := m − j it is

∑_{k=0}^{M} \frac{1}{k!} ∑_{i=0}^{k} \binom{k}{i}j^{k−i}z^{M−i} \frac{M!}{(M − i)!} \frac{(−j)^{M−k}}{(M − k)!}

= ∑_{i=0}^{M} \frac{M!}{(M − i)!}(jz)^{M−i} ∑_{k=i}^{M} \frac{1}{k!}\binom{k}{i}\frac{(−1)^{M−k}}{(M − k)!}

= ∑_{i=0}^{M} \binom{M}{i}(jz)^{M−i} \frac{1}{(M − i)!} ∑_{k=i}^{M} \binom{M − i}{k − i}(−1)^{M−k}

= ∑_{i=0}^{M} \binom{M}{i}(jz)^{M−i} \frac{(−1)^{M−i}}{(M − i)!}δ_{M,i} = 1.

Thus

∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−k}(z)) = ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}λ_{m−k}(z)) − ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−1−k}(z))

= ∑_{j=1}^{m} e^{jz} − λ_{m}(z) − ∑_{j=1}^{m−1} e^{jz} + λ_{m−1}(z) = e^{mz} − Λ_{m}(z),

and the result follows.

Remark. Since every word has some number of ascending runs, we must have that

∑_{m≥0} Λ_{m}(z) = \frac{1}{1 − z} .

In the limiting case q → 1 we will give an independent proof. For the general case, see the next sections.

Consider

Λ_{0}(z) + Λ_{1}(z) + ⋯ + Λ_{m}(z) = λ_{m}(z);

for m = 6 we get e. g.

λ_{6}(z) = 1 + z + z^{2} + z^{3} + z^{4} + z^{5} + z^{6} + \frac{5039}{5040}z^{7} + \frac{5009}{5040}z^{8} + \frac{38641}{40320}z^{9} + O (z^{10}) .

Now this is no coincidence since we will prove that

[z^{n}]λ_{m}(z) = 1 for n ≤ m.

This amounts to prove that^{1}

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

Notice that

\left\{{h \atop n}\right\} = \frac{1}{n!} ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}k^{h}

are Stirling subset numbers, and they are zero for h < n. Therefore, upon expanding (m − k)^{n} by the binomial theorem, almost all the terms are annihilated, only (−k)^{n} survives. But then it is a Stirling number \left\{{n \atop n}\right\} = 1. It is not too hard to turn this proof involving “discrete convergence” into one with “ordinary convergence.”

1A 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.

3. The average length of the mth run

We consider the parameter “combined lengths” of the first m runs in infinite strings and its probability generating function.

Note carefully that now the probability space are infinite words, as opposed to the previous chapter where we had words of length n. This is not unlike the situation in the paper [4].

To say that this parameter is larger or equal to n is the same as to say that a word of length n (the first n letters of the infinite word) has ≤ m ascending runs. Therefore the sought probability generating function is

F_{m}(z) = \frac{z − 1}{z}(Λ_{0}(z) + ⋯ + Λ_{m}(z)) + \frac{1}{z}.

Now

F′_{m}(1) = Λ_{0}(1) + ⋯ + Λ_{m}(1) − 1 = Λ_{1}(1) + ⋯ + Λ_{m}(1)

is the expected value of the combined lengths of the first m runs. Thus Λ_{m}(1) is the expected value of the length of the mth run (m ≥ 1).

In the limiting case q → 1 we can say more since we know Λ_{m}(z) explicitly:

L_{m} = Λ_{m}(1) = m ∑_{j=0}^{m} \frac{(−1)^{m−j}j^{m−j−1}}{(m − j)!} e^{j},

and this is exactly the formula that appears in [6] for the instance of permutations.

There, we also learn that L_{m} → 2; in the general case, we will see in the next sections that L_{m} → 1 + q.

4. Solving the recursion

The effect of the operator \frac{1}{k!}D^{k}(z^{k}f) can also be described by the Hadamard product (see [3] for definitions) of f with the series

T_{k} = ∑_{n} \binom{n + k}{n}z^{n}.

The reformulation of the recursion is then

P^{m} = ∑_{k=0}^{m} T_{k} ⊙ Λ_{m−k}.

We want to invert this relation to get the Λ_{m}(z)’s from the powers of P. We get

Λ_{m}(z) = ∑_{k=0}^{m} U_{k} ⊙ P^{m−k},

where

U_{k} = [w^{k}] 1/ ∑_{j≥0} T_{j}w^{j}.

Lemma 1.

U_{k} = (−1)^{k} ∑_{n} \binom{n + 1}{k}z^{n}.

Proof. Since

U_{n} = − ∑_{k=0}^{n−1} U_{k}T_{n−k},

it is best to prove the formula by induction, the instance n = 0, i.e. U_{0} = 1/(1 − z) being obvious.

The righthandside multiplies the coefficient of z^{n} by

− ∑_{k=0}^{n−1}(−1)^{l}\binom{n + 1}{l}\binom{n + k − l}{n} = (−1)^{k+1} ∑_{l=0}^{k−1} \binom{n + 1}{l}\binom{−n − 1}{k − l} = (−1)^{k}\binom{n + 1}{k},

which finishes the proof.

Therefore we get the formula

Proposition 1.

[z^{n}]Λ_{m}(z) = [z^{n}] ∑_{k=0}^{m}(−1)^{k}\binom{n + 1}{k}P^{m−k};

for n < m this is zero by the combinatorial interpretation or directly.

Now this form definitely looks like an outcome of the inclusion–exclusion principle. Indeed, there are n + 1 gaps between the n letters, and one can pick k of them where the condition that a new run should start is violated. Since we don’t need that, we confine ourselves to this brief remark.

Let us prove that

∑_{m≥0} Λ_{m}(z) = \frac{1}{1 − z} :

[z^{n}] ∑_{m≥0} Λ_{m}(z) = [z^{n}] ∑_{0≤k≤m≤n}(−1)^{k}\binom{n + 1}{k}P^{m−k}

= [z^{n}] ∑_{k=1}^{n}(−1)^{n−k}\binom{n + 1}{k + 1} ∑_{i=0}^{k} P^{i}

= [z^{n}] ∑_{k=1}^{n}(−1)^{n−k}\binom{n + 1}{k + 1} ∑_{i=0}^{k} ∑_{j=0}^{i} \binom{i}{j}(P − 1)^{i}

= [z^{n}](P − 1)^{n} = 1.

(Note that P − 1 = z + . . ..)

Let us also rederive the formula for Λ_{m}(1) in the limiting case q → 1; since

[z^{n}]Λ_{m}(z) = ∑_{k=0}^{m}(−1)^{m−k}\binom{n + 1}{m − k}\frac{k^{n}}{n!}

we have

∑_{n≥0}[z^{n}]Λ_{m}(z) = ∑_{k=0}^{m} \frac{(−1)^{m−k}}{(m − k)!} ∑_{n≥0} (\frac{1}{(n − m + k)!} + \frac{m − k}{(n + 1 − m + k)!})k^{n}

= ∑_{k=0}^{m} \frac{(−1)^{m−k}}{(m − k)!}(k^{m−k} + (m − k)k^{m−k−1})e^{k}

= m ∑_{k=0}^{m} \frac{(−1)^{m−k}}{(m − k)!}k^{m−k−1}e^{k}.

5. A double generating function

From Proposition 1 we infer that

Λ_{m}(z) = ∑_{k=0}^{m} \frac{(−1)^{k}}{k!} D^{k}(zP^{m−k})

= ∑_{k=0}^{m} \frac{(−1)^{k}}{k!} (zD^{k}P^{m−k} + kD^{k−1}P^{m−k})

= z ∑_{k=0}^{m} \frac{(−1)^{k}}{k!} D^{k}P^{m−k} − ∑_{k=0}^{m−1} \frac{(−1)^{k}}{k!} D^{k}P^{m−1−k}.

Now these forms look like convolutions, and thus we introduce the double generating function

R(w, z) = ∑_{m≥0} Λ_{m}(z)w^{m}.

Upon summing we find

R(w, z) = ze^{−wD} \frac{1}{1 − wP} − we^{−wD} \frac{1}{1 − wP} = \frac{z − w}{1 − w( − p(z − w))_{∞}};

the last step was by noticing that e^{aD} is the shift operator E^{a} (see e. g. [1]).

It is tempting to plug in w = 1, because of the summation of the Λ_{m}(z)’s, but this is forbidden, because of divergence.

The instance (q → 1)

R(w, 1) = \frac{1 − w}{1 − we^{1−w}}

differs from Knuth’s

\frac{w(1 − w)}{e^{w−1} − w} + w

just by 1, because in [6] L_{0} = 0, whereas here it is L_{0} = 1. Theorem 2. The generating function of the numbers L_{m} is given by

\frac{1 − w}{1 − w ∏_{i≥0} (1 − (w − 1)pq^{i})}.

The dominant singularity is at w = 1, and the local expansion starts as

\frac{1 + q}{1 − w} + · · · .

From this, singularity analysis [5] entails that

L_{m} = 1 + q + O(ρ^{−m})

for some ρ > 1 that depends on q. Experiments indicate the expansion (m → ∞)

L_{m} = 1 + q − q^{m+1} + 2mq^{m+2} − (1 + 2m^{2})q^{m+3} − \frac{2m^{4}+10m^{2}−15m+9}{3}q^{m+4} + ⋯, so that it seems that one could take ρ = \frac{1}{q} − ϵ. However, that would require a proof.

6. Weakly ascending runs

Relaxing the conditions, we might now say that ⋯ > a_{1} ≤ ⋯ ≤ a_{r} > ⋯ is a run (of length r). Many of the previous considerations carry over, so we only give a few remarks. The recursion (2.1) stays the same, but with P = 1/(pz)_{∞}. With this choice of P the formula

[z^{n}]Λ_{m}(z) = [z^{n}] ∑_{k=0}^{m}(−1)^{k}\binom{n + 1}{k}P^{m−k}

still holds. The bivariate generating function is

\frac{z − w}{1 − w/(p(z − w))_{∞}} .

The poles of interest are the solutions of

∏_{i≥0} (1 + (w − 1)pq^{i}) = w;

the dominant one is w = 1 with a local expansion

(1 + \frac{1}{q})\frac{1}{1 − w} + ⋯,

from which we can conclude that L_{m} → 1 + \frac{1}{q}.

And the experiments indicate that

L_{m} = 1 + \frac{1}{q} − (−1)^{m}q^{2m−1}(1 − 2(m − 1)q + (2m^{2} − 5m + 4)q^{2} + ⋯).

References

[1] M. Aigner. Combinatorial Theory. Springer, 1997. Reprint of the 1979 edition.

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

[3] L. Comtet. Advanced Combinatorics. Reidel, Dordrecht, 1974.

[4] P. Flajolet, D. Gardy, and L. Thimonier. Birthday paradox, coupon collectors, caching algorithms, and self–organizing search. Discrete Applied Mathematics, 39:207–229, 1992.

[5] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3:216–240, 1990.

[6] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. Second edition, 1998.

[7] H. Prodinger. Combinatorial problems of geometrically distributed random variables and applications in computer science. In V. Strehl and R. König, editors, Publications de l’IRMA (Straßbourg), volume 30, pages 87–95, 1993.

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,
homepage: http://www.wits.ac.za/helmut/index.htm.