NOTE

HYPOTHETIC ANALYSES:

APPROXIMATE COUNTING IN THE STYLE OF KNUTH,

PATH LENGTH IN THE STYLE OF FLAJOLET

Helmut Prodinger

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

October 16, 1991

1. Introduction

The first analysis of approximate counting is due to Flajolet [1], whereas the first satisfactory analysis of the average path length in digital search trees has been performed by Knuth [4,p.497ff]. Both authors have used the Mellin Integral Transform (see [2] for a brilliant introduction), but in rather different ways. It was shown by Kirschenhofer and the present writer [3] that both problems are very similar (not to say “almost identical”).

It is now amusing to figure out what Flajolet and Knuth would have done by considering the exchanged problems. The aim of this note is to perform their analyses. It is the author’s opinion that this is entertaining and amusing both from the methodological as well as the historical point of view.

2. Flajolet’s analysis of approximate counting

Flajolet considered C_{N}^{[F]}, the average value of a counter after N increments in a probabilistic algorithm. He computed C_{N}^{[F]} via

C_{N}^{[F]} = ∑_{l≥1} l · p_{N,l}^{[F]} ,

with

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

and

Q_{m} = ∏_{i=1}^{m} (1 − \frac{1}{2^{i}} ) .

Typeset by AMS-TEX 2 HELMUT PRODINGER

Then he approximated p_{N,l}^{[F]} by Φ (\frac{N}{2^{l}} ), with

Φ(x) = \frac{1}{Q_{∞}} ∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j}} e^{−x2^{j}}.

Here,

Q_{∞} = lim_{m→∞} Q_{m} = ∏_{i≥1} (1 − \frac{1}{2^{i}} ) = 0.288788 · · · .

Then the Mellin transform was computed:

Φ^{∗}(s) = Γ(s) · ξ(s),

with

ξ(s) = \frac{1}{Q_{∞}} ∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j}} 2^{−js}.

Finally,

C_{N}^{[F]} ∼ F (N) = ∑_{l≥1} l Φ (\frac{N}{2^{l}} ) ,

and

F^{∗}(s) = \frac{2^{s}}{(2^{s} − 1)^{2}} Φ^{∗}(s).

By considering the negative residues of F^{∗}(s)x^{−s} for ℜs = 0 he obtained Theorem 1. (Flajolet, 1985 [1])

C_{N}^{[F]} ∼ log_{2} N + \frac{γ}{log 2} − α + \frac{1}{2} − δ_{0} (log_{2} N) ,

where

α = ∑_{i≥1} \frac{1}{2^{i} − 1} = 1.6066 ⋯,
γ = 0.57721 ⋯  (Euler’s constant),
δ_{0}(x) = \frac{1}{log 2} ∑_{k≠0} Γ (−\frac{2kπi}{log 2}) e^{2kπix}. □

3. Knuth’s analysis of the average path length in DSTs Knuth considered

L_{N}^{[K]} = ∑_{k=2}^{N} \binom{N}{k}(−1)^{k}Q_{k−2}.  (K)

He changed it to

L_{N}^{[K]} ∼ ∑_{n≥0} a_{n+1} ∑_{m≥0} 2^{m(1−n)} (e^{−N/2^{m}} − 1 + \frac{N}{2^{m}} ) ,

NOTE HYPOTHETIC ANALYSES: APPROXIMATE COUNTING IN THE STYLE OF KNUTH, PATH LENGTH IN THE STYLE OF FLAJOLET3

with

a_{i} = \frac{(−1)^{i+1}2^{−\binom{i}{2}}}{Q_{i−1}} .

By “Mellin”^{1} he obtained

L_{N}^{[K]} ∼ ∑_{n≥0} a_{n+1} \frac{1}{2πi} ∫_{− \frac{3}{2} −i∞}^{− \frac{3}{2} +i∞}Γ(s)N^{−s} \frac{1}{1 − 2^{1−n+s}} ds.

The negative residues of the integrand for ℜs = −1 give the following result

Theorem 2. (Knuth, 1973 [4])

L_{N}^{[K]} ∼ N (log_{2} N + \frac{γ}{log 2} − α + \frac{1}{2} − \frac{1}{log 2} + δ_{−1} (log_{2} N)) ,

with

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

Now we could show [3] that

C_{N}^{[F]} = 1 − ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}2^{−k}Q_{k−1},  (F)

and this similarity with (K) motivated this note. Section 6 contains an attempt to “explain” this phenomen.

4. Knuth’s analysis of approximate counting

We need some “Q-formulæ” (see, e.g. [1], [4, exercise 5.1.1–16]). Let

Q(x) = ∏_{i≥1} (1 − \frac{x}{2^{i}} ) ,

then

Q_{k} = \frac{Q_{∞}}{Q (2^{−k})}.  (Q1)

Euler’s formulæ:

\frac{1}{1 − t} \frac{1}{Q(t)} = ∑_{n≥0} \frac{t^{n}}{Q_{n}}  (E1)

1Actually, Knuth never mentioned the word “Mellin transform”. He basically used the formula e^{−x} = \frac{1}{2πi} ∫ _{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞} Γ(s)x^{−s}ds and some variants that can be proved directly by residue calculus.

Because of the ubiquitous appearance of the Gamma function he christened the approach “Gamma function method”. Also, he gives the credits for this procedure to N. G. de Bruijn.

Q(t) = ∑_{n≥0} a_{n+1}t^{n}  (E2)

Finally we need

∑_{l≥1} \frac{a_{l+1}}{1 − 2^{−l}} = −α;

this follows from

\frac{Q_{∞}}{Q(x)} = ∑_{i≥1} \frac{a_{i}}{1 − x2^{−i}} .

Now

C_{N}^{[F]} − 1 = −Q_{∞} ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}2^{−k} ∏_{l≥0} \frac{1}{1 − 2^{−l−k}}  (by Q1)

= −Q_{∞} ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}2^{−k} ∑_{m≥0} 2^{−km} \frac{1}{Q_{m}} (by E1)

= − ∑_{m≥0} (∑_{k=0}^{N} \binom{N}{k}(−1)^{k}2^{−k(m+1)} − 1) Q (2^{−m}) (by Q1)

= − ∑_{m≥0} ((1 − 2^{−m−1})^{N} − 1) ∑_{n≥0} a_{n+1}2^{−mn} (by E2)

∼ − ∑_{n≥0} a_{n+1} ∑_{m≥0} 2^{−mn} (e^{−N/2^{m+1}} − 1)

= − ∑_{n≥0} a_{n+1} \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}Γ(s)N^{−s} \frac{2^{s}}{1 − 2^{−n+s}} ds.

The negative residues at s = 0 and s = \frac{2kπi}{log 2} (k ≠ 0) give Flajolet’s result: From n = 0 we obtain

log_{2} N + \frac{γ}{log 2} − \frac{1}{2} − δ_{0} (log_{2} N) ;

from n ≥ 1 we obtain

∑_{n≥1} a_{n+1} \frac{1}{1 − 2^{−n}} = −α.

5. Flajolet’s analysis of the average path length in DSTs

We want to go back from (K) to

L_{N}^{[K]} = ∑_{l≥1} l · p_{N,l}^{[K]} ;

this representation is of course not unique. Let

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

NOTE HYPOTHETIC ANALYSES: APPROXIMATE COUNTING IN THE STYLE OF KNUTH, PATH LENGTH IN THE STYLE OF FLAJOLET5

Then

g′(1) = \{ \begin{matrix}0 & for k = 0 \\ − & Q_{k−2} & for k ≥ 1. \end{matrix}

Furthermore, we have in general

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

where [x^{l}] g(x) denotes the coefficient of x^{l} in the Taylor series expansion of g(x). Thus

L_{N}^{[K]} = − ∑_{k=1}^{N} \binom{N}{k}(−1)^{k} ∑_{l≥1} l [x^{l}] ∏_{m=0}^{k−2} (1 − \frac{x}{2^{m}} ) .

By (E1) and (E2) we have

\begin{aligned}∏_{m=0}^{k−2} (1 − \frac{x}{2^{m}} ) & = ∏_{m≥0} (1 − \frac{x}{2^{m}} ) ∏_{m≥0} (1 − \frac{x}{2^{m+k−1}} )^{−1} \\ & = ∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}x^{j}}{Q_{j}} ∑_{s≥0} \frac{1}{Q_{s}} (2^{1−k})^{s} x^{s} \end{aligned}

and thus

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

So we can write

L_{N}^{[K]} = ∑_{l≥1} l · p_{N,l}^{[K]} ,

with

\begin{aligned}p_{N,l}^{[K]} & = − ∑_{k=1}^{N} \binom{N}{k}(−1)^{k} ∑_{j=0}^{l} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j}Q_{l−j}} 2^{−(l−j)(k−1)} \\ & = ∑_{j=0}^{l} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j}Q_{l−j}} 2^{l−j} [1 − (1 − 2^{−(l−j)})^{N}] . \end{aligned}

Flajolet would approximate p_{N,l}^{[K]}/N by Ψ (\frac{N}{2^{l}} ), with

Ψ (x) = \frac{1}{Q_{∞}} ∑_{j≥0} \frac{(−1)^{j}2^{−\binom{j}{2}}}{Q_{j}} \frac{1}{x2^{j}} (1 − e^{−x2^{j}}) .

Now we perform the Mellin transform and find for −1 < ℜs < 0

(\frac{1 − e^{−x}}{x} )^{∗} (s) = ∫_{0}^{∞} (1 − e^{−x}) x^{s−2}dx = −Γ(s − 1).

Therefore

Ψ^{∗}(s) = −ξ(s)Γ(s − 1),

where the function ξ(s) was defined in Section 2. Now

\frac{L_{N}^{[K]}}{N} ∼ K(N)

with

K(x) = ∑_{l≥1} l Ψ (\frac{x}{2^{l}} ) .

As before,

K^{∗}(s) = \frac{2^{s}}{(2^{s} − 1)^{2}} · Ψ^{∗}(s).

By Mellin’s inversion theorem we have

K(x) = −\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{2^{s}}{(2^{s} − 1)^{2}} · ξ(s) · Γ(s − 1) · x^{−s}ds.

The negative residue of the integrand at s = 0 gives the contribution

log_{2} N − \frac{1}{log 2} + \frac{γ}{log 2} − α + \frac{1}{2};

the residues at s = \frac{2kπi}{log 2} produce the contribution δ_{−1} (log_{2} N).

6. An “explanation” of the similarities of the two problems

After a first reading of this paper (1991), an anonymous referee asked for a combinatorial explanation of the surprising similarity of the two seemingly different problems. This is of course a natural question and I failed in 1990 to give a good answer. However now I can offer something.

The probability generating functions for the path length in digital search trees obey the following recursion (N ≥ 1, F_{1}(z) = F_{0}(z) = 1)

F_{N+1}(z) = z^{N} ∑_{k=0}^{N} 2^{−N} \binom{N}{k}F_{k}(z)F_{N−k}(z).

(The averages L_{N} studied by Knuth are obtained via L_{N} = F′_{N}(1).)

Now I will give a combinatorial exlanation of a similar recursion for the approximate counting problem. Let, as in Section 1, p_{N,l}^{[F]} denote the probability that the counter has the value l (“level l”) after N “inputs”, and

F_{N}(z) = ∑_{l≥0} p_{N,l}^{[F]} z^{l}.

It should be noted that the counter is initially set to 1. To have a good idea what’s going on, let’s say that there are N “players”; whenever he (or she) has his turn, he tries to increase the counter by 1. If the counter has the value l, he will succeed with probability 2^{−l}; otherwise his attempt has no effect. For instance, we can ask him to throw l consecutive “heads” (or 1’s) with a fair coin. But we can think about it in another way: He starts at level 1 and flips a fair coin and can proceed if he has a 1. If he reaches the level l+1, it’s exactly what we need. Now we no longer have to think about N consecutive players; each of them can throw the dice as long as he has 1’s; throwing a 0 means to stop. How is the value of counter computed from these data? We start at level 1 and, being at level j, we can go on if there are at least j players who made it to level j + 1. The maximal level that we reach in that way is the value of the counter. Indeed, to proceed to a higher level means to kick out a successful player. From this interpretation we can set up a recursion for the probability generating functions. If k ≥ 1 players have been successful at level 1, k − 1 are going to continue. But if k = 0, the recursion stops. Hence

F_{N}(z) = z ∑_{k=1}^{N} 2^{−N} \binom{N}{k}F_{k−1}(z) + z2^{−N}, N ≥ 1, F_{0}(z) = z.

Now set, as usual, C_{N} = F′_{N}(1). Then the recursion turns into

C_{N} = 1 + 2^{−N} ∑_{k=1}^{N} \binom{N}{k}C_{k−1}, N ≥ 1, C_{0} = 1.

If we subtract the analogous recursion with N replaced by N − 1, it turns into the more feasible

2C_{N} = C_{N−1} + 1 + 2^{1−N} ∑_{k=0}^{N−1} \binom{N − 1}{k}C_{k}, N ≥ 1, C_{0} = 1.

The standard method to solve this recursion is by the use of the exponential generating function C(z) = ∑_{N≥0} C_{N}z^{N}/N!. Then

2C′(z) = C(z) + e^{z} + e^{z/2}C(\frac{z}{2}).

Now one sets D(z) = e^{−z}C(z) to obtain the easier equation

2D′(z) = −D(z) + D(\frac{z}{2}) + 1.

Then we consider the coefficients:

2D_{N+1} = − (1 − 2^{−N}) D_{N}, N ≥ 1, D_{0} = 1, D_{1} = \frac{1}{2}.

Iterating this we find

D_{N} = 2^{−N}(−1)^{N−1}Q_{N−1}, N ≥ 1, D_{0} = 1.

Since C(z) = e^{z}D(z), we have

C_{N} = ∑_{k=0}^{N} \binom{N}{k}D_{k} = 1 − ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}2^{−k}Q_{k−1};

this is formula (F).

Similar ideas are used in a forthcoming paper on probabilistic counting algorithms by Peter Kirschenhofer, Wojciech Szpankowski and the author.

7. Conclusion

Now it is worthwile to discuss the two “Mellin” styles. Knuth and Flajolet attacked their problems from different sides (both of them very natural in their respective contexts). Since in “approximate counting” it is natural to compute the probabilities directly, it was a good idea to approximate them immediately and use “Mellin” after that. In the tree context the recursions (as in Section 6) are most natural, so that Knuth had to use Euler’s formulæ in order to avoid the cancellations in (K). After that “Mellin” can be used. Flajolet used first “Mellin” and then “Euler” (in order to analyze the ξ–function); in Knuth’s case it is the other way around.

It should be stated here explicitly that this note contains no judgement about the relative qualities of the approaches. Both of them are most valuable and have influenced many people.

References

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

2. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

3. P.Kirschenhofer and H. Prodinger, Approximate Counting: An Alternative Approach, RAIRO Theoretical Informatics 25 (1991), 43–48.

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

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