APPROXIMATE COUNTING:

AN ALTERNATIVE APPROACH

Peter Kirschenhofer and Helmut Prodinger

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

Abstract. In this note an alternative analysis of approximate counting is presented by using a lemma from the calculus of finite differences instead of the Mellin integral transform.

R. Morris [6] has proposed a probabilistic algorithm that maintains an approximate count in the interval 1 to n using only about log_{2} log_{2} n bits. Approximate counting (with a binary base) starts with counter C = 1. After n increments C should contain a good approximation to ⌊log_{2} n⌋; thus C should be increased by 1 after another n increments approximately. Since only C is known the algorithm has to base its decision on the content of C alone. The following principle is used to increment the counter:

C := C + \{ \begin{matrix}0 with probability 1 − 2^{−C} \\ 1 with probability 2^{−C} \end{matrix}

Compare Flajolet [2] for a more detailed description. In the same paper a detailed analysis of this algorithm is presented and the following results are shown:

Theorem 1. After n succesive increments the average content \overline{C_{n}} of the counter satisfies:

\overline{C_{n}} ∼ log_{2} n + \frac{γ}{log 2} − α + \frac{1}{2} + δ_{1}(log_{2} n) ;

the variance σ_{n}^{2} satisfies

σ_{n}^{2} ∼ σ_{∞}^{2} + δ_{2}(log_{2} n)

where

σ_{∞}^{2} ∼ \frac{π^{2}}{6 log^{2} 2} − α − β + \frac{1}{12} − \frac{1}{log 2} ∑_{k≥1} \frac{1}{k sinh(θk)}

with

α = ∑_{k≥1} \frac{1}{2^{k} − 1} , β = ∑_{k≥1} \frac{1}{(2^{k} − 1)^{2}} , θ = \frac{2π^{2}}{log 2} ,

Typeset by AMS-TEX

We thank an anonymous referee for his/her guidance concerning a better presentation of this paper.

and δ_{1}(x) as well as δ_{2}(x) are periodic functions with period 1, mean value 0, and amplitude less than 10^{−4}.

Flajolet achieves this result by computing the probability p_{n,l} of having counter value l after n increments:

p_{n,l} = ∑_{j=0}^{l−1} \frac{(−1)^{j} 2^{−\binom{j}{2}} (1 − 2^{−(l−j)})^{n}}{Q_{j} Q_{l−1−j}} ,  (1)

where

Q_{n} = (1 − \frac{1}{2})(1 − \frac{1}{4}) … (1 − \frac{1}{2^{n}}).  (2)

The quantities

\overline{C_{n}} = ∑_{l=1}^{n} l p_{n,l} and σ_{n}^{2} = ∑_{l=1}^{n} l^{2} p_{n,l} − (\overline{C_{n}})^{2}  (3)

are then analyzed using real analysis and certain properties of the Mellin integral transform.

In the sequel we analyze the quantities in (3) by an alternative approach which avoids completely the unpleasant real analysis by making use of a classical lemma from the calculus of finite differences. This method has been attributed by Knuth [5] to S. O. Rice.

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

Moving the contour of integration it turns out that the asymptotic expansion of the alternating sum is obtained via

∑ Res (< n; z > f(z))  (4)

where the sum is taken over all poles different from 1, ..., n. (Flajolet and Sedgewick have used this technique to simplify the analysis of digital search trees in [3].)

In order to apply Lemma 2 we write (1) as

P_{n,l} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k} ∑_{j=0}^{l−1} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j} Q_{l−1−j}} 2^{−(l−j)k}.  (5)

By Euler’s partition identities [1]

∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}x^{j}}{Q_{j}} = ∏_{m≥0} (1 − \frac{x}{2^{m}} )

and

∑_{j≥0} \frac{x^{j}}{Q_{j}} = ∏_{m≥0} (1 − \frac{x}{2^{m}} )^{−1} ,

the inner sum in (5) is the coefficient

[x^{l−1}] ∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}x^{j}}{Q_{j}} ∑_{s≥0} 2^{−(s+1)k} \frac{x^{s}}{Q_{s}}

= 2^{−k}[x^{l−1}] ∏_{m=0}^{k−1} (1 − \frac{x}{2^{m}} ) .

Thus

\overline{C_{n}} = ∑_{l=1}^{n} l p_{n,l} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}2^{−k} ∑_{l=1}^{n} l [x^{l−1}] ∏_{m=0}^{k−1} (1 − \frac{x}{2^{m}} ) ,

where the summation on l can be extended to infinity without changing the value. Since

∑_{l≥1} l [x^{l−1}] g(x) = g′(1) + g(1)

we get immediately the following identity for \overline{C_{n}} which we state as a Proposition, since it is interesting in its own right.

Proposition 3.

\overline{C_{n}} = 1 − ∑_{k=1}^{n} \binom{n}{k}(−1)^{k}2^{−k}Q_{k−1}.  (6)

With

Q_{z} = \begin{matrix}∏ & j≥1 & (1 − \frac{1}{2^{j}} ) \\ ∏ & j≥1 & (1 − \frac{1}{2^{z+j}} ) \end{matrix}

we may write (6) as

\overline{C_{n}} = 1 − ∑_{k=1}^{n} \binom{n}{k}(−1)^{k}f(k) with f(z) = 2^{−z} Q_{z−1}.  (7)

The most significant pole of < n; z > f(z) different from 1, ..., n is z = 0, and the residue is

−\frac{H_{n}}{L} + \frac{1}{2} + α ∼ − log_{2} n − \frac{γ}{L} + \frac{1}{2} + α,

with L = log 2 and H_{n} the n-th Harmonic number. Further poles in z = 2kπi/L with residue equal to

\frac{1}{L}Γ (\frac{2kπi}{L})

give rise to the periodic fluctuation δ_{1}(x).

The next significant poles have real part z = −1 (simple!), so that the error term is of order n^{−1},

A similar approach allows us to evaluate the variance σ_{n}^{2} in a few lines. Since

∑_{l≥1} l^{2} [x^{l−1}] g(x) = g′′(1) + 3g′(1) + g(1)

we have

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

with

f(k) = 2^{−k}Q_{k−1}(2T_{k−1} − 3), T_{k−1} = ∑_{i=1}^{k−1} \frac{1}{2^{i} − 1}.

The continuation of Q_{k} has been referred above; T_{k} can be continued via

T_{z} = α − ∑_{i≥1} \frac{1}{2^{z+i} − 1}.

The most important pole is again z = 0 (triple) with residue

\frac{2}{L^{2}} (\frac{H_{n}^{2} + H_{n}^{(2)}}{2} + H_{n} L (\frac{1}{2} − α)) + α^{2} − 4α − β − \frac{2}{3}

∼ log_{2}^{2} n + (log_{2} n)(\frac{2γ}{L} − 2α + 1) + α^{2} − 2α − β

+\frac{γ}{L} + \frac{γ^{2}}{L^{2}} − \frac{2αγ}{L} + \frac{π^{2}}{6L^{2}} − \frac{2}{3}.

Subtracting \overline{C_{n}^{2}} yields for the variance (apart from smaller order terms)

\frac{π^{2}}{6L^{2}} − α − β + \frac{1}{12} − \frac{2}{L^{2}} ∑_{k≥1} |Γ (\frac{2kπi}{L})|^{2} + δ_{2}(log_{2} n),  (8)

where the series originates from the mean of δ_{1}^{2}(x). Observe that

|Γ(iy)|^{2} = \frac{π}{y sinh πy} , y ∈ R,

to obtain the form of σ_{∞}^{2}, whence Theorem 1.

Finally, it is striking to note that the constant σ_{∞}^{2}, whose numerical value is

σ_{∞}^{2} = 0.76301418710991095777 …

differs from the simpler

\frac{1}{2 log 2} + \frac{1}{24} = 0.76301418711114837034 …

only in the eleventh digit after the decimal point.

Indeed, using a transformation result for Dedekind’s η -function

η(τ) = e^{πiτ/12} ∏_{n≥1}(1 − e^{2πinτ}), ℑτ > 0 ,

the constant σ_{∞}^{2} appearing in (8) turns out to be

\frac{1}{2L} + \frac{1}{24} − \frac{2}{L}h_{1}(\frac{2π^{2}}{L}) + \frac{2π^{2}}{L^{2}} h_{2}(\frac{4π^{2}}{L}),

where

h_{1}(x) = ∑_{k≥1} \frac{(−1)^{k−1}}{k(e^{kx} − 1)} and h_{2}(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} ,

so that the numerical coincidence follows by the smallness of the involved functions h_{1}(x) and h_{2}(x).

Compare [4], where a closely related constant with relevance to digital search trees was evaluated by the authors and J. Schoissengeier.

Finally it should be noted that the extension to arbitrary bases of the counter can be analyzed in the same style.

References

1. G. E. Andrews, The Theory of Partitions, Addison Wesley, 1976.

2. P. Flajolet, Approximate Counting: A Detailed Analysis, BIT 25 (1985), 113–134.

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

4. P. Kirschenhofer , H. Prodinger, and J. Schoissengeier, Zur Auswertung gewisser numerischer Reihen mit Hilfe modularer Funktionen, Zahlentheoretische Analysis II (E. Hlawka, ed.), Lecture Notes in Math. 1262, Springer, Berlin, 1987, pp. 108–110.

5. D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973.

6. R. Morris, Counting Large Numbers of Events in Small Registers, Comm.ACM 21 (1978), 840–842.

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