COMBINATORIAL PROBLEMS RELATED TO

GEOMETRICALLY DISTRIBUTED RANDOM VARIABLES

Helmut Prodinger

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

1. Introduction

Motivated from Computer Science problems we consider the following situation (compare [2] and [3]). In these papers the reader will find a more complete description as well as additional references.

Let X denote a geometrically distributed random variable, i.e. ℙ{X = k} = pq^{k−1} for k ∈ ℕ and q = 1 − p. Assume that we have n independent random variables X_{1}, …, X_{n} according to this distribution.

The first parameter of interest is the number of left-to-right maxima, where we say that X_{i} is a left-to-right maximum (in the strict sense) if it is strictly larger than the elements to left. A left-to-right maximum in the loose sense is defined analogously but “larger” is replaced by “larger or equal”.

The second parameter of interest is the (horizontal) path length, i.e. the sum of the left-to-right maxima in the loose sense of all the sequences X_{i}, …, X_{n}, where i is running from 1 to n.

Example. Consider the sequence 4, 5, 2, 3, 5. It has 2 left-to-right maxima in the strict sense (4–5) and 3 left-to-right maxima in the loose sense (4–5–5). For the path length we must consider the subsequences

4, 5, 2, 3, 5 5, 2, 3, 5 2, 3, 5 3, 5 5

with respectively 3, 2, 3, 2, 1 left-to-right maxima. Therefore the path length is 3 + 2 + 3 + 2 + 1 = 11.

2. Left-to-right maxima in the strict sense

We can find a probability generating function by considering an appropriate “language”.

Typeset by AMS-TEX

The “letters” will be denoted 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}^{∗}.

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} + ε) …

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})})

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 are led to

f(z) = \frac{pz}{1 − z} ∑_{k≥0} \frac{q^{k}}{1 − z(1 − q^{k})},

which is also, by partial fraction decomposition,

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

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}] = p ∑_{k=1}^{n} \binom{n}{k}(−1)^{k−1} \frac{1}{1 − q^{k}}

The asymptotic evaluation of such an alternating sum is conveniently performed by Rice’s method, which we cite as a lemma.

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,

where

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

Extending the contour of integration it turns out that under suitable growth conditions on f(z) 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.

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.

Theorem 1. 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})

where Q = q^{−1}, L = log Q, γ is Euler’s constant and δ is a periodic function of period 1, mean zero and small amplitude. Its Fourier series is given by

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

The variance can also be computed, by considering the second derivative of F (z, y) with respect to y.

Theorem 2. 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})+δ_{1}(log_{Q} n)+O(\frac{1}{n}).

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

3. Left-to-right maxima in the loose sense

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)}.

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})}]

and

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

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}).

Theorem 4. 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})+δ_{2}(log_{Q} n)+O(\frac{1}{n}).

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

4. Path length

If we denote the path length of a “word” ω by a(ω), then we have the following recursion formula

a(ω) = a(ρmσ) = a(ρ) + a(σ) + 1 + |ρ|

with ρ ∈ {1, …, m}^{∗} and σ ∈ {1, …, m − 1}^{∗}. From this we get a functional equation for the generating functions. (The upper index ‘= m’ e.g. refers to all sequences where the maximal element is m.)

P^{=m}(z, y) = pq^{m−1}zyP^{≤m}(zy, y)P^{<m}(z, y)

It is not likely that this formidable equation can be solved explicitly. However it contains enough information to obtain the generating functions for the expectations (and the variance, too). For the expectation we have to differentiate with respect to y and then set y = 1. Denoting the corresponding functions by F^{∗}(z), we get

\frac{F^{=m}(z)}{pq^{m−1}z} = P^{≤m}(z, 1)P^{<m}(z, 1)

+ [z \frac{∂}{∂z} P^{≤m}(z, 1) + F^{≤m}(z)] P^{<m}(z, 1) + P^{≤m}(z, 1)F^{<m}(z).

Since P^{≤m}(z, 1) = \frac{1}{1 − z(1 − q^{m})} =: \frac{1}{[[m]]} and \frac{∂}{∂z} P^{≤m}(z, 1) = \frac{1 − q^{m}}{[[m]]^{2}} ,

we obtain

F^{≤m}(z)[[m]]^{2} = F^{<m}(z)[[m − 1]]^{2} + \frac{pq^{m−1}z}{[[m]]} ,

which we can solve by iteration:

F^{≤m}(z) = \frac{p}{q} \frac{z}{[[m]]^{2}} ∑_{i=1}^{m} \frac{q^{i}}{[[i]]}

The limit for m → ∞ is the generating function for the expectations:

F (z) = \frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]}

From this it is easy to get the coefficients E_{n}

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

Theorem 5. The expected path length E_{n} in the context of n independently distributed geometric random variables has the asymptotic expansion

E_{n} = (Q − 1)n( log_{Q} n + \frac{γ − 1}{L} − \frac{1}{2} + \frac{1}{L}δ_{3}(log_{Q} n)) + O(log n)

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

To deal with the variance, we have to differentiate the functional equation twice. Denoting the resulting generating function by H(z), we finally find

H(z) = 2\frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]^{2}}

− 2\frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]}

− 2(\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]}

+ 4(\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]]^{2}[[j]]}

+ 2(\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]^{2}}

+ 2(\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j<i} \frac{q^{i+j}}{[[i]][[i − 1]][[j]]}

+ 2(\frac{p}{q})^{3} \frac{z^{3}}{(1 − z)^{2}} ∑_{i≥1} ∑_{1≤j≤i} ∑_{1≤h<i} \frac{q^{i+j+h}}{[[i]][[i − 1]][[j]][[h]]}

To get the coefficient of z^{n} in an efficient way we use to following principle (used recently by Flajolet and Richmond).

A(z) = ∑_{n≥0} a_{n}z^{n} ⟷ \frac{1}{1 − w} A(\frac{w}{1 − w} ) = ∑_{n≥0} ( ∑_{k=0}^{n} \binom{n}{k}a_{k})w^{n}

Of course this relation can be inverted to read

A(z) = ∑_{n≥0} ( ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}f(k))z^{n} ⟷ \frac{1}{1 − w} A(\frac{w}{w − 1}) = ∑_{n≥0} f(n)w^{n}.

That means that if we find the coefficients in the “w–world” we automatically have the coefficients in the “z–world” as alternating sums!

This is especially convenient, since the expressions become nicer if we substitute

z = \frac{w}{w − 1}, because \frac{1}{[[i]]} = \frac{1 − w}{1 − wq^{i}}.

Consider as an example the first one, namely A(z) = \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]^{2}} .

We easily find that

\frac{1}{1 − w} A(\frac{w}{w − 1}) = −(1 − w)^{2} ∑_{i≥1} \frac{wq^{i}}{(1 − wq^{i})^{2}} .

Let us forget the extra factor −(1 − w)^{2} for a moment. We find for n ≥ 1

[w^{n}] ∑_{i≥1} \frac{wq^{i}}{(1 − wq^{i})^{2}} = ∑_{i≥1} q^{in} · [w^{n}]\frac{w}{(1 − w)^{2}} = \frac{n}{Q^{n} − 1}.

But because (1 − w)^{2} = \frac{w^{2}}{z^{2}} , the extra factor just works as a shift on both sides, so that we find Sum 1.

[z^{n}]\frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]^{2}} = − ∑_{k=3}^{n+2} \binom{n + 2}{k}(−1)^{k} \frac{k − 2}{Q^{k−2} − 1}

In this way we find for the coefficients of z^{n} in the other sums in H(z) the following expressions as alternating sums. Sum 2.

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

Sum 3.

[z^{n}]\frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]} = − ∑_{k=3}^{n+1} \binom{n + 1}{k}(−1)^{k} \frac{1}{Q^{k−1} − 1} [k − 2 + ∑_{m=1}^{k−2} \frac{1}{Q^{m} − 1}]

Sum 4.

[z^{n}]\frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]]^{2}[[j]]} = ∑_{k=4}^{n+2} \binom{n + 2}{k}(−1)^{k} \frac{1}{Q^{k−2} − 1} [\binom{k − 2}{2} + ∑_{m=1}^{k−3} \frac{m}{Q^{m} − 1}]

Sum 5.

[z^{n}]\frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]^{2}}

= ∑_{k=4}^{n+2} \binom{n + 2}{k}(−1)^{k} \frac{1}{Q^{k−2} − 1} [\binom{k − 2}{2} + (k − 2) ∑_{m=1}^{k−3} \frac{1}{Q^{m} − 1} − ∑_{m=1}^{k−3} \frac{m}{Q^{m} − 1}]

Sum 6.

[z^{n}]\frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j<i} \frac{q^{i+j}}{[[i]][[i − 1]][[j]]} = ∑_{k=4}^{n+2} \binom{n + 2}{k}(−1)^{k} \frac{k − 3}{(Q − 1) (Q^{k−2} − 1)}

Sum 7.

[z^{n}]\frac{z^{3}}{(1 − z)^{2}} ∑_{\begin{matrix}i≥1 \\ 1≤j≤i \\ 1≤h<i \end{matrix}} \frac{q^{i+j+h}}{[[i]][[i − 1]][[j]][[h]]}

= − ∑_{k=5}^{n+2} \binom{n + 2}{k}(−1)^{k} \frac{1}{(Q − 1) (Q^{k−2} − 1)} [\binom{k − 3}{2} + \frac{k − 4}{Q − 1} + ∑_{m=2}^{k−3} \frac{m − 2}{Q^{m} − 1}]

This gives finally the following result: Theorem 6. The variance V_{n} of the path length in the context of n independently distributed geometric random variables has the asymptotic expansion

\begin{aligned}V_{n} & = (Q − 1)^{2}n^{2}\{\frac{Q + 1}{2(Q − 1)L} + \frac{1}{L^{2}} − \frac{π^{2}}{6L^{2}} + \frac{8π^{2}}{L^{2}} h(\frac{4π^{2}}{L} ) − α_{1} + δ_{4}(log_{Q} n)\} \\ & + O(n^{1+ε}), ε > 0, \end{aligned}

where h(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} , α_{1} = L ∑_{k≥1} \frac{1}{k(L^{2} + 4k^{2}π^{2}) sinh(2kπ^{2}/L)} and δ_{4}(x) is

again continuous, periodic of period 1 and mean zero.

Both, h(·) and α_{1} are very small quantities, so that a less accurate but more readible formula is

V_{n} ∼ (Q − 1)^{2}n^{2}\{\frac{Q + 1}{2(Q − 1)L} + \frac{1}{L^{2}} − \frac{π^{2}}{6L^{2}} \}.

5. A combinatorial interpretation of Euler’s partition identities The identities in question are (compare [1])

∏_{n≥0} (1 + tq^{n}) = ∑_{n≥0} \frac{t^{n}q^{\binom{n}{2}}}{Q_{n}(q)}

and

∏_{n≥0} \frac{1}{1 − tq^{n}} = ∑_{n≥0} \frac{t^{n}}{Q_{n}(q)},

where

Q_{n}(q) = (1 − q^{1})(1 − q^{2}) … (1 − q^{n}).

Now consider

ℙ{X_{1} < ⋯ < X_{n}}

and its generating function

M_{<}(z) = ∑_{n≥0} ℙ{X_{1} < ⋯ < X_{n}}z^{n}

resp. the analogous quantities

ℙ{X_{1} ≤ ⋯ ≤ X_{n}}

and

M_{≤}(z) = ∑_{n≥0} ℙ{X_{1} < ⋯ < X_{n}}z^{n}.

Then we can set up appropriate languages

M_{<} = (ε + 1)(ε + 2) …

and

M_{≤} = 1^{∗} · 2^{∗} …,

so that

M_{<}(z) = ∏_{k≥1} (1 + pq^{k−1}z)

resp.

M_{≤}(z) = ∏_{k≥1} \frac{1}{1 − pq^{k−1}z} .

Using the identities we can further write

M_{<}(z) = ∏_{k≥0} (1 + pq^{k}z) = ∑_{n≥0} \frac{p^{n}z^{n}q^{\binom{n}{2}}}{Q_{n}(q)}

and

M_{≤}(z) = ∏_{k≥0} \frac{1}{1 − pq^{k}z} = ∑_{n≥0} \frac{p^{n}z^{n}}{Q_{n}(q)},

so that we have the explicit formulæ

ℙ\{X_{1} < ⋯ < X_{n}\} = \frac{p^{n}q^{\binom{n}{2}}}{Q_{n}(q)}

and

ℙ\{X_{1} ≤ ⋯ ≤ X_{n}\} = \frac{p^{n}}{Q_{n}(q)}.

References

1. G. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976.

2. P. Kirschenhofer and H. Prodinger, The path length of random skip lists, Acta Informatica 31 (1994), 775–792.

3. H. Prodinger, Combinatorics of geometrically distributed random variables: Left-to-right maxima, 5th conference on Formal Power Series and Algebraic Combinatorics, Firenze (Discrete Mathematics, to appear) (1993).

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

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