COMBINATORICS OF GEOMETRICALLY DISTRIBUTED RANDOM VARIABLES: INVERSIONS AND A PARAMETER OF KNUTH

HELMUT PRODINGER

Abstract. For words of length n, generated by independent geometric random variables, we consider the mean and variance of the number of inversions and of a parameter of Knuth from permutation in situ. In this way, q–analogues for these parameters from the usual permutation model are obtained.

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 random variables X_{1}, …, X_{n} has attracted recent interest, especially because of applications in computer science. We mention just two areas, the skip list [3, 18, 21, 12, 19, 9] and probabilistic counting [4, 10, 11, 13].

In [20] the number of left-to-right maxima was investigated for words x_{1} … x_{n}, where the letters x_{i} are independently generated according to the geometric distribution. In [14] the study of left-to-right maxima was continued, but now the parameters studied were the mean value and mean position of the r-th maximum.

In [5] runs of consecutive equal letters in a string of n geometrically distributed independent random letters were studied.

In the present paper we deal with the number of inversions. This parameter is well understood in the context of permutations, see e. g. [17]. An inversion in a word x_{1} … x_{n} is a pair 1 ≤ i < j ≤ n such that x_{i} > x_{j}. In section 2 we compute average and variance of this parameter. Interestingly, if we perform the limit q → 1 in these answers, we get exactly the same formulæ as in the model of permutations.

Another parameter related to pairs of indices in a permutation is the parameter a that was studied by Knuth in the context of an algorithm to permute a file in situ [16], compare also [8, 22]. This parameter is defined as

a = |{(i, j) | 1 ≤ i < j ≤ n, x_{i} = min{x_{i}, x_{i+1}, …, x_{j}}}|.

In this more complicated example, surprisingly, the limiting case q → 1 again gives exactly the formulæ from the model of permutations (see Section 3).

Date: March 17, 1999.

1991 Mathematics Subject Classification. 05A15.

Key words and phrases. Geometric distribution, inversions, permutations, harmonic numbers, q– analogues.

Thus the examples treated in this paper can be interpreted as q–analogues of the two parameters.

2. The number of inversions

The probability that a random word of length n, produced by indepent geometric random variables, has k inversions, is given as the coefficient of v^{k} in

f(v) = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∏_{1≤j<k≤n} ([[i_{j} ≤ i_{k}]] + [[i_{j} > i_{k}]]v).

Here, [[P]] is a characteristic function, being 1 when condition P is satisfied and 0 otherwise. This is the notation of Iverson, being popularized by [6]. The form of this generating function is merely a reformulation of the definition of the number of inversions.

The expected value is obtained as 𝔼 = f′(1), which is

𝔼 = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∑_{1≤j<k≤n}[[i_{j} > i_{k}]]

= \binom{n}{2}(\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}}[[i_{1} > i_{2}]]

= \binom{n}{2}(\frac{p}{q})^{2} ∑_{i_{1},i_{2}≥1} q^{i_{1}+i_{2}}[[i_{1} > i_{2}]]

= \binom{n}{2}(\frac{p}{q})^{2} ∑_{i_{1}>i_{2}≥1} q^{i_{1}+i_{2}}

= \binom{n}{2}\frac{p}{q} ∑_{i_{2}≥1} q^{2i_{2}}

= \binom{n}{2}\frac{q}{1 + q} .

Now we are going to compute the second factorial moment 𝔼\underline{2}, which is obtained by 𝔼\underline{2} = f′′(1), since the variance 𝕍 is given by 𝔼\underline{2} + 𝔼 − 𝔼^{2};

𝔼\underline{2} = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∑_{1≤j<k≤n,1≤l<m≤n,(j,k)≠(l,m)}[[i_{j} > i_{k}]][[i_{l} > i_{m}]].

There are several possibilities for (j, k) ≠ (l, m) to hold, yielding several contribution to 𝔼\underline{2} = 𝔼\underline{2} 1 + 𝔼\underline{2} 2 + 𝔼\underline{2} 3 + 𝔼\underline{2} 4.

First, all 4 indices might be mutually different;

𝔼\underline{2} 1 = \binom{n}{2}\binom{n − 2}{2}(\frac{p}{q})^{4} ∑_{i_{1},...,i_{4}≥1} q^{i_{1}+···+i_{4}}[[i_{1} > i_{2}]][[i_{3} > i_{4}]]

= \binom{n}{2}\binom{n − 2}{2}(\frac{p}{q})^{4} ∑_{i_{1}>i_{2}≥1,i_{3}>i_{4}≥1} q^{i_{1}+···+i_{4}}

= \binom{n}{2}\binom{n − 2}{2}\frac{q^{2}}{(1 + q)^{2}} .

The second contribution stems from j = l, k ≠ m:

𝔼\underline{2} 2 = 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1},i_{2},i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}[[i_{1} > i_{2}]][[i_{1} > i_{3}]]

= 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1}>i_{2}≥1,i_{1}>i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}

= 2\binom{n}{3}\frac{q(1 + q^{2})}{(1 + q)(1 + q + q^{2})}.

The third contribution originates from j ≠ l, k = m:

𝔼\underline{2} 3 = 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1},i_{2},i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}[[i_{1} > i_{3}]][[i_{2} > i_{3}]]

= 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1}>i_{3}≥1,i_{2}>i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}

= 2\binom{n}{3}\frac{q^{2}}{1 + q + q^{2}} .

Finally, the two cases j < k = l < m and l < m = j < k can be combined by symmetry;

𝔼\underline{2} 4 = 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1},i_{2},i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}[[i_{1} > i_{2}]][[i_{2} > i_{3}]]

= 2\binom{n}{3}(\frac{p}{q})^{3} ∑_{i_{1}>i_{2}>i_{3}≥1} q^{i_{1}+i_{2}+i_{3}}

= 2\binom{n}{3}\frac{q^{3}}{(1 + q)(1 + q + q^{2})}.

Altogether we find

𝔼\underline{2} = \frac{n(n − 1)(n − 2)}{12}(3nq(1 + q + q^{2}) + 3q^{3} + 7q^{2} − q + 4)\frac{q}{(1 + q)^{2}(1 + q + q^{2})}.

The variance is thus

𝕍 = \frac{n(n − 1)}{6} \frac{q}{(1 + q)^{2}(1 + q + q^{2})}(2(1 − q + q^{2})n − q^{2} + 7q − 1).

Summarizing, we obtain the following theorem.

Theorem 1. The average and the variance of the number of inversions in a random word of length n obtained by independent geometric random variables with probabilities ℙ{X = k} = pq^{k−1}, are given by

𝔼 = \frac{n(n − 1)}{2} \frac{q}{1 + q} ,
𝕍 = \frac{n(n − 1)}{6} \frac{q}{(1 + q)^{2}(1 + q + q^{2})}(2(1 − q + q^{2})n − q^{2} + 7q − 1).

For fixed q and n → ∞, we find

𝔼 ∼ \frac{n^{2}}{2} \frac{q}{1 + q} ,
𝕍 ∼ \frac{n^{3}}{3} \frac{q(1 − q + q^{2})}{(1 + q)^{2}(1 + q + q^{2})}.

On the other hand, for q = 1, our formulæ turn into

𝔼 = \frac{n(n − 1)}{4},
𝕍 = \frac{n(n − 1)(2n + 5)}{72},

and these are exactly the formulæ for the instance of permutions, compare e. g. [17].

3. Knuth’s parameter from permutation in situ

This time, the generating function of interest is

f(v) = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∏_{1≤j<k≤n} ([[i_{j} = min\{i_{j}, …, i_{k}\}]]v + [[i_{j} ≠ min\{i_{j}, …, i_{k}\}]]).

Again, this is not really a useful generating function, but merely a direct translation of the definition. Nevertheless we find it appropriate in order to control the rather unwieldy expression.

As always, the expected value is again obtained via 𝔼 = f′(1);

𝔼 = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∑_{1≤j<k≤n}[[i_{j} = min\{i_{j}, …, i_{k}\}]]

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j} ∑_{i_{j}=min\{i_{j},...,i_{k}\}} q^{i_{j}+···+q_{k}}

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j} ∑_{i≥1} q^{i(k+1−j)} \frac{1}{p^{k−j}}

= p ∑_{1≤j<k≤n} (\frac{1}{q})^{k+1−j} ∑_{i≥1} q^{i(k+1−j)}

= p ∑_{1≤j<k≤n} \frac{1}{1 − q^{k+1−j}}

= p ∑_{2≤h≤n}(n + 1 − h)\frac{1}{1 − q^{h}} .

And the second factorial moment is again obtained by a second derivative;

𝔼\underline{2} = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ×

× ∑_{1≤j<k≤n,1≤l<m≤n,(j,k)≠(l,m)}[[i_{j} = min{i_{j}, …, i_{k}}]][[i_{l} = min{i_{l}, …, i_{m}}]].

Now there are even more cases to be considered. We might have disjoint intervals, overlapping intervals or one interval being included in the other. Or, two indices might coincide, resulting in two intervals glued together or again one interval being included in the other with either a common left or right endpoint.

Assume first that 1 ≤ j < k < l < m ≤ n. The corresponding contribution turns out to be

p^{2} ∑_{1≤j<k<l<m≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} .

Observe that in general

∑_{1≤j<k<l<m≤n} a_{k+1−j}a_{m+1−l} = ∑_{2≤i,j≤n−2; i+j≤n} a_{i}a_{j}\binom{n + 2 − i − j}{2}.

The next range is given by 1 ≤ j < l < m < k ≤ n, with a contribution

p^{2} ∑_{1≤j<l<m<k≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} .

We have the general formula

∑_{1≤j<l<m<k≤n} a_{k+1−j}a_{m+1−l} = ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)(j − i − 1).

For the range 1 ≤ j < l < k < m ≤ n we obtain the contribution

p^{2} ∑_{1≤j<l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} (m − l − 1).

Observe again that in general

∑_{1≤j<l<m≤n} a_{m+1−j}a_{m+1−l}(m − l − 1) = ∑_{3≤i<j≤n} a_{i}a_{j}(n + 1 − j)(i − 2).

Now the first range with 3 indices involved is 1 ≤ j < k = l < m ≤ n with a contribution

p^{2} ∑_{1≤j<k<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−k}} .

Again, such a sum can be rearranged in general;

∑_{1≤j<k<m≤n} a_{m+1−j}a_{m+1−k} = ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j).

The next range 1 ≤ j < l < m = k ≤ n gives a contribution

p^{2} ∑_{2≤j<l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} .

Here we note also a general formula;

∑_{1≤j<l<m≤n} a_{m+1−j}a_{m+1−l} = ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j).

The last range 1 ≤ j = l < k < m ≤ n gives a contribution

p ∑_{1≤j<k<m≤n} \frac{1}{1 − q^{m+1−j}} = p ∑_{1≤j<m≤n} \frac{m − j − 1}{1 − q^{m+1−j}} .

Observe that in general

∑_{1≤j<m≤n}(m − j − 1)a_{m+1−j} = ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i).

All these contributions come with a factor 2, because of symmetry. Thus

\frac{1}{2}𝔼^{(2)} = p^{2} ∑_{2≤i,j≤n−2; i+j≤n} \frac{1}{1 − q^{i}} \frac{1}{1 − q^{j}} \binom{n + 2 − i − j}{2}

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

+ p^{2} ∑_{3≤i<j≤n} \frac{1}{1 − q^{i}} \frac{1}{1 − q^{j}} (n + 1 − j)(i − 2)

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

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

+ p ∑_{3≤i≤n} \frac{1}{1 − q^{i}} (n + 1 − i)(i − 2).

After several tedious simplifications we arrive at this form;

𝔼^{(2)} = 2p^{2} ∑_{1≤i<m≤n} \frac{1}{1 − q^{i}} \frac{1}{1 − q^{m−i}} \binom{n + 2 − m}{2} − 2p ∑_{1≤j≤n} \frac{(n + 1 − j)^{2}}{1 − q^{j}}

+ 2p^{2} ∑_{1≤i<j≤n} \frac{1}{1 − q^{i}} \frac{1}{1 − q^{j}} (n + 1 − j)(j − 1) + n(n + 1).

However, we can still do better than that by noting that

∑_{1≤i<m} \frac{1}{(1 − q^{i})(1 − q^{m−i})} = ∑_{1≤i<m} (\frac{q^{i}}{1 − q^{i}} + \frac{1}{1 − q^{m−i}} ) \frac{1}{1 − q^{m}}

= −\frac{m − 1}{1 − q^{m}} + \frac{2}{1 − q^{m}} ∑_{1≤i<m} \frac{1}{1 − q^{i}} .

Thus

𝔼^{(2)} = −2p^{2} ∑_{1≤m≤n} \frac{m − 1}{1 − q^{m}} \binom{n + 2 − m}{2} − 2p ∑_{1≤j≤n} \frac{(n + 1 − j)^{2}}{1 − q^{j}}

+ 2p^{2}(n + 1) ∑_{1≤i<j≤n} \frac{n + 1 − j}{(1 − q^{i})(1 − q^{j})} + n(n + 1).

Theorem 2. The average and the variance of Knuth’s parameter from the permutation in situ problem for random words of length n obtained by independent geometric random variables with probabilities ℙ{X = k} = pq^{k−1}, are given by

𝔼 = p ∑_{1≤i≤n} \frac{n + 1 − i}{1 − q^{i}} − n,

𝕍 = −2p^{2} ∑_{1≤m≤n} \frac{m − 1}{1 − q^{m}} \binom{n + 2 − m}{2} + 2p^{2} ∑_{1≤i<j≤n} \frac{i(n + 1 − j)}{(1 − q^{i})(1 − q^{j})}

− p^{2} ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{(1 − q^{i})^{2}} + p ∑_{1≤i≤n} \frac{(n + 1 − i)(2i − 1)}{1 − q^{i}}.

As a corollary, let us evaluate these quantities for fixed q and n → ∞.

For this purpose, we need two infinite series:

α := ∑_{i≥1} \frac{1}{q^{−i} − 1}, β := ∑_{i≥1} \frac{1}{(q^{−i} − 1)^{2}} .

Then

𝔼 = p\binom{n + 1}{2} + pn ∑_{i≥1} \frac{1}{q^{−i} − 1} − n + O(1)

= \frac{p}{2}n^{2} + (\frac{p}{2} − 1 + pα)n + O(1).

For the variance, the computations are a bit more complicated. We treat the sums separately:

∑_{1≤m≤n} \frac{m − 1}{1 − q^{m}} \binom{n + 2 − m}{2} = \frac{n^{4}}{24} + \frac{n^{3}}{12} − \frac{n^{2}}{24} + \frac{n^{2}}{2} ∑_{m≥1} \frac{m − 1}{q^{−m} − 1} + O(n)

= \frac{n^{4}}{24} + \frac{n^{3}}{12} − \frac{n^{2}}{24} + \frac{n^{2}}{2} β + O(n);

∑_{1≤i<j≤n} \frac{i(n + 1 − j)}{(1 − q^{i})(1 − q^{j})} = \frac{n^{4}}{24} + \frac{n^{3}}{12} − \frac{n^{2}}{24} + \frac{n^{2}}{2} (α + β) + O(n);

∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{(1 − q^{i})^{2}} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + 2 ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{q^{−i} − 1} + ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{(q^{−i} − 1)^{2}} + O(n)

= \frac{n^{3}}{3} + \frac{n^{2}}{2} + 2n^{2}α + n^{2}β + O(n);

∑_{1≤i≤n} \frac{(n + 1 − i)(2i − 1)}{1 − q^{i}} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + O(n).

Collecting we find

𝕍 = \frac{pq}{3} n^{3} + (\frac{pq}{2} − p^{2}(α + β))n^{2} + O(n).

Now we consider the limit q → 1.

For the expectation we easily get

𝔼 = (n + 1)H_{n} − 2n.

For the variance we get

𝕍 = 2 ∑_{1≤i<j≤n} \frac{n + 1 − j}{j} − ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{i^{2}} + ∑_{1≤i≤n} \frac{(n + 1 − i)(2i − 1)}{i}

= ∑_{1≤j≤n} \frac{(n + 1 − j)(4j − 3)}{j} − ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{i^{2}}

= −(n + 1)H_{n} − (n + 1)^{2}H_{n}^{(2)} + 2n(n + 2).

Here we only used standard summations involving harmonic numbers, as treated e. g. in [15, 7]. (Recall that the harmonic numbers of first and second order are defined by

H_{n} = ∑_{1≤k≤n} \frac{1}{k}, H_{n}^{(2)} = ∑_{1≤k≤n} \frac{1}{k^{2}} ,

respectively.)

Thus, in the limiting case, expectation and variance are exactly the same as in the permutation model, compare [16, 22, 8].

Some other q–analogues of harmonic numbers can be found e. g. in [2, 1].

References

[1] G. Andrews, D. Crippa, and K. Simon. q–series arising from the study of random graphs. SIAM Journal on Discrete Mathematics, 10:41–56, 1997.

[2] G. Andrews and K. Uchimura. Identities in combinatorics. IV: Differentiation and harmonic numbers. Utilitas Mathematica, 28:265–269, 1985.

[3] L. Devroye. A limit theory for random skip lists. Advances in Applied Probability, 2:597–609, 1992.

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

[5] P. Grabner, A. Knopfmacher, and H. Prodinger. Combinatorics of geometrically distributed random variables: Run statistics. In preparation, 1999.

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

[7] D. H. Greene and D. E. Knuth. Mathematics for the analysis of algorithms. Birkhauser, Boston, second edition, 1982.

[8] P. Kirschenhofer, H. Prodinger, and R. F. Tichy. A contribution to the analysis of in situ permutation. Glasnik Mathematicki, 22(42):269–278, 1987.

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

[10] P. Kirschenhofer and H. Prodinger. On the analysis of probabilistic counting. In E. Hlawka and R. F. Tichy, editors, Number–theoretic Analysis, volume 1452 of Lecture Notes in Mathematics, pages 117–120, 1990.

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

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

[13] P. Kirschenhofer, H. Prodinger, and W. Szpankowski. Analysis of a splitting process arising in probabilistic counting and other related algorithms. Random Structures and Algorithms, 9:379– 401, 1996.

[14] A. Knopfmacher and H. Prodinger. Combinatorics of geometrically distributed random variables: Value and position of the rth left-to-right maximum. Submitted.

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

[16] D. E. Knuth. Mathematical analysis of algorithms. In Information Processing 71, pages 19–27. North Holland Publishing Company, 1972. Proceedings of IFIP Congress, Ljubljana, 1971.

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

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

[19] 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.

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

[21] W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33:668–676, 1990.

[22] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

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.