%TCS


\input amstex
\documentstyle{amsppt}




\TagsOnRight
\topmatter

\define\CNF{C_{N}^{[F]}}
\define\CNK{L_{N}^{[K]}}
\define\sig{(-1)^j}
\define\zw{2^{-\binom j2}}
\define\qi{Q_\infty}
\define\pnlF{p_{N,l}^{[F]}}
\define\pnlK{p_{N,l}^{[K]}}
\redefine\L{\log 2}
\title NOTE\\ \\
       HYPOTHETIC ANALYSES:\\
       APPROXIMATE COUNTING IN THE STYLE OF KNUTH,\\
       PATH LENGTH IN THE STYLE OF FLAJOLET
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address
\flushpar TU Vienna
\newline Wiedner Hauptstra{\ss}e 8-10
\newline A-1040 Vienna
\newline Austria
\endaddress

\endtopmatter

\document

\rightline{{\it October 16, 1991}}

\heading
1. Introduction
\endheading

The first analysis of {\it approximate counting} is due to Flajolet
\cite{1}, where\-as the first satisfactory analysis of the
{\it average path length in digital search trees}
has been performed by Knuth \cite{4,p.497ff}.
Both authors have used the
{\it Mellin Integral Transform}
(see \cite{2} for a brilliant introduction),
but in rather different ways. It was shown by Kirschenhofer and the
present writer \cite{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
{\it historical}
point of view.

\heading
2. Flajolet's analysis of approximate counting
\endheading

Flajolet considered $\CNF$, the average value of a counter after $N$
increments in a probabilistic algorithm.
He computed $\CNF$ via
$$
\CNF =\sum_{l\ge 1}l\cdot \pnlF \ ,
$$
with
$$
\pnlF=\sum_{j=0}^{l-1}\frac{\sig \zw \left(1-2^{j-l}\right)^N}{Q_jQ_{l-1-j}}
$$
and
$$
Q_m=\prod_{i=1}^m \left(1-\frac{1}{2^i}\right).
$$
Then he approximated $\pnlF$ by $\Phi\left(\frac{N}{2^l}\right)$, with
$$
\Phi(x)=\frac{1}{\qi}\sum_{j\ge 0}\frac{\sig \zw}{Q_j}e^{-x2^j}.
$$
Here,
$$
\qi =\lim_{m\to\infty}Q_m=\prod_{i\ge 1}\left(1-\frac{1}{2^i}\right)
=0.288788\cdots.
$$
Then the Mellin transform was computed:
$$
\Phi^*(s)=\Gamma(s)\cdot \xi(s),
$$
with
$$
\xi(s)=\frac{1}{\qi}\sum_{j \ge 0}\frac{\sig \zw}{Q_j}2^{-js}.
$$
Finally,
$$
\CNF\sim F(N)=\sum_{l \ge 1}l\, \Phi\left(\frac{N}{2^l}\right),
$$
and
$$
F^*(s)=\frac{2^s}{(2^s-1)^2}\Phi^*(s).
$$
By considering the 
{\it negative residues}
of $F^*(s)x^{-s}$ for $\Re s=0$ he obtained

\proclaim{Theorem 1} (Flajolet, 1985 {\rm\cite 1})
$$
\CNF \sim \log_2N+\frac{\gamma}{\L}-\alpha+\frac 12 -
\delta_0\left(\log_2N\right),
$$
where
$$
\aligned
\alpha &=\sum_{i\ge 1}\frac{1}{2^i-1}=1.6066\cdots,\\
\gamma&=0.57721\cdots\qquad\text{(Euler's constant)},\\
\delta_0(x)&=\frac{1}{\L}\sum_{k\neq 0}
\Gamma\left(-\frac{2k\pi i}{\L}\right)
e^{2k\pi ix}.\qed
\endaligned
$$
\endproclaim

\heading
3. Knuth's analysis of the average path length in DSTs
\endheading

Knuth considered
$$
\CNK=\sum_{k=2}^N\binom Nk(-1)^kQ_{k-2}.
\tag K
$$
He changed it to
$$
\CNK\sim\sum_{n\ge 0}a_{n+1}\sum_{m\ge 0}
2^{m(1-n)}\left(e^{-N/2^m}-1+\frac{N}{2^m}\right),
$$
with
$$
a_i=\frac{(-1)^{i+1}2^{-\binom i2}}{Q_{i-1}}.
$$
By ``Mellin"
\footnote{
Actually, Knuth never mentioned the word ``Mellin transform''. He 
basically used the formula $e^{-x}=\frac{1}{2\pi i}\int_{\frac 12-i\infty}^
{\frac 12+i\infty}\Gamma(s)x^{-s}ds$ and some variants that can be
proved directly by residue calculus. Because of the 
{\it 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.
} he obtained
$$
\CNK\sim\sum_{n\ge 0}a_{n+1}\ 
\frac{1}{2\pi i}
\int\limits_{-\frac 32-i\infty}^{-\frac 32+i\infty}
\Gamma(s)N^{-s}\frac{1}{1-2^{1-n+s}}ds.
$$
The negative residues of the integrand for $\Re s=-1$ give the following
result

\proclaim{Theorem 2 }(Knuth, 1973 {\rm \cite 4})
$$
\CNK \sim N\left(\log_2N+\frac{\gamma}{\L}-\alpha+\frac 12 -\frac{1}{\L}
+\delta_{-1}\left(\log_2N\right)\right),
$$
with
$$
\delta_{-1}(x)=\frac{1}{\L}\sum_{k\neq 0}
\Gamma\left(-1-\frac{2k\pi i}{\L}\right)
e^{2k\pi ix}.\qed
$$
\endproclaim

Now we could show \cite{3} that
$$
\CNF=1-\sum_{k=1}^N\binom Nk(-1)^k2^{-k}Q_{k-1},
\tag F
$$
and this similarity with (K) motivated this note. Section 6 contains an
attempt to ``explain'' this phenomen. 

\heading 
4. Knuth's analysis of approximate counting
\endheading

We need some ``Q-formul\ae" (see, e.g. \cite{1}, \cite{4, exercise
5.1.1--16}).
Let
$$
Q(x)=\prod_{i\ge 1}\left(1-\frac{x}{2^i}\right),
$$
then
$$
Q_k=\frac{\qi}{Q\left(2^{-k}\right)}.
\tag Q1
$$
Euler's formul\ae:
$$
\frac{1}{1-t}\frac{1}{Q(t)}=\sum_{n\ge 0}\frac{t^n}{Q_n}
\tag E1
$$
$$
Q(t)=\sum_{n\ge 0}a_{n+1}t^n
\tag E2
$$
Finally we need
$$
\sum_{l\ge 1}\frac{a_{l+1}}{1-2^{-l}}=-\alpha;
$$
this follows from
$$
\frac{\qi}{Q(x)}=\sum_{i \ge 1}\frac{a_i}{1-x2^{-i}}.
$$
Now
$$
\aligned
\CNF -1&=-\qi\sum_{k=1}^N\binom Nk (-1)^k 2^{-k}
\prod_{l\ge 0}\frac{1}{1-2^{-l-k}}\qquad \text{(by Q1)}\\
&=-\qi\sum_{k=1}^N\binom Nk(-1)^k 2^{-k}
\sum_{m\ge 0}2^{-km}\frac{1}{Q_m}\qquad \text{(by E1)}\\
&=-\sum_{m\ge 0}
\left(
\sum_{k=0}^N\binom Nk (-1)^k2^{-k(m+1)}-1
\right)
Q\left(2^{-m}\right)\quad \text{(by Q1)}\\
&=-\sum_{m\ge 0}\left(\left(1-2^{-m-1}\right)^N-1\right)
\sum_{n\ge 0}{a_{n+1}}2^{-mn}\qquad \text{(by E2)}\\
&\sim-\sum_{n\ge 0}{a_{n+1}}\sum_{m\ge 0}2^{-mn}
\left(e^{-N/2^{m+1}}-1\right)\\
&=-\sum_{n\ge 0}{a_{n+1}}\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}
                                            ^{-\frac 12+i\infty}
\Gamma(s)N^{-s}\frac{2^s}{1-2^{-n+s}}ds.
\endaligned
$$
The negative residues at $s=0$ and $s=\frac{2k\pi i}{\L}$ ($k\neq 0$)
give Flajolet's result:
From $n=0$ we obtain
$$
\log_2N+\frac{\gamma}{\L}-\frac 12 -\delta_0\left(\log_2N\right);
$$
from $n\ge 1$ we obtain
$$
\sum_{n\ge 1}a_{n+1}\frac{1}{1-2^{-n}}=-\alpha.
$$

\heading
5. Flajolet's analysis of the average path length in DSTs
\endheading

We want to go back from (K) to
$$
\CNK=\sum_{l\ge 1}l \cdot\pnlK\ ;
$$
this representation is of course not unique.
Let
$$
g(x)=\prod_{m=0}^{k-2}\left(1-\frac{x}{2^m}\right).
$$
Then
$$
g'(1)=\left\{
\alignedat2 
          &0& \quad &\text{for} \quad k=0\\
         -&Q_{k-2}&\qquad &\text{for} \quad k\ge 1.
\endalignedat
         \right.
$$
Furthermore, we have in general
$$
\sum_{l\ge 1}l\left[x^l\right]g(x)=g'(1), 
$$
where $\left[x^l\right]g(x)$ denotes the coefficient of $x^l$ in the
Taylor series expansion of $g(x)$. Thus
$$
\CNK=-\sum_{k=1}^N \binom Nk(-1)^k\sum_{l\ge 1}l\left[x^l\right]
\prod_{m=0}^{k-2}\left(1-\frac{x}{2^m}\right).
$$
By (E1) and (E2) we have
$$
\aligned
\prod_{m=0}^{k-2}\left(1-\frac{x}{2^m}\right)&=
\prod_{m\ge 0}\left(1-\frac{x}{2^m}\right)
\prod_{m\ge0}\left(1-\frac{x}{2^{m+k-1}}\right)^{-1}\\
&=\sum_{j\ge 0}\frac{(-1)^j2^{-\binom j2}x^j}{Q_j}
\sum_{s\ge 0} \frac{1}{Q_s}\left(2^{1-k}\right)^sx^s
\endaligned
$$
and thus
$$
\left[x^l\right]\prod_{m=0}^{k-2}\left(1-\frac{x}{2^m}\right)
=\sum_{j=0}^l \frac{(-1)^j2^{-\binom j2}}{Q_jQ_{l-j}}
2^{-(l-j)(k-1)}.
$$
So we can write
$$
\CNK=\sum_{l\ge 1} l\cdot\pnlK \ ,
$$
with
$$
\aligned
\pnlK&=-\sum_{k=1}^N\binom Nk (-1)^k
\sum_{j=0}^l \frac{(-1)^j2^{-\binom j2}}{Q_jQ_{l-j}}2^{-(l-j)(k-1)}\\
&=\sum_{j=0}^l \frac{(-1)^j2^{-\binom j2}}{Q_jQ_{l-j}}2^{l-j}
\left[1-\left(1-2^{-(l-j)}\right)^N\right].
\endaligned
$$
Flajolet would approximate $\pnlK/N$ by $\Psi\left(\frac{N}{2^l}\right)$,
with
$$
\Psi\left({x}\right)=\frac{1}{\qi}\sum_{j\ge 0}
\frac{(-1)^j2^{-\binom j2}}{Q_j}
\frac{1}{x2^j}\left(1-e^{-x2^j}\right).
$$
Now we perform the Mellin transform and find for $-1<\Re s<0$
$$
\left(\frac{1-e^{-x}}{x}\right)^*(s)=\int_{0}^\infty \left(1-e^{-x}\right)
x^{s-2} dx=-\Gamma(s-1).
$$
Therefore
$$
\Psi^*(s)=-\xi(s)\Gamma(s-1),
$$
where the function $\xi(s) $ was defined in Section 2.
Now
$$
\frac{\CNK}{N}\sim K(N)
$$
with
$$
K(x)= \sum_{l \ge 1}l\, \Psi\left(\frac{x}{2^l}\right).
$$
As before,
$$
K^*(s)=\frac{2^s}{(2^s-1)^2}\cdot\Psi^*(s).
$$
By Mellin's inversion theorem we have
$$
K(x)=-\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}^{-\frac 12+i\infty}
\frac{2^s}{(2^s-1)^2}\cdot
\xi(s)
\cdot
\Gamma(s-1)
\cdot
x^{-s} ds.
$$
The negative residue of the integrand at $s=0$ 
gives the contribution
$$
\log_2N-\frac 1{\log 2}+\frac{\gamma}{\log 2}-\alpha+\frac 12;
$$
the residues at $s=\frac{2k\pi i}{\L}$ produce the contribution
$\delta_{-1}\left(\log_2N\right)$.

\heading
6. An ``explanation'' of the similarities of the two problems
\endheading

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 {\it probability generating functions} for the path length in
digital search trees obey the following recursion 
($N\ge 1, \ F_1(z)=F_0(z)=1$)
$$
F_{N+1}(z)=z^N\sum_{k=0}^N2^{-N}\binom Nk 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, $\pnlF$
denote the probability that the counter has the value $l$ (``level $l$'')
after $N$
``inputs'', and
$$
F_N(z)=\sum_{l \ge 0}\pnlF\, 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$
{\it 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\ge 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\sum_{k=1}^N2^{-N}\binom Nk F_{k-1}(z)+z2^{-N}, 
\quad N\ge 1, \ F_0(z)=z.
$$
Now set, as usual, $C_N=F'_N(1)$. Then the recursion turns into
$$
C_N=1+2^{-N}\sum_{k=1}^N\binom NkC_{k-1},\quad N\ge 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}\sum_{k=0}^{N-1}\binom{N-1}kC_k, \quad N\ge 1, \ C_0=1.
$$
The standard method to solve this recursion is by the use of the
exponential generating function $C(z)=\sum_{N\ge 0}C_Nz^N/N!$. Then
$$
2C'(z)=C(z)+e^z+e^{z/2}C\big(\frac z2\big).
$$
Now one sets $D(z)=e^{-z}C(z)$ to obtain the easier equation
$$
2D'(z)=-D(z)+D\big(\frac z2\big)+1.
$$
Then we consider the coefficients:
$$
2D_{N+1}=-\left(1-2^{-N}\right)D_N, \quad N\ge 1, \ D_0=1,\ D_1=\frac 12.
$$
Iterating this we find
$$
D_N=2^{-N}(-1)^{N-1}Q_{N-1}, \quad N\ge 1, \ D_0=1. 
$$
Since $C(z)=e^zD(z)$, we have
$$
C_N=\sum_{k=0}^N\binom Nk D_k=1-\sum_{k=1}^N\binom Nk(-1)^k2^{-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.

\heading
7. Conclusion
\endheading

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 {\it had} to use Euler's formul\ae\  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 $\xi$--function); in Knuth's case it is the other way around. 

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








\Refs

\ref \no 1\by P.Flajolet \paper Approximate Counting: A Detailed Analysis
     \jour BIT \vol 25 \pages \linebreak 113--134 \yr 1985 \endref

\ref \no 2 \by P.Flajolet and J.Vitter \paper Average-Case Analysis of
     Algorithms and Data Structures \yr 1990 \pages 431--524
     \inbook Handbook of Theoretical
     Computer Science Vol. A ``Algorithms and
     Complexity''\publ North-Holland 
     \endref

\ref \no 3\by P.Kirschenhofer and H. Prodinger \paper Approximate Counting:
     An Alternative Approach \jour RAIRO Theoretical Informatics
     \yr 1991\vol 25 \pages 43--48  \endref

\ref \no 4 \by D.E.Knuth \book The Art of Computer Programming Vol. 3
     \publ Addison-Wesley \publaddr Reading MA \yr 1973 \endref


\endRefs

\enddocument



