A RESULT IN ORDER STATISTICS

RELATED TO

PROBABILISTIC COUNTING

Peter Kirschenhofer and Helmut Prodinger

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

Abstract. Considering geometrically distributed random variables the d-maximum of these events is investigated, i.e. the d-th largest element (with repetitions allowed). The quantitative behaviour of expectation and variance is analyzed thoroughly. In particular the asymptotics of the variance for d getting large is established by means of nontrivial techniques from combinatorial analysis and complex variable theory. These results apply to probabilistic counting algorithms, where the cardinalities of large sets are estimated.

Zusammenfassung. Bezüglich geometrisch verteilter zufälliger Veränderlicher wird das d-Maximum solcher Ereignisse studiert, also das d-größte Element, wobei Wiederholungen erlaubt sind. Das quantitative Verhalten von Erwartungswert und Varianz wird ausgiebig analysiert. Insbesondere wird das Verhalten der Varianz für große d mit Hilfe nichttrivialer Techniken aus Kombinatorik und komplexer Analysis untersucht. Diese Resultate haben Anwendungen bei probabilistischen Zählalgorithmen, die zur Schätzung der Kardinalitäten großer Mengen verwendet werden.

1. Introduction

Szpankowski and Rego [14] have considered n independently and identically distributed geometric random variables X_{1}, …, X_{n}. Their parameter of interest was the maximum, max{X_{1}, …, X_{n}}.

The aim of this paper is threefold:

• A slightly more direct approach will be used to this problem; Szpankowski and Rego set up recurrences for the expectation and the second moment. These recurrences are solved by generating function techniques. This is somewhat superfluous as we can directly compute the probabilities for these max–statistics.

• In the main part the following generalization will be considered: Let d ≥ 1 be an integer. We consider the d–maximum, i.e. the d–th largest element (with repetitions allowed). (d = 1 is the maximum.) To be more precise, if there are numbers x_{1}, …, x_{n} and we sort them in descending order as y_{1} ≥ ⋯ ≥ y_{n}, then the d–maximum max_{d}{x_{1}, …, x_{n}} is y_{d}. It will turn out, that, by choosing d to be large, the variance can be made quite small. We will give quantitative asymptotic results. This is a nontrivial task since the expectation contains periodic fluctuations which give an essential contribution to the variance.

• An important observation is the application of these results to probabilistic counting, [2]. Without going into details, n data values produce an infinite 0, 1–string with only finitely many 1’s, looking like

1 1 1 … 1 0 σ σ σ … σ 1 0 0 0 …,

where σ ∈ {0, 1}. The region between the first 0 and the last 1 is called the fringe. The parameter R_{n} to estimate log_{2} n, used by Flajolet and Martin, is the index of the first 0. This parameter may by analyzed according to very delicate observations, compare [2], [9] and [11]. The index of the last 1 is just Szpankowski and Rego’s parameter minus 1 (assuming equal probabilities for 0 and 1). (One has to subtract 1 since the indices in the string start with 0 and the geometric random variable takes only values ≥ 1.) It is less accurate than the original one used by Flajolet and Martin, but with the parameter d, e.g. for d = 3, we can beat R_{n} with respect to the variance. However, in [2] there are also other variations reported in order to make the variance small. Nevertheless we mention that even an arbitrarily small variance cannot compensate the effect of approximating a discrete quantity by a continuous one. Furthermore it should be stated explicitely that the applicability is somehow limited in the following sense. The original algorithm of Flajolet and Martin can be used to compute the cardinality of a multiset. This is especially useful in database applications when the number of different elements in the union of several databases is of interest. For d ≥ 2 this doesn’t work well, because the d-maximum is sensitive (though not much) to multiple appearences of the same element.

2. Expectation and Variance

Let X be a random variable distributed according to the geometric distribution with parameter p; as usual, set q = 1 − p. It is convenient to define Q = q^{−1} and L = log Q. Then, Prob{X ≤ k} = 1 − q^{k} and Prob{X > k} = q^{k}. Therefore

Prob {max_{d}{X_{1}, …, X_{n}} ≤ k}

= ∑_{λ=0}^{d−1} Prob{λ elements are > k and the others are ≤ k}

= ∑_{λ=0}^{d−1} \binom{n}{λ}q^{kλ} (1 − q^{k})^{n−λ} .

Let E_{n}^{(d)} be the expectation of the d–maximum. We have

\begin{aligned}E_{n}^{(d)} & = ∑_{k≥0} Prob \{max_{d}\{X_{1}, …, X_{n}\} > k\} \\ & = ∑_{k≥0} [1 − ∑_{λ=0}^{d−1} \binom{n}{λ}q^{kλ} (1 − q^{k})^{n−λ}] \end{aligned}

We expand (1 − q^{k})^{n−λ} according to the binomial theorem, interchange the sums and combine the “1” with the instance λ = 0 to get

E_{n}^{(d)} = − ∑_{i=1}^{n} \binom{n}{i}(−1)^{i} \frac{1}{1 − q^{i}} − ∑_{λ=1}^{d−1} \binom{n}{λ} ∑_{i=0}^{n−λ} \binom{n − λ}{i}(−1)^{i} \frac{1}{1 − q^{λ+i}} .

Observe that the first sum is just E_{n}^{(1)}. Alternating sums of the type

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

are most easily evaluated asymptotically by Rice’s method, compare [5]:

Lemma 1. Let C be a curve surrounding the points s, s + 1, …, n (s ∈ ℕ) in the complex plane and let f(z) be analytic inside C. Then

∑_{k=s}^{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)}. □

This lemma is useful, because the integral may be asymptotically evaluated by collecting the residues of [n; z]f(z) with ℜz < s. Consider the instance of Szpankowski and Rego,

E_{n}^{(1)} = − ∑_{i=1}^{n} \binom{n}{i}(−1)^{i} \frac{1}{1 − Q^{−i}} = ∑_{i=1}^{n} \binom{n}{i}(−1)^{i}f(i)

with

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

At z = 0, the local expansion looks like

f(z) ∼ −\frac{1}{Lz} (1 + \frac{Lz}{2} ) .

The quantity [n; z] has also a pole at z = 0;

[n; z] ∼ −\frac{1}{z}(1 + zH_{n})

with a harmonic number H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n}. The residue is^{1}

[z^{−1}] \frac{1}{Lz} (1 + \frac{Lz}{2} ) \frac{1}{z}(1 + zH_{n}) = \frac{1}{2} + \frac{H_{n}}{L} .

Observe that H_{n} ∼ log n + γ.

There are also simple poles at z = χ_{k} = \frac{2kπi}{L}, k ∈ ℤ \ \{0\} with residue

−\frac{[n; χ_{k}]}{L} ∼ −\frac{1}{L}Γ(−χ_{k})n^{χ_{k}} (n → ∞).

Collecting all residues we obtain again the result from Szpankowski and Rego:

1[z^{n}]f(z) denotes the coefficient of z^{n} in the (Laurent-) series f(z).

Theorem 2.

E_{n}^{(1)} ∼ log_{Q} n + \frac{γ}{L} + \frac{1}{2} + P_{1} (log_{Q} n)

where P_{1}(x) is a continuous periodic function of period 1, mean zero, small amplitude and Fourier expansion

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

To perform the generalization to the general case we only have to consider the extra terms

− ∑_{λ=1}^{d−1} \binom{n}{λ} ∑_{i=0}^{n−λ} \binom{n − λ}{i}(−1)^{i} \frac{1}{1 − Q^{−λ−i}} .

To this end, let N := n − λ and consider

∑_{i=0}^{N} \binom{N}{i}(−1)^{i}f(i),

with

f(z) = \frac{1}{1 − Q^{−λ−z}} .

Now there is only a simple pole at z = −λ. We find immediately that

Res_{z=−λ}[N; z]\frac{1}{1 − Q^{−λ−z}} = \frac{1}{L} \frac{N!(λ − 1)!}{(N + λ)!}.

Therefore the correction is (apart from the fluctuations) asymptotic to

−\frac{1}{L} ∑_{λ=1}^{d−1} \binom{n}{λ}\frac{(n − λ)!(λ − 1)!}{n!} = −\frac{1}{L}H_{d−1}.

Hence we have

Theorem 3. As n → ∞, we have

E_{n}^{(d)} ∼ log_{Q} n + \frac{γ}{L} + \frac{1}{2} − \frac{1}{L}H_{d−1} + P_{1} (log_{Q} n)

where P_{1}(x) = P_{1,d}(x) is a continuous periodic function of period 1, mean zero, small amplitude and Fourier expansion

P_{1}(x) = −\frac{1}{L} ∑_{k≠0} e^{2πikx}Γ (−χ_{k}) (1 + ∑_{λ=1}^{d−1} \frac{(λ − 1 − χ_{k})_{λ}}{λ!} ) . □

With regard to the variance we start with the second moment, which is easily computed as

∑_{k≥0}(2k + 1) [1 − ∑_{λ=0}^{d−1} \binom{n}{λ}q^{kλ} (1 − q^{k})^{n−λ}]

= − ∑_{i=1}^{n} \binom{n}{i}(−1)^{i} \frac{1 + Q^{−i}}{(1 − Q^{−i})^{2}}

− ∑_{λ=1}^{d−1} \binom{n}{λ} ∑_{i=0}^{n−λ} \binom{n − λ}{i}(−1)^{i} \frac{1 + Q^{−λ−i}}{(1 − Q^{−λ−i})^{2}} .

Let’s start with the main term

∑_{i=1}^{n} \binom{n}{i}(−1)^{i}f(i)

with

f(z) = −\frac{1 + Q^{−z}}{(1 − Q^{−z})^{2}} .

At z = 0 there is altogether a triple pole; we have

f(z) ∼ −\frac{2}{L^{2}z^{2}} (1 + \frac{Lz}{2} + \frac{L^{2}z^{2}}{6} ) .

Also,

[n; z] ∼ −\frac{1}{z} (1 + zH_{n} + z^{2} \frac{H_{n}^{2} + H_{n}^{(2)}}{2} ) ,

(with H_{n}^{(2)} = ∑_{k=1}^{n} \frac{1}{k^{2}} , a harmonic number of order 2) and the residue of [n; z]f(z) is

\frac{H_{n}^{2}}{L^{2}} + \frac{H_{n}^{(2)}}{L^{2}} + \frac{H_{n}}{L} + \frac{1}{3}

∼ log_{Q}^{2} n + \frac{2γ log_{Q} n}{L} + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} + log_{Q} n + \frac{γ}{L} + \frac{1}{3}.

For the correction, consider (with N = n − λ)

∑_{i=0}^{N} \binom{N}{i}(−1)^{i}f(i)

with

f(z) = \frac{1 + Q^{−λ−z}}{(1 − Q^{λ−z})^{2}} .

At z = −λ there is a double pole; with w = λ + z → 0 we have

f(z) ∼ \frac{2}{L^{2}w^{2}} (1 + \frac{Lw}{2} ) .

Furthermore,

[N; z] ∼ \frac{N!(λ − 1)!}{(N + λ)!}[1 + w (H_{N+λ} − H_{λ−1}) ],

and the residue of [N; z]f(z) at z = −λ is

\frac{N!(λ − 1)!}{(N + λ)!} \frac{2}{L^{2}} (\frac{L}{2} + H_{N+λ} − H_{λ−1}) .

We can sum this up as follows:

− ∑_{λ=1}^{d−1} \binom{n}{λ}\frac{(n − λ)!(λ − 1)!}{n!} \frac{2}{L^{2}} (\frac{L}{2} + H_{n} − H_{λ−1})

= − ∑_{λ=1}^{d−1} \frac{1}{λ} (\frac{1}{L} + \frac{2}{L^{2}} H_{n} − \frac{2}{L^{2}} H_{λ−1})

= −\frac{1}{L}H_{d−1} − \frac{2}{L^{2}} H_{n}H_{d−1} + \frac{H_{d−1}^{2}}{L^{2}} − \frac{H_{d−1}^{(2)}}{L^{2}}

Altogether we find for the second moment (apart from the fluctuations) the asymptotic equivalent

log_{Q}^{2} n + \frac{2γ log_{Q} n}{L} + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} + log_{Q} n + \frac{γ}{L} + \frac{1}{3}

− \frac{1}{L}H_{d−1} − \frac{2H_{d−1}}{L} log_{Q} n − \frac{2H_{d−1}}{L^{2}} γ + \frac{H_{d−1}^{2}}{L^{2}} − \frac{H_{d−1}^{(2)}}{L^{2}} .

Now for the variance we must subtract the square of the expectation. There are many terms cancelling, and we end up with

Proposition 4. The variance V_{n}^{(d)} fulfills

V_{n}^{(d)} ∼ \frac{π^{2}}{6L^{2}} + \frac{1}{12} − \frac{H_{d−1}^{(2)}}{L^{2}} − [P_{1}^{2}]_{0} + P_{2} (log_{Q} n) . □

where P_{2}(x) is a continuous periodic function of period 1 and mean 0, and [P_{1}^{2}]_{0} is the “mean” of the square of the function P_{1}(x) from Theorem 3.

3. An Analysis of the Function P_{1}(x)

First, by the elementary formula

∑_{k=0}^{r} \binom{k + a}{k} = \binom{r + a + 1}{r},

we may rewrite

P_{1}(x) = −\frac{1}{L} ∑_{k≠0} e^{2πikx}Γ (−χ_{k}) ∑_{λ=0}^{d−1} \frac{(λ − 1 − χ_{k})_{λ}}{λ!}

as

P_{1}(x) = −\frac{1}{L} ∑_{k≠0} e^{2πikx}Γ (−χ_{k}) \binom{d − 1 − χ_{k}}{d − 1}.

Therefore the mean [P_{1}^{2}]_{0} of P_{1}^{2}(x) is

[P_{1}^{2}]_{0} = \frac{1}{L^{2}} ∑_{k≠0} |Γ (−χ_{k})|^{2} \binom{χ_{k} − 1}{d − 1}\binom{−χ_{k} − 1}{d − 1};

it is this quantity that we are going to study thoroughly in this section.

Lemma 5. \binom{a − 1}{n}\binom{−a − 1}{n} = ∑_{k=0}^{n} \binom{a}{k}\binom{−a}{k}

Proof. We use Euler’s first identity for hypergeometric series [7], [8]

2F_{1}(c − a, c − b; c; x) = _{1}F_{0}(c − a − b; x)_{2}F_{1}(a, b; c; x)

in the special instance c = 1, b = −a where it takes the form

∑_{n≥0} \frac{(1 − a)^{(n)}(1 + a)^{(n)}}{n!^{2}} x^{n} = \frac{1}{1 − x} ∑_{n≥0} \frac{a^{(n)}(−a)^{(n)}}{n!^{2}} x^{n}

with the Pochhammer symbol a^{(n)} = a(a + 1) … (a + n − 1). Now comparing the coefficients of x^{n} and observing that

\frac{(1 − a)^{(n)}(1 + a)^{(n)}}{n!^{2}} = \binom{n − a}{n}\binom{n + a}{n} = \binom{−a − 1}{n}\binom{a − 1}{n}

resp.

\frac{a^{(k)}(−a)^{(k)}}{k!^{2}} = \binom{a + k − 1}{k}\binom{−a + k − 1}{k} = \binom{−a}{k}\binom{a}{k}

gives the desired identity. □

Remark. Once the formula is known, it may of course also be proved by induction.

An immediate consequence is the formula

[P_{1}^{2}]_{0} = \frac{1}{L^{2}} ∑_{j=0}^{d−1} \frac{1}{j!^{2}} ∑_{k≠0} |Γ (j − χ_{k})|^{2} .

The following lemmata evaluate the inner sums. A proof for the special instance Q = 2, using series transformation results due to Ramanujan, is given in [10]. In the Appendix, we sketch an alternative proof for general Q > 1 using the Mellin transform combined with the residue calculus.

Lemma 6. If j ≥ 1,

∑_{k≠0} Γ(j + χ_{k})Γ(j − χ_{k}) = 2L(2j − 1)! ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1}
+ L(2j − 1)!2^{−2j} − (j − 1)!^{2}.

Lemma 7.

∑_{k≠0} Γ(χ_{k})Γ(−χ_{k}) = \frac{π^{2}}{6} + \frac{L^{2}}{12} − L log 2 − 2L ∑_{h≥1} \frac{(−1)^{h−1}}{h (Q^{h} − 1)}

Now this gives us our final formula which we therefore state as a proposition. Proposition 8.

[P_{1}^{2}]_{0} = \frac{π^{2}}{6L^{2}} + \frac{1}{12} − \frac{log 2}{L} − \frac{2}{L} ∑_{h≥1} \frac{(−1)^{h−1}}{h (Q^{h} − 1)}

+ \frac{2}{L} ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j} ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1}

+ \frac{1}{L} ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j}2^{−2j} − \frac{H_{d−1}^{(2)}}{L^{2}}

4. Behaviour of the Variance for large d

Combining Propositions 4 and 8 we have proved that the main term of V_{n}^{(d)} for n → ∞ is given by

\frac{log 2}{L} − \frac{1}{L} ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j}2^{−2j} + \frac{2}{L} ∑_{h≥1} \frac{(−1)^{h−1}}{h (Q^{h} − 1)}

− \frac{2}{L} ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j} ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1} + P_{2}(log_{2} n)

where P_{2}(x) has mean zero.

In this section we want to analyze the nonfluctuating part of the above quantity for d → ∞.

We start with the first sum and prove, as the main step, Lemma 9.

4^{−j} \frac{1}{2j} \binom{2j}{j} = −[t^{j}] log \frac{1 + \sqrt{1 − t}}{2}

Proof. We have

[t^{j}] log \frac{1 + \sqrt{1 − t}}{2} = \frac{1}{j}[t^{j−1}] (log \frac{1 + \sqrt{1 − t}}{2})′

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

To find the coefficient in this sum we use the formal residue calculus, as described in [6], with the substitution

t = \frac{4u}{(1 + u)^{2}}  and  dt = \frac{4(1 − u)}{(1 + u)^{3}}du.

[t^{j−1}]\frac{1}{\sqrt{1 − t} (1 + \sqrt{1 − t} )}

= [t^{−1}]t^{−j} \frac{1}{\sqrt{1 − t} (1 + \sqrt{1 − t} )}

= [u^{−1}]4^{−j}u^{−j}(1 + u)^{2j} \frac{1 + u}{1 − u} \frac{1 + u}{2} \frac{4(1 − u)}{(1 + u)^{3}}

= \frac{1}{2}4^{1−j}[u^{j−1}](1 + u)^{2j−1} = \frac{1}{2}4^{1−j}\binom{2j − 1}{j − 1},

and this is clearly equivalent to the announced formula. □

As an immediate consequence of the lemma we get

Proposition 10. As d → ∞,

\frac{1}{L} ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j}2^{−2j} = \frac{log 2}{L} + \frac{1}{\sqrt{π}} d^{−1/2} + O(d^{−3/2}).

Proof. We have

∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j}2^{−2j} = −[t^{d−1}]\frac{1}{1 − t} log \frac{1 + \sqrt{1 − t}}{2}

= [t^{d−1}]\frac{log 2}{1 − t} − [t^{d−1}]\frac{1}{1 − t} log (1 + \sqrt{1 − t} )

= log 2 − [t^{d−1}]\frac{1}{1 − t} log (1 + \sqrt{1 − t} )

The latter generating function has its dominating singularity at t = 1 and behaves as

−\frac{1}{1 − t} log (1 + \sqrt{1 − t}) = \frac{1}{\sqrt{1 − t}} + O ((1 − t)^{−3/2}) (t → 1),

Order Statistics and Probabilistic Counting 10 so that by singularity analysis [4] the coefficient of t^{d−1} behaves like

\frac{1}{\sqrt{π}} d^{−1/2} + O(d^{−3/2}) (d → ∞). □

It remains to treat the more complicated sum

Σ_{d−1} = ∑_{j=1}^{d−1} \frac{1}{2j} \binom{2j}{j} ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1}.

Observe that

∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1} = ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j}} ∑_{m≥0} Q^{(−h−j)m}

= ∑_{m≥1} (Q^{−m} (1 + Q^{−m})^{−2})^{j} .

Now it follows from a simple substitution in Lemma 9 that

\frac{1}{2j} \binom{2j}{j} (\frac{1}{Q^{m}(1 + Q^{−m})^{2}} )^{j} = −[t^{j}] log (\frac{1 + \sqrt{1 − \frac{4t}{Q^{m}(1+Q^{−m})^{2}}}}{2} ) .

Therefore we have

Σ_{d−1} = −[t^{d−1}]\frac{1}{1 − t} log (\frac{1 + \sqrt{1 − \frac{4t}{Q^{m}(1+Q^{−m})^{2}}}}{2} ) .

Observing that

Σ_{∞} = − ∑_{m≥1} log (\frac{1 + \sqrt{1 − \frac{4t}{Q^{m}(1+Q^{−m})^{2}}}}{2} )

= − ∑_{m≥1} log \frac{1}{1 + Q^{−m}} = ∑_{m≥1} log (1 + Q^{−m})

we find by singularity analysis Proposition 11. For any ε > 0, we have for d → ∞

\frac{2}{L}Σ_{d−1} = \frac{2}{L} ∑_{m≥1} log (1 + Q^{−m}) + O ((\frac{4}{Q(1 + Q^{−1})^{2}} )^{d−ε})

The main term coincides with

\frac{2}{L} ∑_{h≥1} \frac{(−1)^{h−1}}{h(Q^{h} − 1)},

whereas, for Q > 1, the remainder term is exponentially small for d → ∞ compared with the remainder term from Proposition 10. Altogether we have proved:

Theorem 12. The nonfluctuating part of the main asymptotic term of the variance V_{n}^{(d)} for n → ∞ behaves for d → ∞ as

\frac{1}{\sqrt{π}} d^{−1/2} + O(d^{−3/2}).

Remark. This analysis is of more than local interest; the periodic function P_{1}(x) is not uncommon in the Analysis of Algorithms. We mention e.g. [13].

5. Application to Probabilistic Counting

To continue the discussion from the Introduction, let us just mention that (by means of a hash function) each data value produces exactly one bit, and it is in position k ≥ 0 with probability 2^{−k−1}. The OR–composition of all the bits (1’s) constitutes the string, as seen in the Introduction. Now this is exactly a geometric probability. The result of Flajolet and Martin states, that (apart from the fluctuations) the average value of R_{n} is asymptotic to log_{2} n−0.37; the Szpankowski–Rego parameter −1 has an average of log_{2} n + 0.33, whence we deduce the average size of the fringe to be less than 1.

The variance in the Flajolet–Martin–instance is approximately 1.257 and in the Szpankowski–Rego–instance 3.507.

Below we give the limiting values of the variances V_{n}^{(d)} for N → ∞ and some values of d for the special instance q = \frac{1}{2}, i.e. Q = 2.

d lim V_{n}^{(d)}
1 3.5070
2 1.4256
3 0.9053
4 0.6740

Finally we mention that from the algorithmic point of view it is easy to maintain the parameter of interest. It is not even necessary to keep the whole actual bit string (the OR–composition). It is sufficient to store the actual d data values with highest entries.

Appendix

As announced in Section 3 we sketch here a derivation of the formula from Lemma 6 (Lemma 7 can be proved in a quite similar manner).

We start from the left hand side and interpret the sum as the collection of the residues at the poles χ_{k}, k ≠ 0, of the function

L\frac{Γ(j + z)Γ(j − z)}{e^{Lz} − 1}.

Therefore we have

∑_{k≠0} |Γ(j + χ_{k})|^{2} = \frac{L}{2πi} ∫_{(1/2)} \frac{Γ(j + z)Γ(j − z)}{e^{Lz} − 1}dz

− \frac{L}{2πi} ∫_{(−1/2)} \frac{Γ(j + z)Γ(j − z)}{e^{Lz} − 1}dz − Γ(j)^{2}.

(Γ(j)^{2} is the residue at z = 0.)

Now we use the decomposition

\frac{1}{e^{Lz} − 1} = −1 − \frac{1}{e^{−Lz} − 1}

for the second integral and get

− \frac{L}{2πi} ∫_{(−1/2)} \frac{Γ(j + z)Γ(j − z)}{e^{Lz} − 1}dz

= \frac{L}{2πi} ∫_{(−1/2)} Γ(j + z)Γ(j − z)dz + \frac{L}{2πi} ∫_{(−1/2)} \frac{Γ(j + z)Γ(j − z)}{e^{−Lz} − 1}dz

= \frac{L}{2πi} ∫_{(0)} Γ(j + z)Γ(j − z)dz + \frac{L}{2πi} ∫_{(1/2)} \frac{Γ(j − z)Γ(j + z)}{e^{Lz} − 1}dz.

Therefore

∑_{k≠0} |Γ(j + χ_{k})|^{2}

= \frac{2L}{2πi} ∫_{(1/2)} \frac{Γ(j + z)Γ(j − z)}{e^{Lz} − 1}dz + \frac{L}{2πi} ∫_{(0)} Γ(j + z)Γ(j − z)dz − Γ(j)^{2}

= I_{1} + I_{2} − Γ(j)^{2}.

I_{1} is evaluated by shifting the contour to the right and collecting the negative residues, which gives

I_{1} = −2L ∑_{m≥j} \frac{Γ(j + m)}{e^{Lm} − 1} \frac{(−1)^{j−m+1}}{(m − j)!}

and with m = h + j

= 2L ∑_{h≥0} \frac{(h + 2j − 1)!(−1)^{h}}{h!} \frac{1}{Q^{h+j} − 1}

= 2L(2j − 1)! ∑_{h≥0} \binom{−2j}{h}\frac{1}{Q^{h+j} − 1}.

Order Statistics and Probabilistic Counting 13

Integral I_{2} is of interest for itself and appears already in early references to the Mellin transform technique as by Nielsen [12, p.224].

We start with the function

f(x) = \frac{x^{j}}{(1 + x)^{2j}}

and perform its Mellin transform (see, e.g., [3] for definitions)

f^{∗}(s) = ∫_{0}^{∞} f(x)x^{s−1}dx = B(j + s, j − s) = \frac{Γ(j + s)Γ(j − s)}{Γ(2j)}

with the Beta function B(z, w) (compare [1]). The fundamental strip is ⟨−j, j⟩. Therefore the inversion formula for the Mellin transform gives

f(x) = \frac{1}{2πi} ∫_{(0)} \frac{Γ(j + s)Γ(j − s)}{Γ(2j)}x^{−s}ds.

Now we may evaluate at x = 1 and get the formula

\frac{1}{2πi} ∫_{(0)} Γ(j + s)Γ(j − s)ds = Γ(2j)2^{−2j}.

This completes the proof of Lemma 6.

References

1. M.Abramowitz, I.A.Stegun, Handbook of Mathematical Functions, Dover, New York, 1970.

2. P.Flajolet and G.N.Martin, Probabilistic Counting Algorithms for Data Base Applications, J.Comput.Syst.Sci. 31 (1985), 182–209.

3. P.Flajolet, M.Régnier and R.Sedgewick, Combinatorics on Words, Springer NATO ASI Series F, Vol. 12, Berlin, 1985.

4. P.Flajolet and A.Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216–240.

5. P.Flajolet and R.Sedgewick, Digital Search Trees Revisited, SIAM J.Comput. 15 (1986), 748– 767.

6. I.P.Goulden and D.M.Jackson, Combinatorial Enumeration, John Wiley & Sons, New York, 1983.

7. R.L.Graham, D.E.Knuth and O.Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA.

8. P.Henrici, Applied and Computational Complex Analysis Volume 1, John Wiley & Sons, New York, 1974.

9. P.Kirschenhofer and H.Prodinger, On the Analysis of Probabilistic Counting, Number Theoretic Analysis, E.Hlawka, R.F.Tichy (Eds.), Lecture Notes in Mathematics 1452 (1990), 117–120.

10. P.Kirschenhofer and H.Prodinger, On Some Applications of Formulæof Ramanujan in the Analysis of Algorithms, Mathematika 38 (1991), 14–33.

11. P.Kirschenhofer, H.Prodinger and W. Szpankowski, How to Count Quickly and Accurately: A Unified Analysis of Probabilistic Counting and Other Related Problems, ICALP92, W.Kuich (Ed.), Lecture Notes in Computer Science 623 (1992), 211–222.

12. N.Nielsen, Handbuch der Theorie der Gammafunktion, Teubner, Leipzig, 1906.

Order Statistics and Probabilistic Counting 14

13. H.Prodinger, Über längste 1-Teilfolgen in 0-1–Folgen, in: Zahlentheoretische Analysis II, E.Hlawka, Ed., Lecture Notes in Mathematics 1262 (1987), 124–133.

14. W.Szpankowski and V.Rego, Yet another Application of a Binomial Recurrence: Order Statistics, Computing 43 (1990), 401–410.

Department of Algebra and Discrete Mathematics TU Vienna Wiedner Hauptstraße 8-10/118 A-1040 Vienna Austria