\documentstyle[11pt]{article}
%\input{psfig}
\newtheorem{Proposition}{Proposition}
\newtheorem{Theorem}{Theorem}
\newtheorem{Lemma}{Lemma}
\newenvironment{pic}[1]%
{\input{#1}\begin{figure}\centerline{\box\graph}\vspace*{\bigskipamount}}%
{\end{figure}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\baselinestretch}{1.3}
\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newcommand{\con}{\rightarrow}
\newcommand{\cd}{\mbox{$\stackrel{d}{\rightarrow}$}}
\newcommand{\cp}{\mbox{$\stackrel{p}{\rightarrow}$}}
\newcommand{\ed}{\mbox{$ \ \stackrel{d}{=}$ \ }}
\newcommand{\ep}{\varepsilon}
\newcommand{\FF}{{\cal F}}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in}
\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\1{\hbox{\bf 1}}
\def\t{\tilde}
\def\half{{1\over 2}}
\def\med{\medskip\parsec}
\def\binom#1#2{{#1 \choose #2}}
\def\M{{\cal M}}
\def\n{\eta}
\def\th{\widetilde{h}}
\def\ss{\sigma}
\def\pr{\hbox{\rm Pr}}
\def\w{\omega}
\def\l{\ell}
\def\a{\alpha}
\def\b{{\bf b}}
\def\d{\delta}
\def\eps{\varepsilon}
\def\GG{\Gamma}
\def\w{\omega}
\def\wo{\omega'}
\def\TL{\widetilde{L}}
\def\Tl{\widetilde{l}}
\def\TW{\widetilde{W}}
\def\Tw{\widetilde{w}}
\def\TT{\widetilde{T}}
\def\Tt{\widetilde{t}}
\def\TR{\widetilde{R}}
\def\Tr{\widetilde{r}}
\def\TM{\widetilde{M}}
\def\Tm{\widetilde{m}}
\def\g{\widetilde{g}}
\def\TG{\widetilde{G}}
\def\TH{\widetilde{H}}
\def\TX{\widetilde{X}}
\def\TV{\widetilde{V}}
\def\var{\hbox{\rm Var~}}
\def\vphi{\varphi}
\def\sech{\text{sech}}
\def\R{R_{N,d}}
\def\U{{\cal U}}
\def\S{{\cal S}}
\def\D{{\cal D}}
\def\DH{\widehat{\D}}
\def\DO{\overline{\D}}
\vsize=8.5in
\voffset=-0.7in
\hoffset=-0.7in
\begin{document}
\begin{center}
{\bf ANALYSIS OF A SPLITTING PROCESS ARISING IN PROBABILISTIC COUNTING
AND OTHER RELATED ALGORITHMS
}\footnotemark
\footnotetext[1]{A preliminary version of parts
of this paper was presented in
{\it ICALP 92}, Vienna \cite{kps}. This work was supported by
NSF Grants INT-8912631 and CCR-9201078.}
\par
\medskip
\parsec
\today
\end{center}
\par
\bigskip\medskip
\begin{singlespace}
\noi
\begin{tabular}{lll}
Peter Kirschenhofer&Helmut Prodinger&Wojciech Szpankowski\footnotemark\\
Dept. Algebra\&Discrete Math.&Dept. Algebra\&Discrete Math.&Dept. Computer Science\\
Technical University of Vienna&Technical University of Vienna&Purdue University\\
A-1040 Vienna& A-1040 Vienna&W. Lafayette, IN 47907\\
Austria&Austria&U.S.A.\\
\end{tabular}
\footnotetext[2]{This author was additionally was supported by NSF Grants
NSF Grants NCR-9206315 and NCR-9415491,
and in part by NATO Collaborative Grant CRG.950060.}
\bigskip\bigskip
\begin{center}
{\bf Abstract}
\end{center}
\par
We present an analytical method of analyzing
a class of ``splitting algorithms'' that include probabilistic counting,
selecting the leader,
estimating the number of questions necessary to identify
distinct objects, searching algorithms based on digital tries,
approximate counting, and so forth. In our discussion we concentrate
on the analysis of a generalized probabilistic counting algorithm.
%which generalize the well-known ``probabilistic counting'' procedure
%due to Flajolet and Martin. Similar splitting processes occur in
Our technique belongs to the toolkit
of the analytical analysis of algorithms, and it involves solutions of
functional equations, analytical poissonization and depoissonization,
Mellin transform, etc.
In particular, we deal with a functional equation of the form
$g(z)=\beta a(z)g(z/2)+b(z)$ where $a(z)$ and $b(z)$ are given functions,
and $\beta<1$ is a constant.
With respect to our generalized probabilistic counting algorithm, we
obtain asymptotic expansions of the first two
moments of an estimate of the cardinality of a set
that is computed by the algorithm.
We also derive the {\it asymptotic} distribution of this
estimate, and observe that it actually fluctuates, leading to a conclusion
that its {\it limiting} distribution does not exist.
\end{singlespace}
\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}
\newpage
\parsec
{\bf 1. INTRODUCTION}
\par
\medskip
In several database algorithms a major determinant
of efficiency is the {\it cardinality} of the underlying set.
Therefore, one needs an efficient way of
estimating the cardinality of large (multi)sets of data. Clearly,
the trivial method of building a list of elements without replications
is unacceptable due to the cost of disk access and auxiliary memory.
Knowing this fact, Flajolet and Martin \cite{fm} proposed an algorithm
that is probabilistic in its nature. It works as follows: In order to
estimate the cardinality $N$ of a set $\M$ (with replications) every
element $x\in \M$ is hashed into a binary string of size $m$ (the choice
of $m$ is easy, and $m=5+\log N$ suffices \cite{bb}).
The bitwise OR-composition of
the modified hashed strings
in which only the least significant (rightmost) ``1'' survives
is used to build the so called {\tt bitmap} and to obtain
the estimate $R_N$ of the cardinality $N$ of $\M$. More precisely, the
position $R_N$ of the leftmost zero in the {\tt bitmap} string
(where we start enumerating positions with 0)
approximates $\log_2 N$ as shown by Flajolet and Martin in \cite{fm}
(cf. also \cite{bb}).
Observe that, equivalently, $R_N$ is the length of the longest run of
ones at the beginning of the bitmap string.
In fact, probabilistic counting is a special case of a {\it splitting
process} that also includes such algorithms as selecting the loser
\cite{ms,prodinger},
estimating the number of questions necessary to identify distinct
objects \cite{pittel}, searching algorithms based on digital tries
\cite{jr,js,js1,kps,knuth,rjs,spa2}, approximate counting \cite{kp2},
conflict resolution algorithms for multiaccess communication
\cite{js,usch,spa1} and so forth.
Using a digital tree representation one can describe
the probabilistic counting in terms of this
splitting process as follows:
Imagine $N$ persons flipping a fair coin, and those
who get $1$ (a hit) discontinue throwing
(move to the right in the digital tree representation) while the rest
continue throwing
(i.e., move to the left in the digital tree) until they get a hit.
The process continues until all remaining persons flip a 0. It should
be clear that the number of rounds in the flipping procedure equals
one plus the quantity $R_N$ from above.
Let us now consider the following {\em more general version\/} of the
splitting process, where the coin flipping ends as soon as at most $d$
persons have flipped a 1 in the same round, where $d$ is a given
parameter. This time we denote the number of rounds by $1+R_{N,d}$.
Observe that $d=0$ corresponds to the original situation. Again we
will expect $R_{N,d}$ to be an estimate of $\log_2N$.
We should point out that a similar extension of the primary
leader election algorithm was recently considered by Grabner \cite{grabner}.
Returning to the probabilistic counting algorithm:
We can interpret the generalized situation as follows:
We start from
an empty {\tt bitmap} string, that is, with all positions
filled by zeros. We further assume that $N$
different objects (e.g., data, persons, etc.)
can randomly insert (hit) a $1$ at any position of the {\tt bitmap}, however,
the probability of hitting the $j\geq 0$ position is equal to $2^{-j-1}$.
(In terms of the modified hashed strings discussed above
this means that the probability of
the occurrence of the pattern like $0^j1\cdots$ is equal to
$2^{-j-1}$ since $0$ and $1$ are equally likely.)
Every object can hit only
one time. We count the number of
hits in any position of the {\tt bitmap}, but we count the number of hits
only up to the value $d+1$, where $d$ is a given parameter. In other words,
the {\tt bitmap} is a $d+2$-ary string now. Clearly, the {\tt bitmap}
will contain many
$d+1$'s at the beginning of the string. This is due to the fact that
the probability of a hit decreases exponentially fast with
the increase
of the position in the {\tt bitmap}.
It is easy to see that
the length of the longest run of $d+1$'s in the front of the
{\tt bitmap} equals $R_{N,d}$ defined above.
More precisely, we have:
\begin{equation}
R_{N,d}= \min\{ k:~ {\tt bitmap}(k)0$. In the analysis
of the
algorithms introduced in this paper, we must
investigate among others the equation (\ref{e2}) with
$a(z)=1-e_d(z)e^{-z}$ where $e_d(z)=\sum_{i=0}^d z^i/i!$. Even more
complicated functions for $a(z)$ and $b(z)$ are involved in the
analysis of the variance and the
asymptotic distribution (cf. Sections 2 and 3).
As mentioned above, the case $d=0$
was analyzed by Flajolet and Martin \cite{fm}. In addition,
Greenberg {\it et al.} \cite{gfl}
investigated the instance $d=1$ in the analysis of
a conflict resolution algorithm for
multiple channels.
It must be stressed that the analysis of Flajolet and Martin
\cite{fm} is based on the inclusion-exclusion rule, and seems to
be very unlikely extendable to $d\geq 1$. This is partially
evident from the analysis in \cite{gfl}.
The plan for the present paper is as follows: In the next section we
present our main results concerning the
generalized counting algorithm and the associated splitting process,
and their algorithmic consequences. The
proofs are delayed till Section 3 where -- besides of
proving our findings --
we also present a general
methodology of dealing with functional equations like (\ref{e2}).
In particular, we use a {\it depoissonization lemma} that allows us
to obtain an estimate of a sequence from
its exponential generating function. This approach turned to be very
useful in many other situations encountered in the analysis of
algorithms (cf. \cite{ms,frs,js,rj,rjs}).
\big
{\bf 2. MAIN RESULTS}
\par
\medskip
Let $F_N(u)=Eu^{R_{N,d}}$ be the probability generating function
of the estimator $R_{N,d}$.
That is, $[u^j]F_N(u)$ (the $j$th coefficient
at $F_N(u)$) is the probability that either
the splitting process terminates after $j+1$ rounds or that the
result of the {\tt bitmap} is
$(d+1)^jc\ldots$ where $c\le d$, and $(d+1)^j$ denotes $j$
consecutive values ``$d+1$''.
To derive the recurrence for $F_N(u)$ we observe:
%we recall the definition of the splitting process from Section 1.
If at the first step $k$ persons flip $1$, then either the contribution to
the generating function $F_N(u)$ is
$u^0 \sum_{k\leq d} {N\choose k} 2^{-N}$ for $k\leq d$,
or the contribution becomes $u\sum_{d+1\leq k\leq N} {N\choose k} 2^{-N}
F_{N-k}(u)$ for $k> d$. In short, we obtain the following recurrence
\begin{equation}
F_N(u)=\sum_{k=0}^d {N\choose k} 2^{-N} + u \sum_{k=0}^{N-d-1}{N\choose k}
2^{-N} F_k(u) ~,
\label{e3}
\end{equation}
which is valid for all $N\geq 0$.
\par
Using (\ref{e3}) we can derive recurrences for the first and second
factorial moments
of $R_{N,d}$, namely: $ER_{N,d}=F_N^\prime(1)$ and
$F_N^{\prime\prime}(1)$.
Observe that $\var R_{N,d}=F_N^{\prime\prime}(1)
+F_N^\prime(1)-(F_N^\prime(1))^2$.
In particular, let $L(z)$ and $W(z)$ be the exponential generating
function for $F_N^\prime(1)$ and $F_N^{\prime\prime}(1)$, respectively.
That is,
\begin{eqnarray*}
L(z)&=& \sum_{N\geq 0} F_N^\prime(1) z^N/N! ~,\\
W(z)&=& \sum_{N\geq 0} F_N^{\prime\prime}(1) z^N/N! ~.
\end{eqnarray*}
Define also
$\TL(z)=e^{-z}L(z)$ and $\TW(z)=e^{-z}W(z)$ as the
{\em Poisson generating functions}.
These Poisson generating functions represent the first two moments
in a variation of the probabilistic counting problem in which the
number of people (objects) is not fixed but is a random variable
distributed according to a Poisson process with mean $z$.
Then, after some algebra (\ref{e3}) implies
\begin{equation}
\TL(z)=f_d(z/2)\TL(z/2)+f_d(z/2)~,
\label{e4}
\end{equation}
\begin{equation}
\TW(z)=f_d(z/2)\TW(z/2)+2\TL(z)f_d(z/2)
\label{e5}
\end{equation}
where
\begin{equation}
f_d(z)=1-e_d(z)e^{-z}\qquad\hbox{and}\qquad
e_d(z)=1+{z^1\over 1!} + \cdots +{z^d\over d!} ~.
\label{e51}
\end{equation}
The above functional equations are solved
in the next section (cf. Section 3.1). Their solutions are expressed in
terms of the following function that is needed to articulate our
main results below:
\begin{equation}
\vphi(x) =\prod_{j=0}^\infty f_d(x2^j)=
\prod_{j=0}^\infty \left(1-e_d(x2^j)e^{-x2^j}\right)~.
\label{vp}
\end{equation}
We now can present
our first main result which is proved in Section 3.2.
\med
{\bf Theorem 1}. {\it Consider the generalized splitting
algorithms described above. Then the estimator $R_{N,d}$
behaves as follows:
\med
{\rm (i)} The average value of $R_{N,d}$ becomes asymptotically as
$N\con \infty$\quad
%(fixed $d$)
\begin{equation}
ER_{N,d} = \log_2 N -1 -C_d +P_1(\log_2N) +
O\left({N}^{-1/2+\eps}\right)
\label{e10}
\end{equation}
for any $\eps>0$ with
\begin{eqnarray}
C_d&=&{1\over L^2} \int_0^\infty e^{-x}e_d(x)\varphi(2x)
\frac{\log x}{x} dx \nonumber \\
&=& \log_2 d -\frac12 +O\left(\frac1d\right) \ \ \ \ \ \ {\rm as} \ \ \
d\con \infty
\label{e11}
\end{eqnarray}
where $L=\log2$ and the function $\vphi(x)$ is defined in (\ref{vp}).
Furthermore, with $\chi_k=2k\pi i/L$,
\begin{equation}
P_1(x)= -{1\over L^2} \sum_{k\ne 0}
\Phi^{*\prime}(-\chi_k) e^{2\pi i k x}
\label{e111}
\end{equation}
where $\Phi^*(s)$ is the Mellin transform of $\vphi(2x)-\vphi(x)$
and $\Phi^{*\prime}(s)$ is the first derivative of $\Phi(s)$
(cf. Section 3 for details). In particular, $P_1(x)$
is a periodic function of mean zero and small amplitude
for reasonable values of $d$.
\med
{\rm (ii)} The variance of $R_{N,d}$ is
\begin{equation}
\var R_{N,d} = D_d -C_d^2 -{[P_1^2]}_0+P_2(\log_2N) +
O\left({N}^{-1/2+\eps}\right)
\label{v1x}
\end{equation}
for any $\eps>0$, where
\begin{equation}
D_d -C_d^2-\left[P_1^2\right]_0=\frac{1}{\sqrt{\pi d}}
+O\left(\frac 1d\right) \ \ \ {\rm for} \ \ \ \ \ \
d\to \infty ~.
\label{v1}
\end{equation}
More precisely
\begin{eqnarray}
D_d&=&{1\over L^3} \int_0^\infty e_d(x)e^{-x}\varphi(2x){\log^2 x \over x} dx
\nonumber \\
&=& -C_d -1/6 +\log_2^2d +O\left({1\over d}\right) \ \ \ \
\hbox{ {\rm as} } \ \ \
d\con \infty ~,
\label{e13}
\end{eqnarray}
so that
\begin{eqnarray}
D_d -C_d^2= {1\over 12} + O\left(\frac1d\right)
\ \ \ \ \ \ {\rm as} \ \ \
d\con \infty~.
\label{e12}
\end{eqnarray}
The quantity ${[P^2_1]}_0$ is the (integral) mean of the square of $P_1(x)$,
and for large $d$ behaves as
\begin{eqnarray}
{[P_1^2]}_0=\frac{1}{12}-\frac{1}{\sqrt{\pi d}}+O\left(\frac 1d\right)
\ \ \ \ \ \ \hbox{as} \ \ \
d\con \infty ~.
\end{eqnarray}
Finally, $P_2(x)$ is a periodic function with
period 1 and small amplitude.}
\par
\bigskip
Using numerical integration, we computed for some values
of $d$ the constant terms (for $N\to\infty$)
in
$ER_{N,d}-\log_2N-P_1(\log_2N)$ and
$\var R_{N,d} -P_2(\log_2N)$. They are displayed in
Table 1. We note that the variance initially rapidly decreases
(for $d\leq 2$) and then the decrease slows down.
As an immediate consequence of
Theorem 1, we observe
that $R_{N,d}$ converges {\it in probability} (pr.) to
$ER_{N,d}$. Indeed, by Chebyshev's
inequality we have
$$
\pr\{| R_{N,d}/ER_{N,d} -1|>\eps \} \leq {\var R_{N,d} \over
\eps^2 E^2 R_{N,d}} = O\left({1\over \log^2N}\right) \con 0$$
as $N\con \infty$. This proves the announced convergence, but
does not warrant the almost sure (a.s.) convergence since
the {\it Borel-Cantelli Lemma} cannot be applied. However, observe that
$\R$ is a nondecreasing function of $N$, in the sense that
on every sample path we have
$R_{N+1,d}\geq \R$. To prove the (a.s.) convergence
one should apply the Borel-Cantelli Lemma along a doubly exponentially
increasing sequence such as $N=2^{2^k}$ (cf. \cite{kingman}), thus
$\R\to E\R$ (a.s.), too.
\par
Our technique also allows to deal with the asymptotic distribution for $R_{N,d}$
and the limiting generating function. For this, we introduce
the Poisson transform of $F_N(z)$ as
\begin{equation}
\TG(z,u)= e^{-z} \sum_{N=0}^\infty F_N(u){z^N\over N!} ~.
\label{e14}
\end{equation}
Observe that $\TG(z,u)$ can be interpreted as the generating function
of $\R$ when the cardinality of a set is Poisson distributed
with mean $z$.
\begin{table}
\caption{Performance of the algorithm for small values of $d$
(neglecting fluctuations of mean zero).}
\med
\begin{center}
\begin{tabular}{|c||c|c|} \hline
d&$ER_{N,d}-\log_2N$&$\var~ R_{N,d}$ \\ \hline\hline
0&-0.37&1.26\\ \hline
1&-1.40&0.78\\ \hline
2&-2.00&0.59\\ \hline
3&-2.42&0.49\\ \hline
4&-2.74&0.43\\ \hline
5&-3.02&0.38\\ \hline
6&-3.24&0.35\\ \hline
7&-3.43&0.32\\ \hline
\end{tabular}
\end{center}
\end{table}
The Poisson generating function $\TG(z,u)$ satisfies the following
functional equation
\begin{equation}
\TG(z,u)=uf_d(z/2)\TG(z/2,u)+(u-1)(f_d(z/2)-1) ~.
\label{e15}
\end{equation}
Using the technique from Section 3.1, we can solve it
for $z\to \infty$, and then by depoissonization (that is, after
recovering $F_N(u)$
from $\TG(z,u)$) we prove in Section 3.3 our second main finding.
%\begin{equation}
%H(z,u)=uf_d(z/2)H(z/2,u)+(u-1)f_d(z/2) ~.
%\label{e15}
%\end{equation}
\med
{\bf Theorem 2}. {\it Let $t$ be a fixed real number. Then, for
large $N$ the asymptotic distribution of $\R$ becomes
for $N\to\infty$\ ($d$ fixed)
\begin{equation}
\pr\{\R \leq \log_2N +t-1\} = 1-
\vphi\left(2^{-t-\{\log_2N+t\}}\right) + O(N^{-1/2+\eps}) ~,
\label{e151}
\end{equation}
for any $\eps>0$,
where
$\vphi(x)$ is defined in (\ref{vp}), and
$\{\log_2N+t\}=\log_2 N+t -\lfloor \log_2 N +t \rfloor$. Since
$\{\log_2N+t\}$ is dense in $[0,1]$ but not uniformly distributed in $[0,1]$
the limiting distribution of $\R$ does not exist. In fact,
\begin{eqnarray}
\liminf_{N\to \infty} \pr\{\R \leq \log_2N +t-1\} &=&
1-\vphi\left(2^{-t-1}\right) \label{e153}\\
\limsup_{N\to \infty} \pr\{\R \leq \log_2N +t-1\} &=&
1-\vphi\left(2^{-t}\right) \label{e154}
\end{eqnarray}
for real $t$ and all $d\geq 0$}.
\med
{\bf Remark.} With a more involved proof, using the {\em
complex Mellin transform}
%(compare 3.2)
it can be shown that the remainder term in (\ref{e151}) is
$ O(N^{-1/2})$, and the error terms in (\ref{e10}) resp. (\ref{v1x})
are $O(\log N/N)$ resp. $O(\log^2 N/N)$.
$\Box$
\par
\medskip
The nonexistence of the limiting distribution could be expected.
Observe that the estimate $R_{N,d}$ is related to an
extreme statistics of a set of $N$ discrete random variables
(in fact, geometrically distributed). Anderson \cite{anderson}
in 1970 predicted such a behavior for $M_n=\max\{X_1,\ldots , X_N\}$
where $X_i$ are i.i.d. discrete random variables. In fact, when
$X_i$ are geometrically distributed with parameter $1/2$, then
the asymptotic distribution of $M_n-\log_2 N$ oscillates between
two {\it double exponential} distributions, namely $e^{-2^{-t-1}}$ and
$e^{-2^{-t}}$. The bounds (\ref{e153}) and (\ref{e154}) resemble
the double exponential distribution. Indeed, consider $d=0$, and take
only the first two terms of the infinite product $\vphi(2^{-t})$. Then,
$\vphi(2^{-t}) \approx \sum_{j\geq 0} e^{-2^{-t+j}}$.
This is illustrated in Figure 1
where we show the upper
``envelope'' for the asymptotic distribution of $R_{N,d}-\log_2 N$ (i.e.,
$1-\vphi(2^{-t})$) for $d=0$ and $d=3$). In passing, we should
point out that recently Fill {\it et. al.} \cite{ms} used the
depoissonization technique to obtain a similar oscillation in
the height of the incomplete trie.
A thorough account on analytical depoissonization
can be found in Jacquet and Szpankowski \cite{js2}.
%\begin{figure}
%\centerline{\psfig{file=fig1.epsi,angle=-90,height=3in,width=5in}}
%\caption{The upper ``envelope'' for the ``shifted'' asymptotic distribution
%$1-\vphi(2^{-t})$ for $d=0$ and $d=3$.}
%\end{figure}
%
Our technique might be applied to analyze several other algorithms
that are based on the ``splitting process" described at the
beginning of this section. More precisely, a splitting algorithm
divides randomly $N$ objects according to some rule.
For example, consider a multiaccess system with a large number
of users. The following ``conflict resolution" algorithm found to be
successful for some multiaccess systems (cf. \cite{gfl},
\cite{js}). Let $N$
be the size of a conflict, that is, the number of users that
simultaneously sent packets. To split it, every user
flips a fair coin, and those who get $1$ ``move
right" in a digital tree represented this process,
while the others ``move left". This
splitting process continues until all users sent successfully
their packets (i.e., subtrees containing
conflicting users are of size one). This algorithm can be analyzed
in a unified manner by our approach through the functional
equation of type (\ref{e6}).
Here is another example that generalizes PATRICIA tries
(cf. \cite{knuth}, \cite{spa2}).
Consider $N$ infinite strings that are built over a $V$-ary
alphabet. Using a trie construction as in Knuth \cite{knuth}
(see also \cite{spa2}) we can split all strings in such a manner
that no two of them will share the common prefix. A trie
built in such a manner may contain some internal nodes that
are unary. To avoid such a waste of storage, one may
compress this trie to obtain a PATRICIA trie. In the PATRICIA
all internal nodes have degree greater or equal to two.
But a generalization of a PATRICIA trie might be also explored by
imposing that all internal nodes have degree of size greater or
equal to $d\leq V$. What is the search time (i.e., the
length of a path to an external node) in such a trie?
What about the average height, etc.? The analysis of such
a data structure seems to be a nontrivial task, and our approach
can be applied to solve some of these problems.
\big
{\bf 3. ANALYSIS}
\par
\medskip
In this section we present the proof of Theorem 1 (cf. Section 3.2)
and Theorem 2 (cf. Section 3.3). To streamline our analysis, in
Section 3.1 we discuss a general solution of a functional equation
that arises on many occasions in this paper (cf. (\ref{e2})), and in general
in the analysis of algorithms (cf.
\cite{bb,ms,fs,fla,gfl,kp1,kp2,kp3,knuth,prodinger,rjs,rj,usch,spa1,spa2,sr}).
In addition,
we offer a unified approach to depoissonization: a technique that
allows to analyze the Poisson model instead of the more difficult Bernoulli
model (i.e., when the number of objects is fixed). Poissonization
is a standard probabilistic technique (cf. Aldous \cite{aldous}),
however, depoissonization
causes usually some problems. We cope with it in Section 3.1 where
we present an analytical approach to the depoissonization
(cf. also \cite{ms,js,js1,js2,rjs,rj}).
\med
{\bf 3.1 General Solution and Depoissonization}
\par
\medskip
The functional equations (\ref{e4}) and (\ref{e5}) for the Poisson
generating functions of $\TL(z)$ and $\TW(z)$, as well as (\ref{e15})
on $\TG(z,u)$ satisfy the following general functional equation
\begin{equation}
\widetilde{g}(z,u)=\beta a(z/2,u)\widetilde{g}(z/2,u) +b(z,u) ~,
\label{e6}
\end{equation}
%[{\Large\bf Wojtek: Shouldn't we replace $\beta$ by $\beta(u)$ to
%cover (\ref{e15})?? }]
where $|\beta|\leq 1$, and $u$ is either fixed (cf. (\ref{e4}) and (\ref{e5}))
and in this case we simplify the notation to $\widetilde{g}(z)$, or $u$ belongs
to a compact neighborhood $\U(u_0)$ of $u_0$ (cf. in (\ref{e15}) we have
$u_0=0$). The factor $\beta$ may depend on $u$.
Iterating (\ref{e6}), we obtain a general solution
in the form of (cf. \cite{js,spa1})
\begin{equation}
\widetilde{g}(z,u)=\sum_{n=0}^\infty \beta^nb(z2^{-n},u) \prod_{k=1}^n a(z2^{-k},u)
\label{e7}
\end{equation}
if $\widetilde{g}(0,u)=0$. Define
\begin{equation}
\varphi(z,u)=\prod_{j=0}^\infty a(z2^j,u) ~,
\label{e8}
\end{equation}
provided the infinite product in (\ref{e8}) converges.
Then, the general
solution (\ref{e7}) can be rewritten as
\begin{equation}
\widetilde{g}(z,u)=
\sum_{n=0}^\infty \beta^n b(z2^{-n},u) \prod_{j=0}^{n-1}\varphi(z2^{-j},u) ~.
\label{e91}
\end{equation}
or even more conveniently as
\begin{equation}
\widetilde{g}(z,u)\varphi(z,u)
=\sum_{n=0}^\infty \beta^n b(z2^{-n},u) \varphi(z2^{-n},u) ~.
\label{e9}
\end{equation}
The last form is the clue to our
asymptotic solution of the functional
equation (\ref{e7}), and in particular to solve (\ref{e4}), (\ref{e5})
and (\ref{e15}). This is due to the fact that the sum in (\ref{e9}) falls
under the so called {\it harmonic sum} that can be easily handled by
the Mellin transform technique (cf. \cite{frs,usch}):
Using the Mellin transform
we obtain
the asymptotic behavior of the above function for $z\to \infty$, and then
we ``depoissonize'' it to recover the original sequence.
In view of this, the important part of our analysis relies on
depoissonization that we discuss next. To assure enough generality,
let $g_N(k)$ be a double
sequence of $N\geq 0$ and $k\geq 0$ (e.g., $g_{N}(k)=\pr\{\R=k\}$).
Define $g_N(u)=\sum_{k\geq 0}
u^k g_N(k)$, the exponential generating function $g(z,u)=
\sum_{N\geq 0} g_N(u)z^N/N!$, and the Poisson generating
function $\g(z,u)=e^{-z}g(z,u)$.
When the sequence depends only
on $N$ (e.g., $g_N=ER_{N,d}$), we write $\g(z)=e^{-z}\sum_{N\geq 0} g_N z^N/N!$.
On several instances the Poisson generating function $\g(z,u)$
(or $\g(z)$) is easier to handle, and one can obtain the asymptotic
behavior of $\g(z,u)$ for $z\to \infty$. The question is how to
recover $g_N(u)$ (or $g_N$). This reverse process is
called {\it depoissonization}, and the lemma below
was proved
in Rais {\it et. al.} \cite{rjs} (cf. also \cite{jr,js1,rj}).
\med
{\bf Depoissonization Lemma}.
%(i)
{\it Let $\S_\theta$ be a cone
$\S_\theta=\{z:~ |{\rm arg} z| < \theta~,~ 0<\theta<\pi/2\}$.
As $z\con \infty$ the following two conditions are assumed to hold for all
$u$ in a compact set $\cal U$:\\
(I) For $z\in \S_\theta$
\begin{equation}
\g(z,u)=O(|z|^\varepsilon)
\label{e22}
\end{equation}
for some $\varepsilon>0$;\\
(O) For $z\not\in \S_\theta$
\begin{equation}
\g(z,u)e^z=O( e^{\alpha |z|})
\label{e227}
\end{equation}
for some $\alpha <1$.
Then for large $N$
uniformly in $u\in \cal U$ the generating function $g_N(u)
=[z^N/N!]\g(z,u)e^z$ satisfies}
\begin{equation}
g_N(u)=\g(N,u)+O(N^{-1/2+\varepsilon})~.
\label{e24}
\end{equation}
%In particular, condition (I) is automatically satisfied if
%for $z\in \S_\theta$
%\begin{equation}
%\g(z)=O(z^p\log^q z)
%\label{p1}
%\end{equation}
%%[{\Large\bf Wojtek: Is no remainder term needed here to get (\ref{p2})??}]
%for some constants $p$ and $q$.
%% and the hypothesis (\ref{e227}) of (i) for $z\notin \S_\theta$ holds, then
%\begin{equation}
%g_N = \g(N) \left(1+O(1/\sqrt{N})\right)
%\label{p2}
%\end{equation}
%\med
%{\rm (ii)} If $\TX(z)$ and $\TV(z)$ are the mean and the variance of a
%random variable $X_N$ in the Poisson model, then under the assumptions
%of (ii) the mean $EX_N$ and
%the variance $\var X_N$ in the corresponding Bernoulli model
%become
%\begin{eqnarray}
%EX_N&\sim& \TX(N)(1-O(1/N))-\frac{1}{2} N \TX''(N) \label{dep1} ~, \\
%\var X_N & \sim & \TV(N)(1-O(1/N)) - n[\TX'(N)]^2
%\label{dep2}
%\end{eqnarray}
%where $\TX'(N)$ and $\TX''(N)$ are the first and the second derivatives of
%$\TX(z)$ at $z=N$}.
\med
{\bf Remark} (i) The error term in (\ref{e24}) depends only on the bounds
on $\g(z,u)$ (cf. (\ref{e22}) and (\ref{e227})) and does not depend directly
on the function $\g(z,u)$ itself.
\med
(ii) A more careful analysis reveals that the error term in
(\ref{e24}) is $O(N^{-1+\eps})$ (cf. \cite{js2}).
$\Box$
\par
\medskip
Using the Depoissonization Lemma, we can ``depoissonize''
functional equation (\ref{e6}),
and prove the following general result.
\med
{\bf Theorem 3}. {\it Consider the functional equation (\ref{e6}) for
$u$ in a compact set $\U$ such that $\g(z,u)$ is bounded in $\U$.
Choose large $B>0$ such that for $|z|>B$ and any constants $\beta_1, \beta_2,
\delta,\delta_1>0$
the following conditions
hold:\\
(I) or $z\in \S_\theta$
\begin{equation}
{|\beta a(z/2,u)| \over 2^\eps} < 1-\delta \ \ \ \ , \ \ \ \ \
|b(z,u)|<\beta_1 \delta |z|^\eps ~;
\label{p3}
\end{equation}
(O) for $z\notin \S_\theta$
\begin{equation}
{|\beta a(z/2,u)e^{z/2}| } < (1-\delta_1) e^{\a |{z/2}|} \ \ \ \ , \ \ \ \ \
|b(z,u)e^z|<\beta_2 \delta_1 e^{\a |z|} ~,
\label{p4}
\end{equation}
for $\a<1$. Then, q
\begin{equation}
g_N(u)=\g(N,u)+O(N^{-1/2+\eps})
\label{p5}
\end{equation}
for $u\in\U$}. % provided $\eps<1/2$}.
\med
{\bf Proof}. It suffices to prove that under (\ref{p3}) and (\ref{p4}) the
two conditions (\ref{e22}) and (\ref{e227}) of the Depoissonization
Lemma hold.
The proof is by induction along the so called {\it increasing domains}
as used in \cite{jr} and defined precisely in \cite{js1}:
Suppose $1<\lambda <2$ is a given real number, and then define increasing
domains $\D_m$ for $m=0,1,\ldots$ as
$$
\D_m = \{z:\ B \le |z| < B\lambda^{m+1}\} ~.
$$
Note that if $z\in \D_{m+1} - \D_m$, then $z/2 \in \D_m$, for
$m=0,1,\ldots\ $. Thus, we can apply induction
with respect to $m$.
We first show that (\ref{e22}) holds provided inequalities
(\ref{p3}) are fulfilled for $z\in \S_\theta$. Define $\DH=\D_m\cap \S_\theta$.
Clearly (\ref{e22}) holds in $\DH_0$ as long as a solution
of the functional equation is bounded in a compact set. Let us now assume that
condition (\ref{e22}) is satisfied in $\DH_m$, and we prove that it
also holds in $\DH_{m+1}$.
If $z\in \DH_m$, then we are done. If $z\in \DH_{m+1}-\DH_m$, then
$z/2\in \DH_m$, and we can apply induction hypothesis, that is,
$|g(z/2,u)|\leq \beta_1 |z|^\eps/2^\eps$ for large $z\in \S_\theta$.
Then, from the induction hypothesis, inequalities (\ref{p3}),
and equation (\ref{e6}) we have
$$
|\g(z,u)| \leq \beta_1(1-\delta) |z|^\eps +\beta_1\delta |z|^\eps=
\beta_1 |z|^\eps ~.
$$
Thus, (\ref{e22}) holds in the larger domain $\D_{m+1}$,
and by induction, in the whole cone $\S_\theta$.
In a similar manner we prove that the second set of inequalities (\ref{p4})
imply (\ref{e227})
by noting that $|e^z|=e^{\Re(z)} \leq e^{\a |z|}$ where $\a=\cos\theta<1$.
This time we use domains $\DO_m=\D_m\cap \overline{\S}_\theta$
where $\overline{\S}_\theta$ is the complimentary set to $\S_\theta$.
The rest follows the same line of arguments as above.
This completes the proof of Theorem 3. \eod
\med
{\bf 3.2 Analysis of Moments}
\par
\medskip
We now prove Theorem 1. We consider two cases: bounded $d$, and
large $d$ ($d\to \infty$).
\med
{\sc Case A: Bounded $d$}
\par
\medskip
We start with the average value $ER_{N,d}$.
Its Poisson
generating function $\TL(z)$ satisfied the functional equation (\ref{e4})
which we repeat below
\begin{equation}
\TL(z)=f_d(z/2)\TL(z/2)+f_d(z/2)
\label{e19}
\end{equation}
where $f_d(z)=1-e_d(z)e^{-z}$ and $e_d(z)=1+z^1/1!+\cdots +z^d/d!$.
This equation falls under the general functional equation (\ref{e6}),
thus by (\ref{e9}) we have
\begin{equation}
\TL(z)\varphi(z)=\sum_{n=0}^\infty \varphi(z2^{-n-1}) ~,
\label{e20}
\end{equation}
where
\begin{equation}
\varphi(z)=\prod_{j=0}^\infty f_d(z2^j)=\prod_{j=0}^\infty
\left(1-e_d(z2^j)e^{-z2^j}\right) ~.
\label{e21}
\end{equation}
%or, equivalently,
%$$
%\TL(z)=\sum_{n=0}^\infty\prod_{j=1}^{n+1} f_d \left(z2^{-j}\right).
%$$
Observe that, by d'Alembert's criterion, the final expression converges
absolutely for all complex numbers $z$.
The idea of our analysis is to obtain
the asymptotic behavior of $\TL(z)$
as $z\con \infty$, and then
to apply
depoissonization.
To obtain the asymptotics of $\TL(z)$ we make use of the Mellin transform
technique. The Mellin approach is by now a standard technique
in the analysis of algorithms. The interested reader can find more on
Mellin transform in a recent survey \cite{frs} (cf. also \cite{usch}).
For the reader's convenience, however, we provide below some properties
of the transform that we shall use in our analysis.
The following properties are used in this paper:
\begin{itemize}
\item[(P1)] {\sc Definition and Inverse of the Real Mellin Transform}
\begin{equation}
f^*(s)=\int_0^\infty f(x)x^{s-1}dx \ \ \ \ \ , \ \ \ \ \
f(x)={1\over 2\pi i} \int_{c-i \infty}^{c+i\infty} f^*(s) x^{-s} ds
\label{m1}
\end{equation}
where $c$ belongs to the {\it fundamental strip} defined below.
\item[(P2)] {\sc Fundamental Strip}\\
The Mellin transform of $f(x)$ exists in the {\it fundamental strip}
$\Re(s)\in <-\alpha, -\beta>$ where
$$
f(x)=\left\{ \begin{array}{ll}
O(x^\a) & \mbox{~ ~ ~ $x\to 0$} \\
O(x^\beta) & \mbox{~ ~ ~ $x\to \infty$}~.
\end{array}
\right.
$$
\item[(P3)] {\sc Harmonic sum}
\begin{equation}
f(x)=\sum_{k\geq 0} \lambda_k g(\mu_k x) \ \ \ \ \Leftrightarrow \ \ \ \ \
f^*(s)=g^*(s)\sum_{k\geq 0} \lambda_k \mu_k^{-s}
\label{m2}
\end{equation}
provided the above sum converges. In the above, we used the following
property
\begin{equation}
f(x)=g(ax) \ \ \ \ \Leftrightarrow \ \ \ \ \ f^*(s)=a^{-s}g^*(s)
\label{m3}
\end{equation}
in the fundamental strip of $f^*(s)$.
\item[(P4)] {\sc Asymptotic Expansion} \\
If $f^*(s)$ satisfies certain smallness-conditions towards $i\infty$
(cf. \cite{frs})
for $-\beta < \Re(s) \leq M$, ($M>0$) and
\begin{equation}
f^*(s) = \sum_{k=0}^K {d_k \over (s-b)^{k+1}} ~,
\label{m4}
\end{equation}
then as $x\to \infty$
\begin{equation}
f(x) = \sum_{k=0}^K {d_k \over k!} x^{-b} (-\log x)^k +O(x^{-M}) ~.
\label{m5}
\end{equation}
\item[(P5)] {\sc Mellin Transform in Complex Plane}
(cf. \cite{davies, doetsch, FJnote}) \\
If $F(z)$ is analytic in a cone $\theta_1\le \arg(z)\le \theta_2$
with $\theta_1<0<\theta_2$, then the Mellin transform $F^*(s)$ can be defined
by replacing the path of integration $[0,\infty[$ by any curve starting at
$z=0$ and going to $\infty$ inside the cone, and it is identical with the
real transform $f^*(s)$ of $f(z)=F(z)\Big|_{z\in R}$ from (\ref{m1}).
In particular, if $f^*(s)$ fulfills an asymptotic expansion (\ref{m4}),
then (\ref{m5}) holds for $F(z)$ as $z\con\infty$ in the cone.
\end{itemize}
Now we are ready to solve asymptotically (\ref{e20}) since we recognize
it as a harmonic sum. Let $Q_1(z)=\TL(z)\varphi(z)$ and $Q_1^*(s)$ be
its Mellin transform which due to (P2) exists in the strip $\Re(s)\in(-\infty,0)$.
By the harmonic sum formula (P3) we have $Q_1(s)=2^s/(1-2^s) \vphi^*(s)$
where the Mellin $\vphi^*(s)$ of $\vphi(x)$ exists in
$\Re(s)\in(-\infty,0)$. There is a problem, however, since the Mellin transform
of
$\vphi(s)$ does not exists at $s=0$, and we need a more precise estimate
of $\vphi^*(s)$ at $s=0$.
Thus, we proceed as follows. Define
\begin{equation}
\Phi(x)=\vphi(2x)-\vphi(x)=e_d(x)e^{-x} \vphi(2x) ~.
\label{e251}
\end{equation}
Observe now that the Mellin transform
of $\Phi(x)$ exists in $(-\infty, \infty)$,
and by (\ref{m3}) we finally obtain
\begin{equation}
Q_1^*(s)={2^s\over 1-2^s} \varphi^*(s)=\left({2^s\over 1-2^s}\right)^2
\Phi^*(s) ~,
\label{e25}
\end{equation}
where $\Phi^*(s)$ is an entire function, as we noticed above, and defined as
\begin{equation}
\Phi^*(s)=\int_0^\infty e_d(x) e^{-x} \vphi(2x) x^{s-1} dx ~.
\label{e252}
\end{equation}
To assess asymptotically $\TL(z)$ we use property (P4) of the
Mellin transform, that is, we must estimate residues
of (\ref{e25}). Note that $\chi_k=2\pi i k/L$ ($k=0,\pm 1, \pm 2, \ldots$)
are the solutions of $1-2^{-s}=0$, and the main contribution to the
asymptotics comes from $\chi_0=0$. Since
$\varphi(z)\sim 1+O(z^{-M})$ for any $M>0$,
we obtain,
%\footnote{Since an explicit formula for $\varphi^*(s)$ is not
%known, we must use singularity analysis of Flajolet and
%Odlyzko \or some Tauberian theorems. Details
%are left for a journal version of this paper.}
for $z\con \infty$
\begin{equation}
\TL(z) = \log_2 z \cdot {\Phi^*(0) \over L} -{\Phi^*(0) \over L}-
{\Phi^{*\prime}(0) \over L^2} +P_1(\log_2z) +O(z^{-M})
\label {26}
\end{equation}
where
\begin{eqnarray}
\Phi^*(0)&=&\int_0^\infty e^{-x}e_d(x)\varphi(2x){dx\over x} ~, \label{e261}\\
\Phi^{*\prime}(0)&=& \int_0^\infty e^{-x}e_d(x)\varphi(2x){\log x\over x} dx ~,
\label{e262}
\end{eqnarray}
and
\begin{equation}
P_1(x)=\sum_{k\ne 0}\left(\frac{\Phi^*(-\chi_k)(x-1)}{L}-
\frac{\Phi^{*\prime}(-\chi_k)}{L^2}\right)e^{2k\pi ix}~.
\end{equation}
To complete the proof,
we need to evaluate $\Phi^*(0)$,$\Phi^*(\chi_k)$,
$\Phi^{*\prime}(0)$, and $\Phi^{*\prime}(\chi_k)$.
The first one is rather easy, and by properties of the Mellin transform
we find out that $\Phi^*(0)=L=\log 2$. The derivatives
are harder to estimate.
In order to treat the other constants,
we first present another evaluation
of $\Phi^*(0)$.
Define the function $\1(x)$ as follows
\begin{equation}
\1(x)=\left\{\begin{array}{ll}
1& \mbox{if $x\geq 1$} \\
0&\mbox{if $x<1$} ~.
\end{array}
\right.
\end{equation}
Then, we can write
\begin{eqnarray}
\Phi^*(0)&=&\int_0^\infty (\varphi(2x)-\varphi(x)){dx\over x} \nonumber \\
&=&\int_0^\infty (\varphi(2x)-\1(2x)){dx\over x}+
\int_0^\infty (\1(2x)-\1(x)){dx\over x}+
\int_0^\infty (\1(x)-\varphi(x)){dx\over x} \\
&=&\int_0^\infty (\1(2x)-\1(x)){dx\over x} =\int_{1/2}^1 {dx\over x}=L ~,
\nonumber
\end{eqnarray}
since after the substitution $u=2x$ in the second line of the
above display, the first and the second integrals cancel.
A similar derivation shows that $\Phi^*(\chi_k)=0$, thus one proves
formula (\ref{e111}) for $P_1(x)$ in Theorem 1(i).
To complete the proof of Theorem 1(i), we must establish depoissonization of
$\TL(z)$ which follows directly from Theorem 3. For the reader convenience,
we repeat the arguments below:
Observe that due to (\ref{26}) condition (\ref{e24}) of
the Depoissonization Lemma (growth estimate inside a cone $S_\theta$)
is automatically satisfied.
Assume now $z\notin \S_\theta$ for some $0<\theta<\pi /2$, and define
$1>\alpha> \cos \theta:=c$. We apply induction and the increasing
domains as in the proof of Theorem 3. Consider (\ref{e19}), and by
induction hypothesis assume that $|\TL(z/2)e^{z/2}| \leq \beta e^{\alpha
|z/2|}$ for some $\beta>1$. Then:
\begin{eqnarray*}
|\TL(z)e^z|&\leq&|f_d(z/2)e^{z/2}||\TL(z/2)e^{z/2}|+|f_d(z/2)e^{z}| \\
&\leq & |f_d(z/2)|e^{c |z/2|} \beta e^{\alpha |z/2|}+|f_d(z/2)| e^{c|z|}\\
&\leq & \beta e^{\alpha |z/2|}
\end{eqnarray*}
where the last inequality holds as long as we choose $\xi$ such that
for $|z|>\xi$ we have $|f_d(z/2)| \leq e^{(\alpha -c)|z/2|}$.
This completes the depoissonization argument, and after an application
of the depoissonization Lemma Theorem 1(i) is finally proved.
The proof of Theorem 1(ii) concerning the {\it variance} of $R_{N,d}$
is more intricate but it proceeds along the same lines as
the above derivation. In particular, we deal now with the
functional equation (\ref{e5}) which we repeat below
\begin{equation}
\TW(z)=f_d(z/2)\TW(z/2)+2\TL(z)f_d(z/2) ~.
\label{e27}
\end{equation}
Using the idea from Section 3.1 (cf. (\ref{e6}) -- (\ref{e9})) we
find immediately an explicit solution to (\ref{e27}), namely
$$
\TW(z)\varphi(z)=2 \sum_{n=0}^\infty \TL(z2^{-n-1}) \varphi(z2^{-n-1})~,
$$
which becomes, after inserting solution (\ref{e20}) for
$\TL(z)$
\begin{equation}
\TW(z)\varphi(z)=2\sum_{j=1}^\infty \sum_{n=1}^\infty \varphi(z2^{-n-j})~.
\label{e28}
\end{equation}
\par
To establish
the asymptotics of $\TW(z)$, thus also for $F_N^{\prime\prime}(1)$,
we proceed as before through the Mellin transform and
depoissonization. Let $Q_2(z)=\TW(z)\vphi(z)$ and $Q_2^*(s)$ be
its Mellin transform. Then, from the harmonic sum formula
$$
Q_2^*(s)=2\left({2^s\over 1-2^s}\right)^2 \varphi^*(s)=
2\left({2^s\over 1-2^s}\right)^3 \Phi^*(s)
$$
where $\Phi^*(s)$ is defined as before. Noting that
$$
{1\over (1-2^{-s})^3} = {1\over s^3L^3}+{3 \over 2 s^2 L^2} +{1 \over sL}
+O(1) ~,
$$
and computing residues, we easily obtain the following
for $z \con \infty$ and any $M>0$
$$
Q_2(z) = \log_2^2 z -(3+2C_d)\log_2 z +2+3C_d+D_d+ P_2(\log_2z) +
O(z^{-M})
$$
with $C_d$ from (8), $P_2(x)$ is a periodic function with
period 1, and
$$
D_d={1\over L^3}\Phi^{*\prime\prime}(0)=
{1\over L^3} \int_0^\infty e_d(x)e^{-x}\varphi(2x){\log^2 x\over x}
dx ~.
$$
The rest is easy.
We first depoissonize $Q_2(z)$ using the same arguments as above for
$\TL(z)$.
Since $\vphi(z)=1+O(z^{-M})$ for any $M>0$, we easily find
the second factorial moment of $\R$.
%Then, the Poisson variance becomes $\TV(z)=\TW(z)+\TL(z)-[\TL(z)]^2$.
Using Depoissonization Lemma,
%part (ii) we observe that
%$\var \R = \TV(N)(1-O(1/N)) +O(1/N)$.
%This completes
the proof of Theorem 1, apart from the asymptotics of the constant term for
$d\to\infty$, is completed.
\med
{\sc Case B: Large $d$}
\par
\medskip
Now, we analyze the case when $d\to \infty$.
Considering more carefully $\Phi^{*\prime}(0)$, we obtain
the following (with $\1(x)$ defined in (49))
\begin{eqnarray}
\Phi^{*\prime}(0)&=&-L^2/2+L \int_0^\infty (\1(x)-\varphi(x)){dx\over x}
\nonumber \\
&=&-L^2/2 +L\int_0^1\varphi(x){dx\over x}+
L\int_1^\infty(1- \varphi(x)){dx\over x} ~.
\label{d1}
%&\sim& O(1/d!) - \int_1^\infty e_d(x)e^{-x}{dx\over x} \ \ \ \ \ d\con \infty
\end{eqnarray}
We now estimate the above two integrals of (\ref{d1}) for large $d$.
The first one is easy. Note that $\vphi(x)\leq 1-e_d(x)e^{-x}= e^{-x}
\sum_{k=1}^\infty x^{d+k}/(d+k)!$. Thus,
$$
0\le
\int_0^1\varphi(x){dx\over x} \leq \sum_{k=1}^\infty {1\over (d+k)! (d+k)}
=O\left(\frac{1}{d!}\right) ~.
$$
In order to estimate the second integral of (\ref{d1}) -- which we call
$I(d)$ -- we recognize its
similarity to the {\it incomplete gamma} function (cf. \cite{as}).
We shall derive separately a lower and an upper bound on $I(d)$.
For the lower bound, we observe that
\begin{eqnarray}
I(d)&=&\int_1^\infty(1-\varphi(x)){dx\over x}
\ge\int_1^\infty e_d(x)e^{-x}{dx\over x}
= \int_1^\infty {e^{-t} \over t} dt +\sum_{i=1}^d {1\over i!} (\Gamma(i)-
\gamma(i,1)) \nonumber \\
&=&E_1(1)+\sum_{i=1}^d {1\over i!} (\Gamma(i)- \gamma(i,1) )
\label{d2}
\end{eqnarray}
where $E_1(1)=-\gamma -\sum_{n\geq 1} (-1)^n/(n n!)$ is
a particular value of the exponential
integral $E_1(z)=\int_z^\infty t^{-1}e^{-t}~ dt$, and
$\gamma(a,z)=\int_0^z e^{-t} t^{a-1} dt$ the incomplete gamma
function (cf. \cite{as}).
Now we must estimate the second term of (\ref{d2}). Note that
$$
{\gamma(i+1,1) \over i!} ={1\over e} \sum_{k=i+1}^\infty {1\over k!}~,
$$
and (cf. Knuth \cite{knuth1} Ex. 1.2.7--1.2.13),
$$
{1\over e} \sum_{k=1}^\infty {H_k\over k!}=
e\sum_{n=1}^\infty {(-1)^{n+1} \over n n!} ~,
$$
where $H_k$ is the $k$th harmonic number. Hence
\begin{eqnarray*}%\label{herz}
I(d) &\ge& H_d-\gamma+\frac{1}{e}\sum_{k\ge 1}\frac{H_k}{k!}-
\frac{1}{e}\sum_{i=1}^d\frac1i\sum_{k\ge i}\frac{1}{k!} \\
&=& H_d-\gamma+\frac1e\sum_{k>d}(H_k-H_d)\\
&\ge& H_d-\gamma=\log d+O(d^{-1}),\qquad d\con\infty.
\end{eqnarray*}
An upper bound on $I(d)$ is more intricate. First,
we rewrite $I(d)$ as
\begin{equation}
I(d)=\int_1^{d+1}(1-\vphi(x))\frac{dx}{x}+\int_{d+1}
^\infty(1-\vphi(x))\frac{dx}{x}~.
\label{i1}
\end{equation}
The first integral above denoted as $I_1(d)$ fulfills
$$
I_1(d)\le \int_1^\infty\frac{dx}{x}=\log(d+1)=\log d+O(d^{-1}),
\qquad d\con\infty.
$$
In the following we estimate the second integral of (\ref{i1}) which
we denote as $I_2(d)$.
We start from the observation that for $0\le a_k\le1$
$$
1-\sum_{k\ge0}a_k\le \prod_{k\ge0}(1-a_k),
$$
which can easily be proved taking logarithms. Therefore
$$
I_2(d)\le \sum_{k\ge0}I_{2,k}(d),
$$
with
$$
I_{2,k}(d)=\int_{d+1}^\infty e_d(x2^k)e^{-x2^k}\frac{dx}{x}
=\int_{(d+1)2^k}^\infty
e_d(u)e^{-u}\frac{du}{u}~.
$$
Now, for $u\ge d$,
$$
e_d(u)\le (d+1)\frac{u^d}{d!},
$$
so that
$$
I_{2,k}(d)\le \frac{d+1}{d!}\int_{(d+1)2^k}^\infty
u^{d-1}e^{-u}\frac{du}{u}~.
$$
Since the function $f(u)=u^de^{-u}$ takes its maximum for $u=d$ and is
monotonically decreasing for $u\ge d$, we have for $u\ge (d+1)2^k$
$$
u^{d-1}e^{-u}\le u^{-2}\left((d+1)2^k\right)^{d+1}e^{-(d+1)2^k}~.
$$
Hence
\begin{eqnarray*}
I_{2,k}(d)&\le & \frac{d+1}{d!}\left((d+1)2^k\right)^{d+1}e^{-(d+1)2^k}
\int_{(d+1)2^k}^\infty
\frac{du}{u^2}\\
&=&\frac{d+1}{d!}\left(\frac{d+1}{e}\right)^d2^{k(d+1)}e^{-(d+1)(2^k-1)}\\
&\le & \frac{d+1}{d!}\left(\frac{d+1}{e}\right)^d
\left(\frac2e\right)^{k(d+1)}~,
\end{eqnarray*}
so that $\sum_{k\ge 0}I_{2,k}(d)$ is exponentially small in $d\con\infty$.
Altogether we have proved that
\begin{equation}
I(d)=\log d+O(d^{-1}),\qquad d\con\infty~.
\end{equation}
Putting everything together, we finally obtained
the asymptotics for
$C_d$ described in Theorem 1(i), that is,
\begin{equation}
C_d=\frac{\Phi^{*\prime}(0)}{L^2}=
\log_2 d-1/2+O(d^{-1})~.
\end{equation}
Now, can turn our attention to
establishing Theorem 1(ii) for large $d$. We recall that
to compute the variance of $\R$ we need a precise estimate of $(\TL(N))^2$.
But the asymptotic formula on $(\TL(N))^2$ involves $P^2_1(\log_2 N)$,
where the
zeroth term
in the Fourier expansion of $P^2_1(x)$
is {\it not} equal to zero (in contrast to $P_1(x)$).
To recover this zeroth Fourier coefficient $[P_1^2]_0$, we need a new
representation of $P_1(x)$ which we recall below
$$
P_1(x)=-\frac{1}{L^2}\sum_{k\ne0}\Phi^{*\prime}(-\chi_k)e^{2k\pi ix}~.
$$
%The series is bounded due to the fact that $\Phi(x)$ is infinitely many
%differentiable, thus the Mellin $\Phi^*(s)$ for $s=it$ decays exponentially
%fast with $t$. Actually, the magnitude of oscillation is very small.
%To see this, we note that $\Phi(x)\leq e^{-x}$, hence
%$|\Phi^*(s)|\leq |\Gamma(s)|$. Observe that $|\Gamma(2\pi i/L)| \approx
%0.5 10^{-6}$, and using the standard arguments
%we can prove that the amplitude of $P_1(x)$ is very small.
Proceeding as with $\Phi^{*\prime}(0)$ above we find
$$
\frac{1}{L^2}\Phi^{*\prime}(\chi_k)=-\frac{1}{L\chi_k}-\frac{1}{L}\int_0^{d+1}
\vphi(t)\frac{dt}{t^{1+\chi_k}}+
\frac{1}{L}\int_0^{d+1}
(1-\vphi(t))\frac{dt}{t^{1+\chi_k}}~.
$$
Using integration by parts the whole expression turns out to be
\begin{equation}
\frac{1}{L^2}\Phi^{*\prime}(\chi_k)=-
\frac{1}{L\chi_k}\int_0^\infty\vphi'(t)\frac{dt}{t^{\chi_k}}.
\end{equation}
For later use we note that in the last integral $\vphi'(t)$ can be
replaced by $f'_d(t)=\frac{t^d}{d!}e^{-t}$ with an exponentially small
error in $d$: We have
$$
\int_0^\infty\vphi'(t)t^{-\chi_k}dt =
\int_0^\infty f'_d(t)t^{-\chi_k}dt+R(k,d),
$$
with
$$
R(k,d)=\int_0^\infty f'_d(t)(\vphi(2t)-1)t^{-\chi_k}dt+
2\int_0^\infty \vphi_0(t)\vphi'(2t)t^{-\chi_k}dt~,
$$
so that, integrating by parts,
$$
|R(k,d)|\le 2 \int_0^\infty f'_d(t)(\vphi(2t)-1)dt~.
$$
Splitting up the range of integration according to the regions where
either one of the factors of the integrand is small, $|R(k,d)|$ can be
estimated similarly to $\Phi^{*\prime}(0)$, and $R(k,d)$
turns out to be exponentially
small in $d$ (uniformly in $k$). Now,
$$
\int_0^\infty f'_d(t)t^{-\chi_k}dt=\frac{1}{d!}
\int_0^\infty t^{d-\chi_k}e^{-t}dt=\frac{\Gamma(d+1-\chi_k)}{d!}~,
$$
so that
$$
-\frac{1}{L^2}\Phi^{*\prime}(-\chi_k)=\frac{1}{L\chi_k}\left(
\frac{\Gamma(d+1+\chi_k)}{d!}+R(k,d)\right)
$$
and we finally obtain
\begin{equation}\label{groer}
P_1(x)={1\over L} \sum_{k\neq 0}\frac{1}{\chi_k}\left(
\frac{\Gamma(d+1+\chi_k)}{d!}+R(k,d)\right)e^{2k\pi ix} ~.
\end{equation}
Finally,
we can return to the evaluation of the zeroth Fourier coefficient
$[P_1^2]_0$ of $P_1^2(x)$. According to
the uniform exponential smallness of $R(k,d)$ for $d$ getting large
we have
\begin{equation}
{[P_1^2]}_0
=\frac{1}{L^2d!^2}\sum_{k\neq 0}
\frac{1}{|\chi_k|^2}|\Gamma(d+1+\chi_k)|^2
\ + \hbox{exp. small terms in $d$}~.
\label{ph1}
\end{equation}
In order to evaluate the series occurring in
(\ref{ph1}) we observe that
\begin{equation}
\frac{1}{\chi_k}\frac{\Gamma(d+1+\chi_k)}{d!}
=\binom{d+\chi_k}{d}\Gamma(\chi_k)=
\sum_{\lambda=0}^d
\binom{\lambda+\chi_k-1}{\lambda}\Gamma(\chi_k)~.
\end{equation}
Therefore the main term of $P_1(x)$ coincides perfectly with the
periodic function $P_1(x)$ analyzed in \cite{kp3}
(cf. Theorem 3 of \cite{kp3})
if $d$ is replaced by $d+1$. The mean ${[P_1^2]}_0$
of the square of the latter fluctuating function can be analyzed
by different methods. In \cite{kp3} this quantity is treated using
Hankel contour integrals
with the ``kernel''
$$
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}~.
$$
An earlier approach, using transformation results due to Ramanujan, may
be found in \cite{NEU}. From \cite{kp3} we have the asymptotic result
$$
{[P_1^2]}_0=\frac{1}{12}-\frac{1}{\sqrt{\pi d}}+O(\frac1d), \qquad
d\con\infty~.
$$
This completes the proof of part (ii) of Theorem 1.
\med
{\bf 3.3 Asymptotic Limiting Distributions}
\par
\medskip
In this subsection, we prove Theorem 2 concerning the
asymptotic distribution of $\R$. The Poisson generating function
$\TG(z,u)$ of $\R$ satisfies the functional equation (\ref{e15}).
But, the Mellin transform of $\TG(z,u)$ with respect to $z$ does not
exist since $\TG(z,u)=O(1)$ for both $z\to \infty$ and $z\to 0$.
Therefore, we introduce the new function $\TH(z,u)=\TG(z,u)-1$ whose
Mellin transform exists in $\Re(s)\in(-1,0)$. Observe that
$\TH(z,u)$ fulfills the following functional equation
\begin{equation}
\TH(z,u)=uf_d(z/2)\TH(z/2,u)+(u-1)f_d(z/2) ~.
\label{e15a}
\end{equation}
This equation falls under our general equation (\ref{e6}) from
Section 3.1. In particular, using the same arguments as before,
we can write the solution for $\TH(z,x)$ as
\begin{equation}
\varphi(z) \TH(z,u)= (u-1) \sum_{n=0}^\infty u^n \varphi(z2^{-n-1}) ~,
\label{e16}
\end{equation}
where $\varphi(z)$ is defined in (\ref{e21}).
We can now easily obtain asymptotic expansion for the probability generating
function $F_N(z)$.
To derive it we apply the Mellin transform
technique and then depoissonization
since (\ref{e15a}) satisfies all conditions of Theorem 3. As a result,
we can prove the following
\begin{equation}
F_N(u) = u^{\log_{2} N} {\Phi^*(- \log_2 u)\over L (u-1)} +
P_3(\log_2N) +O(N^{-1/2+\varepsilon}) ~.
\label{e17}
\end{equation}
where $\Phi^*(s)$ is the Mellin transform of $\vphi(2x)-\vphi(x)$
as discussed in Section 3.2 and $P_3$ is a fluctuating function.
However, to derive the asymptotic distribution of $\R$, we proceed in
a different manner. Note that from (\ref{e16}) we obtain
$$
{1-\TG(z,u) \over 1-u} = \sum_{k=0}^\infty u^k {\vphi(z2^{-k-1})
\over \vphi(z)}~.
$$
But, using the definition of $\TG(z,u)$ and comparing coefficients at $u^k$
we arrive at
\begin{equation}
\th_k(z)= [u^k] {\TH(z,u)\over 1-u}=
e^{-z}\sum_{N=0}^\infty \pr\{\R>k\} {z^N\over N!} =
{\vphi(z2^{-k-1}) \over \vphi(z)} =\prod_{j=1}^{k+1}f_d(z/2^j)
\label{w1}
\end{equation}
with $f_d(z)=1-e_d(z)e^{-z}$.
In the following we depoissonize (\ref{w1}).
% {\em for fixed $k$}. We start
%from
%\begin{equation}\label{herz}
%\frac{\vphi(z2^{-k-1})}{\vphi(z)}=\prod_{j=1}^{k+1}
%\Big(1-e_d(z2^{-j})e^{-z2^{-j}}\Big).
%\end{equation}
%Now, for $z\to\infty$,
%\begin{equation}\label{herzz}
%|1-e_d(z)e^{-z}|\le 1+|e_d(z)e^{-z}|\le 1+C_1 |z|^de^{-\Re z}
%\end{equation}
%with $C_1=C_1(d)$.
%Let us consider the case $z\in S_\theta=\{z : |\arg z|<\theta,
%0<\theta y \frac\pi2\}$ at first. Then we have
%$\Re z=|z| \cos(\arg z)>|z|\cos\theta$, so that (\ref{herz})
%implies
%$$
%|1-e_d(z)e^{-z}|\le 1+C_1|z|^de^{-|z|\cos\theta}
%\le C_2=C_2(d).
%$$
%Therefore the finite product (\ref{herz})
%may be estimated by $C_2^{k+1}$ for $z\to \infty$, $z\in S_\theta$.
%
%Now we turn to the region outside the cone $S_\theta$.
%Let us assume $\Re z\ge 0$ at first. Then we have from (\ref{herzz})
%$$
%|1-e_d(z)e^{-z}|\le 1+C_1|z|^d\le C_3|z|^d,
%$$
%for $z\to\infty$, with $C_3=C_3(d)$, so that
%\begin{eqnarray*}
%\left|e^z\frac{\vphi(z2^{-k-1}}{\vphi(z)}\right|&\le&
%e^{\Re z}\, C_3^{k+1}|z|^{d(k+1)}2^{-\binom{k+2}{2}}\\
%&\le&C_4 \, e^{\alpha |z|}
%\end{eqnarray*}
%with $\cos\theta <\alpha<1$, $C_4=C_4(d,k)$, since
%$\Re z\le |z|\cos\theta $ for $z\notin S_\theta$.
%
%Finally we consider the case $\Re z<0$, $z\notin S_\theta$.
%Here we find from (\ref{herzz})
%$$
%|1-e_d(z)e^{-z}|\le C_5 |z|^de^{-\Re z},
%$$
%$z\to \infty$, $C_5=C_5(d)$. Therefore
%\begin{eqnarray*}
%\left|e^z\frac{\vphi(z2^{-k-1}}{\vphi(z)}\right|&\le&
%e^{\Re z}\, C_5^{k+1}|z|^{d(k+1)}2^{-\binom{k+2}{2}}
%e^{-\Re z(1-2^{-k-1})}
%\\
%&\le&C_6 \, e^{\alpha |z|}
%\end{eqnarray*}
%with $0<\alpha<1$, $C_6=C_6(d,k)$.
%
We start with an estimate on $\th_k(z)$ inside the cone, thus we
assume $z\in S_\theta$. Then,
$\Re z=|z|\cos (\arg z)\ge |z|\cos\theta$, and
\begin{eqnarray*}
|f_d(z)|&=&|1-e_d(z)e^{-z}|\le 1+e_d(|z|)|e^{-z}|=1+e_d(|z|)e^{-\Re z}\\
&\le& 1+e_d(|z|)e^{-|z|\cos\theta}~.
\end{eqnarray*}
If we assume $\theta\le \frac{\pi }{3}$, the last estimate reads
$$
|f_d(z)|\le 1+e_d(|z|)e^{-|z|/2}\qquad\mbox{for all $z\in S_\theta$~. }
$$
Let $\eps>0$ be arbitrarily small. Then there exists
$K=K(\eps)\ge1$ such that $e_d(x)e^{-x/2}<\frac{\eps}{2}$ for all $x>K$,
resp.
\begin{equation}\label{tussi}
|f_d(z)|\le 1+\frac{\eps}{2}\qquad\mbox{for $z\in S_\theta$, $|z|>K(\eps)$~. }
\end{equation}
Let us now consider the region $|z|\le K$: Since
$0\le f_d(x)=1-e_d(x)e^{-x}\le f_d(K)<1$ for $x\in[0,K]$
and the function $f_d(z)$ is continuous, there exists an open
neighbourhood $\U(x)$ of each point $x\in[0,K]$ with
$|f_d(z)|\le1$ for $z\in \U(x)$. Due to the compactness of $[0,K]$,
it follows that we can choose $\theta=\theta(\eps)$ small enough such that
\begin{equation}\label{tussitussi}
|f_d(z)|\le 1 \qquad\hbox{for $z\in S_{\theta(\eps)}$, $|z|\le K(\eps)$~. }
\end{equation}
By (\ref{tussitussi}) it follows that
\begin{equation}\label{tussitussitussi}
|f_d(z/2^j)|\le 1 \qquad\hbox{for $j>\log_2(|z|/K(\eps))$,
$z\in S_{\theta(\eps)}$, $|z|\le K(\eps)$~. }
\end{equation}
To estimate ${\widetilde h}_k(z)$ we split the product
from (\ref{w1})
into the regions $1\le j \le \min(k+1,\log_2(|z|/K(\eps))$ and
$j> \min(k+1,\log_2(|z|/K(\eps))$, and we obtain
$$
|\widetilde h_k(z)|\le \left(1+\frac{\eps}{2}\right)^{\log_2(|z|/K(\eps))}
=\left(\frac{|z|}{K(\eps)}\right)^{\log_2(1+\frac{\eps}{2})}
$$
i.e.,
$$|\widetilde h_k(z)|\le |z|^{\eps}\qquad\mbox{ for $z\in S_{\theta(\eps)}$, $|z|\ge1$~.}
$$
To complete the depoissonization, we need to estimate $\th_k(z)$ outside the
cone. Thus, assume
$z\notin S_\theta$, so that $\Re z=|z|\cos(\arg z)\le |z|\cos\theta$.
Therefore, with $C_1=C_1(d)$
\begin{equation}\label{plussi}
|e^zf_d(z)|=|e^z-e_d(z)|\le e^{\Re z}+e_d(|z|)\le (1+C_1)e^{|z|\cos\theta}~.
\end{equation}
Again we need a sharper estimate for $|e^{z/2^j}f_d(z/2^j)|$ if $j$ is large:
Since $e^zf_d(z)$ is continuous with $e^0f_d(0)=0$, there exists a constant
$C_3=C_3(d)>0$ such that
\begin{equation}\label{plussiplussi}
|e^zf_d(z)|<1 \qquad\hbox{for $|z| \log_2(|z|/C_3)$~.}
\end{equation}
Now we proceed as follows: Since $\sum_{j=1}^{k+1}\frac{1}{2^j}=1-\frac{1}{2^{k+1}}$,
we have
\begin{equation}
\Big|e^z\prod_{j=1}^{k+1}f_d(z/2^j)\Big|
=|e^{z/2^{k+1}}\prod_{j=1}^{k+1}(e^{z/2^j}-e_d(z/2^j))|~,
\end{equation}
which is estimated by
$$
e^{\Re z/2^{k+1}}\prod_{1\le j \le K}(1+C_1)\, e^{(|z|\cos\theta)/2^j}~,
$$
where $K=\min(k+1, \log_2(|z|/C_3))$ . Therefore the estimate is less than
or equal to
\begin{eqnarray*}
&& e^{(|z|\cos\theta)/2^{k+1}}(1+C_1)^K e^{|z|\cos\theta \, (1-\frac{1}{2^k})}\\
&&\le (1+C_1)^{\log_2(|z|/C_3)}e^{|z|\cos\theta \, (1+\frac{1}{2^{k+1}}-\frac{1}{2^k})}\\
&&\le\left(\frac{|z|}{C_3}\right)^{\log_2(1+C_1)}e^{|z|\cos\theta}
k\} ={\vphi(N2^{-k-1}) \over \vphi(N)} +O\left(N^{-1/2+\eps}\right) ~,
$$
for any $ \eps>0$ where the $O$--constant is independent of $k$.
To complete the proof of
Theorem 2, it suffices to set $k=\lfloor \log_2N +t\rfloor -1$,
and notice that $\pr\{\R>\log_2N +t -1\}=\Pr\{\R>\lfloor \log_2N
+t\rfloor -1\}$ .
\big
{\bf ACKNOWLEDGEMENT}
\par
\medskip
We thank
% Dr.
Philippe Jacquet (INRIA, Rocquencourt)
for several valuable discussions concerning the depoissonization issues.
\begin{singlespace}
\begin{thebibliography}{99}
\bibitem{as}
M. Abramowitz, and I. Stegun (Eds.),
{\it Handbook of Mathematical Functions with Formulas,
Graphs, and Mathematical Tables}, John Wiley \& Sons,
New York 1972.
\bibitem{aldous}
D. Aldous,
{\it Probability Approximations via the Poisson Clumping Heuristic},
Springer Verlag, New York 1989.
\bibitem{anderson}
Anderson, C. (1970).
Extreme value theory for a class of discrete distributions with
applications to some stochastic processes. {\it J. Appl. Probability},
vol. 7, pp. 99--113.
\bibitem{bb}
G. Brassard and P. Bratley,
{\it Algorithmics. Theory and Practice},
Prentice Hall, Englewood Cliffs, 1988.
\bibitem{davies}
B. Davies,
{\it Integral Transforms and Their Applications},
Springer-Verlag,
1978.
\bibitem{doetsch}
G. Doetsch,
{\it Handbuch der Laplace Transformation, {\rm Vol.~1--3}},
Birkh{\"a}user Verlag,
Basel,
1955.
\bibitem{ms}
J. Fill, H. Mahmoud and W. Szpankowski,
On the Distribution for the Duration of a Randomized Leader Election
Algorithm, {\it Annals of Applied Probability}, to appear.
\bibitem{FJnote}
P. Flajolet, P. Jacquet, and W. Szpankowski,
Mellin Transform of a Complex Variable: A Simple Extension,
Unpublished Manuscript, 1995.
\bibitem{fm}
P. Flajolet and G.N. Martin,
Probabilistic Counting Algorithms for Data Base Applications,
{\it J. Comp. Syst. Sci.}, 31, 182-209, 1985.
\bibitem{fs}
P. Flajolet and N. Saheb,
The Complexity of Generating an Exponentially Distributed Variate,
{\it J. Algorithms}, 7, 463-488, 1986.
\bibitem{fla}
P. Flajolet and B. Richmond,
Generalized Digital Trees and Their Difference-Differential Equations,
{\it Random Structures and Algorithms}, 3, 305-320, 1992.
\bibitem{frs}
P. Flajolet, X. Gourdon and P. Dumas,
Mellin Transforms and Asymptotics: Harmonic Sums,
{\it Theoretical Computer Science}, 144, 3-58, 1995.
\bibitem{grabner}
P. Grabner,
Searching for losers,
{\it Random Structures and Algorithms\/}, 4, 99--110, 1993.
\bibitem{gfl}
A. Greenberg, P. Flajolet and R. Ladner,
Estimating the Multiplicities of Conflicts to Speed Their Resolution in
Multiple Access Channels,
{\it JACM}, 34, 289-325, 1987.
\bibitem{henrici}
P. Henrici,
{\it Applied and Computational Complex Analysis}, vol. 2,
John Wiley {\it \&} Sons 1977.
\bibitem{jr}
P. Jacquet, M. R\'{e}gnier, Trie partitioning process:
limiting distributions. {\it Lecture Notes in Computer Science\/}, vol. 214,
pp. 196--210, Springer, New York 1986.
\bibitem{js}
P. Jacquet and W. Szpankowski,
Ultimate Characterizations of the Burst Response of an Interval Searching
Algorithm: A Study of a Functional Equation,
{\it SIAM J. Computing}, 18, 777-791, 1989.
\bibitem{js1}
P. Jacquet and W. Szpankowski,
Asymptotic behavior of the Lempel-Ziv Parsing Scheme and Digital Search
Trees, {\it Theoretical Computer Science}, 144, 161-197, 1995.
\bibitem{js2}
P. Jacquet and W. Szpankowski,
Analytical depoissonization and its applications, preprint.
\bibitem{kendall}
M. Kendall and A. Stuart,
{\it The Advanced Theory of Statistics}, 4th Ed. vol. 1,
Charles and Griffin and Co. Ltd., London (1977).
\bibitem{kingman}
J.F.C. Kingman,
{\it Subadditive processes}, in
Ecole d'Et\'{e} de Probabilit\'{e}s de Saint-Flour V-1975,
Lecture Notes in Mathematics, 539, Springer-Verlag, Berlin (1976).
\bibitem{kp1}
P. Kirschenhofer and H. Prodinger,
On the Analysis of Probabilistic Counting,
{\it Lecture Notes in Mathematics}, 1452 (Eds. E. Hlawka and R. Tichy),
117-120, Springer Verlag 1990.
\bibitem{NEU}
P. Kirschenhofer and H. Prodinger,
On some applications of formul\ae\ of Ramanujan in the analysis of
algorithms,
{\it Mathematika}, 38, 14-33, 1991.
\bibitem{kp2}
P. Kirschenhofer and H. Prodinger,
Approximate Counting: An Alternative Approach,
{\it Informatique Th\'{e}orique et Applications/Theoretical Informatics
and Applications}, 25, 43-48, 1991.
\bibitem{kp3}
P. Kirschenhofer and H. Prodinger,
A Result in Order Statistics Related to Probabilistic
Counting, {\it Computing}, 51, 15-27, 1993.
\bibitem{kps}
P. Kirschenhofer, H. Prodinger, and W. Szpankowski,
How to count quickly and accurately: A unified analysis of
probabilistic counting and other related problems,
{\it International Conference on Automata, Languages, and Programming
(ICALP'92)}, Vienna, LNCS, No. 623, 211-222, 1992.
\bibitem{knuth1}
D. Knuth,
{\it The Art of Computer Programming: Fundamental Algorithms,}
vo. 1., Addison-Wesley, Reading 1973.
\bibitem{knuth}
D.E. Knuth,
{\it The Art of Computer Programming. Sorting and Searching},
vol. 3., Addison-Wesley, Reading, MA 1973.
\bibitem{morris}
R. Morris,
Counting Large Numbers of Events in Small Registers,
{\it Comm. ACM}, 21, 840-842, 1978.
\bibitem{pittel}
B. Pittel and H. Rubin,
How Many Random Questions Are Necessary to Identify $n$ Distinct Objects?,
{\it J. Combinatorial Theory, Ser. A}, 55, 292-312, 1990.
\bibitem{prodinger}
H. Prodinger,
How to Select a Loser,
{\it Discrete Math.}, 120, 149--159, 1993.
\bibitem{rjs}
B. Rais, P. Jacquet, and W. Szpankowski, Limiting Distribution for the
Depth in Patricia Tries, {\it SIAM J. Discrete Mathematics},
6, 197-213, 1993.
\bibitem{rj}
M. R\'{e}gnier and P. Jacquet,
Normal Limiting Distribution of the Size of Tries,
{\it Proc. Performance'87}, Amsterdam: North-Holland, 209-223, 1987.
\bibitem{usch}
U. Schmid, The Average CRI-length of a Tree Collision Resolution
Algorithm in Presence of Multiplicity-Dependent Capture Effects,
{\it Proc. ICALP 92}, Vienna, 223-234, 1992.
\bibitem{spa1}
W. Szpankowski,
Solution of a Linear Recurrence Equation Arising in the Analysis of Some
Algorithms, {\it SIAM J. Alg. Disc. Methods}, 8, 233-250, 1987.
\bibitem{spa2}
W. Szpankowski,
Patricia Tries Again Revisited, {\it JACM}, 37, 691-711, 1990.
\bibitem{sr}
W. Szpankowski and V. Rego,
Yet Another Application of a Binomial Recurrence. Order Statistics,
{\it Computing}, 43, 401-410, 1990.
\end{thebibliography}
\end{singlespace}
\end{document}