ON THE ANALYSIS OF PROBABILISTIC COUNTING

Peter Kirschenhofer and Helmut Prodinger

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

Abstract. In this note an alternative analysis of a probabilistic counting algorithm due to Flajolet and Martin is presented. The asymptotic evaluation of certain combinatorial sums is performed via residue calculus instead of Flajolet’s Mellin transform approach that had to use some unpleasant real analysis.

1. Introduction

A basic probabilistic counting procedure to estimate the number n of distinct elements in a multiset M uses the following idea (compare [1]): We map the possible domain into the set of sufficiently long strings of 0 and 1 such that each string is taken as a value of this mapping with equal probability (a so-called ”hash-function”). The bitwise OR-composition of all the images of the elements of M contains information on the size of n: the position of the leftmost zero is used as an estimate of log_{2} n. Let R be this quantity. In [1] it is shown that the expected value \overline{R_{n}} of R fulfills

Theorem 1.

\overline{R_{n}} ∼ log_{2} n + C_{1} + δ_{1}(log_{2} n)
where C_{1} = −\frac{1}{2} + \frac{γ}{log 2} + log (\frac{2}{3} ∏_{p=1}^{∞} [\frac{(4p + 1)(4p + 2)}{4p(4p + 3)}]^{(−1)^{ν(p)}}) ,
ν(p) = the number of ones in the binary representation of p,
and δ_{1}(x) = \frac{1}{log 2} ∑_{k≠0} Γ (\frac{2kπi}{log 2}) N (\frac{2kπi}{log 2}) ,

with N(s) = the analytic continuation of ∑_{j≥1} \frac{(−1)^{ν(j)}}{j^{s}} .

We mention that δ_{1}(x) is a continuous periodic function of period 1 with very small amplitude and mean zero, so that for practical purposes this periodic fluctuations may be safely ignored.

The variance σ_{n}^{2} of the random variable R is very small:

Typeset by AMS-TEX

Theorem 2.

σ_{n}^{2} ∼ \frac{π^{2}}{6 log^{2} 2} − \frac{N′(0)^{2}}{log^{2} 2} − \frac{N′′(0)}{log^{2} 2} + \frac{1}{12} − [δ_{1}^{2}]_{0} + δ_{2}(log_{2} n),

where N(s) is defined in Theorem 1, [δ_{1}^{2}]_{0} is the mean of δ_{1}^{2}(x), and δ_{2}(x) is again a periodic function of very small amplitude and mean zero.

Numerically

σ_{n}^{2} ∼ 1.257 ….

Observe the somewhat erroneous expression for σ_{n}^{2} in [1] whereas the numerical approximation therein is correct.

In [1] the Theorems are achieved by evaluating certain combinatorial sums by the use of Mellin’s integral transform.

In this note we gain the results by a more concise method which has proved to be successful already in a number of other situations ([2],[3],[4]).

2. The Analysis

Let q_{n,k} be the probability that for a multiset of n distinct elements R ≥ k. In [1] it is shown that

q_{n,k} = ∑_{j=0}^{2^{k}−1} (−1)^{ν(j)} (1 − \frac{j}{2^{k}} )^{n}.  (1)

Observing that

\overline{R_{n}} = ∑_{l≥1} q_{n,l}  (2)

and

σ_{n}^{2} = 2 ∑_{l≥1} l q_{n,l} − \overline{R_{n}} − \overline{R_{n}}^{2},  (3)

we have to evaluate certain alternating sums asymptotically.

For \overline{R_{n}} we have from (2) and (1)

\overline{R_{n}} = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k} ∑_{l≥1} ∑_{j=1}^{2^{l}−1}(−1)^{ν(j)} (\frac{j}{2^{l}} )^{k} ,

so that \overline{R_{n}} is of the form

\overline{R_{n}} = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k}f(k),  (4)

with

f(z) = ∑_{l≥1} ∑_{j=1}^{2^{l}−1}(−1)^{ν(j)} (\frac{j}{2^{l}} )^{z} .

Using residue calculus it can be seen that the sum in (4) may be rewritten as a contour integral:

\overline{R_{n}} = −\frac{1}{2πi} ∫_{C}[n; z]f(z)dz,  (5)

with [n; z] = \frac{(−1)^{n−1}n!}{z(z − 1) ⋯ (z − n)},

where C surrounds the singularities z = 1, 2, …, n of the integrand.

Expanding the contour of integration in a well-suited manner (compare [4] for technical details), we find

\overline{R_{n}} ∼ ∑ Res_{z=z_{i}}([n; z]f(z))  (6)

where the sum is taken over all poles z_{i} of [n; z]f(z) with real part larger than some fixed c that differ from 1, ..., n.

In our instance we may write

f(z) = f_{1}(z) − f_{2}(z),

where

\begin{aligned}f_{1}(z) & = ∑_{l≥1} lim_{k→∞} ∑_{j=1}^{2^{k}−1}(−1)^{ν(j)} (\frac{j}{2^{l}} )^{z} \\ & = \frac{1}{2^{z} − 1}N(−z), \end{aligned}

and

f_{2}(z) = ∑_{l≥1} lim_{k→∞} ∑_{j=2^{l}}^{2^{k}−1}(−1)^{ν(j)} (\frac{j}{2^{l}} )^{z} .

From [1] it follows immediately that f_{2}(z) is analytic for ℜz > −1 with f_{2}(0) = 0. If we use c = −\frac{1}{2} in (6) and take into account the residues at the poles z = χ_{k} =

2kπi/L, k ∈ Z; L = log 2, of [n; z]f_{1}(z) we find:

i) For z → 0

\frac{1}{2^{z} − 1} ∼ \frac{1}{Lz} − \frac{1}{2},
N(−z) ∼ N(0) − zN′(0), where N(0) = −1,
[n; z] ∼ −\frac{1}{z} − H_{n}, where H_{n} = ∑_{k=1}^{n} \frac{1}{k} ,

so that

Res_{z=0}([n; z]f_{1}(z)) ∼ \frac{log n}{L} + (\frac{γ}{L} + \frac{N′(0)}{L} − \frac{1}{2})

ii) For z → χ_{k}, k ≠ 0

\begin{aligned}\frac{1}{2^{z} − 1} & ∼ \frac{1}{L(z − χ_{k})}, \\ N(−z) & ∼ N(−χ_{k}), \\ [n; z] & ∼ n^{χ_{k}}Γ(−χ_{k}), \end{aligned}

so that

Res_{z=χ_{k}}([n; z]f_{1}(z)) ∼ \frac{1}{L}N(−χ_{k})Γ(−χ_{k})e^{2kπi log_{2} n}.

iii) Since f_{2}(0) = 0, we have

Res_{z=0}([n; z]f_{2}(z)) = 0.

Combining these results we rederive Theorem 1.

For the evaluation of N′(0) we use the following formula

N′(0) = log \frac{2}{3} + ∑_{p≥1}(−1)^{ν(p)} log \frac{(4p + 1)(4p + 2)}{4p(4p + 3)}  (7)

which occurs by grouping terms four by four.

The analysis of the variance follows the same idea. We have

∑_{l≥1} l q_{n,l} = ∑_{k=1}^{n} \binom{n}{k}(−1)^{k}g(k)

with

g(z) = \frac{2^{z}}{(2^{z} − 1)^{2}} N(−z) − g_{2}(z),

where g_{2}(z) is analytic for ℜz > −1 and fulfills g_{2}(0) = 0.

Calculating the residues of

[n; z]\frac{2^{z}}{(2^{z} − 1)^{2}} N(−z)

we find that, apart from periodic fluctuations of mean zero,

\begin{aligned}∑_{l≥1} l q_{n,l} & ∼ \frac{1}{2} \frac{log^{2} n}{L^{2}} + \{\frac{γ}{L^{2}} + \frac{N′(0)}{L^{2}}\} log n \\ & + \frac{γ^{2}}{2L^{2}} + \frac{π^{2}}{12L^{2}} + \frac{γN′(0)}{L^{2}} − \frac{N′′(0)}{2L^{2}} − \frac{1}{12}. \end{aligned}  (8)

From (8) we gain Theorem 2 immediately.

References

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

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

3. P. Kirschenhofer and H. Prodinger, Approximate Counting: An Alternative Analysis, RAIRO Informatique Théorique (1990) (to appear).

4. U. Schmid, Analyse von Collision-Resolution Algorithmen in Random-Access- Systemen mit dominanten Übertragungskanälen, Dissertation TU Wien (1986).

TU Vienna, Wiedner Hauptstraße 8-10, A-1040 Vienna, Austria