
%-------------------------------------------------------------------------
\documentstyle[11pt]{article}

\pagestyle{empty}

% 11pt implies a 10% reduction for LNCS. 

\textheight 217mm % for 10\% reduction
\textwidth 140mm  % for 10\% reduction



% to get Theorems etc all right
% Definitions
\newtheorem{dep}{Depoissonization Lemma}
     
\newtheorem{theorem}{Theorem}
\newtheorem{property}{Property}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}

\sloppy % to make things easier

\begin{document}

\title{\LARGE\bf How to Count Quickly and Accurately:\\ \smallskip
\large
A Unified Analysis of Probabilistic Counting and Other 
Related~Problems}
\author{Peter {\sc Kirschenhofer\footnotemark}   $\qquad$
Helmut {\sc Prodinger$^*$}
\\
Technical University of Vienna\\ \\
Wojciech {\sc Szpankowski}\footnotemark\\
Purdue University, West Lafayette}
\date{}
\maketitle








\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}




\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.1}
\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{{\bf 1}}
\def\t{\tilde}
\def\half{{1\over 2}}
\def\med{\medskip\parsec}
\def\binom Nk{{N \choose k}}
\def\M{{\cal M}}
\def\n{\eta}
\def\ss{\sigma}
\def\pr{{\rm Pr}}
\def\w{\omega}
\def\l{\ell}
\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\var{{\rm var}}
\def\sech{\text{sech}}





\footnotetext[1]{
Department of Algebra and Discrete Mathematics,
Technical University of Vienna, Wiedner Hauptstrasse 8--10, 
A-1040 Vienna, Austria.
This work was supported by Fonds zur F\"{o}rderung der
Wissenschaftlichen Forschung Project P7497-TEC}

\footnotetext[2]{Department of Computer Science, Purdue University,
West Lafayette, IN 47907, U.S.A. \linebreak
This research was supported by
the NSF Grant INT-8912631, and in part by
AFOSR grant 90-0107,
by the NSF grant
CCR-8900305,  and by grant R01 LM05118 from the National Library of
Medicine.}

\footnotesize

\begin{small}
\begin{quote}
\noindent
{\bf Abstract.}  \sl
We consider a class of probabilistic counting algorithms parameterized by
an integer $d\geq 0$ that estimate the number of  elements $N$
in a large set.
Our algorithms generalize an idea of Flajolet and Martin 
who limited themselves to the case $d=0$.
As noted by Brassard and Bratley 
``it is far from obvious how to carry out a more precise analysis of
the unbiased estimate of $N$ \dots ''. 
We present a novel and complete analysis of
these new counting algorithms that 
-- to the best of our knowledge -- cannot be
obtained by an extension of the analysis 
by Flajolet and Martin.
We present results concerning the average value, the variance
and the limiting generating function
of an estimate of $N$.
Moreover, our novel approach is {\it not} limited to 
probabilistic counting algorithms,
and it can be applied in the investigation 
of several other ``splitting algorithms" such as
selecting the loser within a group of people, estimating the 
number of questions
necessary to identify the number of distinct objects,
searching algorithms based on digital tries, approximate
counting, electing $d$ finalists in a contest (cf. polling system),
and so forth.
\end{quote}
\end{small}

\normalsize


\section{Introduction}

Flajolet and Martin in their  paper \cite{fm} proposed an
algorithm in order to estimate the cardinality of large
(multi)sets of data. This algorithm is probabilistic in nature and
works as follows. In order to estimate the cardinality $N$ of a
(multi)set $\M$ 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 modified 
hashed strings 
is used to build the so called $bitmap$ and to obtain
the estimate $R_N$ of the cardinality $N$ of $\M$. More precisely, the 
position of the leftmost zero in the $bitmap$ string approximates
$\log_2 N$ (for details see below and \cite{fm}, \cite{bb}). 

The original algorithm turns out to have the variance of the estimator
$R_{N}$ approximately to $1.257$, which is rather large for practical
implementations. Therefore a modification of the basic algorithm was
also proposed in \cite{fm} but this new algorithm is more
complex and costly.

In our paper, we  propose for the instance of sets without
replications a new
estimate $R_{N,d}$ of $N$ that is parameterized by an integer $d$.
The value $d=0$ corresponds to Flajolet-Martin's basic algorithm. 
Our algorithm has smaller variance (apart form fluctuations 
the value tending to  $1/12=0.083$
as $d\con \infty$).
The new idea behind our algorithm is to {\it count} the number of
$1$'s up to $d+1$ in every position of the $bitmap$. 
As an estimate of $N$ we propose to take 
the leftmost position that contains the
value smaller than $d+1$. More formally, our algorithm 
works as follows.
We assume that there
exists a 
carefully implemented hashing function $hash:~ \M \con \{0,1\}^m$
where $m$ is chosen as in \cite{fm}. 
Let $y$ be the image of 
$x\in\M$ over
the $hash(\cdot)$ function, that is,
$y=hash(x)$. The procedure below constructs another
string called $bitmap$ that is used to estimate $N$. As in 
\cite{fm},
we define the function $\rho(y)$ for a binary string $y$ as the leftmost
position that contains value $1$.
\begin{tabbing}
{\bf procedure} $BITMAP$ \\
{\bf for} $i=0$ {\bf to} $m-1$ {\bf do} $bitmap(i)=0$ ;\\
{\bf for} \= $x\in \M$ {\bf do} \\
	\>{\bf begin} \\
	\>$y=hash(x)$ ;\\
	\>$index := \rho(hash(x))$\\
	\>$bitmap(index)=\min\{bitmap(index)+1,~ d+1\};$\\
	\>{\bf end};
\end{tabbing}
Note that the resulting string $bitmap$ is a $d+1$-ary 
string. For example,
for $d=3$ we may have $bitmap= 4444444444434100000$. As the estimate
$R_{N,d}$ we take the position of the leftmost 
value smaller than $d+1$
(e.g., in the example above we have $R_{N,3}=11$). More precisely
we define:
\begin{equation}
R_{N,d}= \min\{ k:~ bitmap(k)<d+1~ \hbox{and for all}~ 
0\leq i<k \ \ bitmap(i)=d+1\} ~.
\label{e1}
\end{equation} 
It is easy how our algorithm works. The $bitmap$ string is a sequence
of integers from the set $\{0,1, \dots , d+1\}$. If
$bitmap(i)=k<d+1$, then exactly $k$ strings $y$ have
at the $i$th position the leftmost one. Moreover, $bitmap(i)=d+1$ 
means that  
{\it at least} $d+1$ strings 
$y$ contain the leftmost one at position $i$.
\par
We now summarize our main results concerning the probabilistic behavior
of $R_{N,d}$. In particular, 
we prove that $ER_{N,d} = \log_2 N -1 -C_d +P(\log_2N) +
O(\sqrt{N})$ where
$C_d$ is a constant such that $C_d = \log_2 d -0.5 +
O(d^{-1/2+\eps})$ as $d\con \infty$,
and $P(x)$ is a periodic fluctuation of period 1.
More importantly, we show that the variance of $R_{N,d}$ 
fulfills, neglecting periodic fluctuations, 
$\var R_{N,d} \con 1/12 =0.08333\ldots$  as $d\con \infty$.
Interestingly enough the quantity $1/12$ is not uncommon in such a 
situation and known as
Sheppard's
correction (cf. \cite{kendall}) which says that the discretization
by itself introduces some fluctuations with the variance equal to $1/12$. 
Finally, in the next section 
we make some comments concerning the distribution and
the limiting generating function for $R_{N,d}$.

The reader might have noticed that for $d\ge 1$ our algorithm does not
necessarily neglect multiplicities. 
To be more precise: Only multiplicities greater than $d$ will
be ignored by the algorithm.
Therefore for data base applications
a priori knowledge about the expected multiplicities of the different
elements is necessary. In this paper we confine our analysis on the
quantity $R_{N,d}$, which is a good estimator provided there are no
multiplicities.

Literature on the probabilistic counting is rather scanty. It was initiated
by the paper of Flajolet and Martin \cite{fm}
who analyzed the case $d=0$
of our algorithm. Their analysis is based on an application of 
the inclusion-exclusion rule, and -- to the best of our knowledge -- cannot 
be extended to $d>0$. This is also evident from the
analysis of Greenberg, Flajolet and Ladner \cite{gfl} who 
analyzed a conflict resolution algorithm which resembles the case $d=1$
of our analysis. A simplification of Flajolet-Martin's analysis is
presented in Kirschenhofer and Prodinger \cite{kp2}. Finally, 
a different estimator for the probabilistic counting algorithm was 
analyzed in Szpankowski and Rego \cite{sr} who investigated the
maximum over $N$ geometrically distributed random variables. The authors of
\cite{sr} considered the {\it last} bit that is equal to one in the $bitmap$.
Unfortunately, in this case the variance is even bigger and equal to
$3.507$.




It must be stressed that the novelity of our paper also lies in
the area of the mathematical analysis of algorithms. 
In fact, our technique of analysis can be applied to several 
other algorithms. As shown in the section below, we reduce
our probabilistic counting algorithm to a problem on 
{\it (digital) trees}. 
%probabilistic counting is an instance of a more general class of algorithms
%which ask how to split randomly a group of $N$ objects into a set 
%of size $d$ (cf. \cite{pittel}, \cite{prodinger}). To evaluate
%the number of questions required to split these objects, 
Evaluating a parameter of such a tree,
we obtain
the following functional equation 
\begin{equation}
g(z)=\beta a(z/2)g(z/2) +b(z) ~.
\label{e2}
\end{equation}
In general, this equation does not have an explicit finite solution
unless $a(z)$ is a very particular function. For example,
$a(z)=e^{z}$ was discussed in Knuth \cite{knuth} (cf. also 
\cite{spa2}), 
and Szpankowski \cite{spa1}, \cite{spa2} (cf. also
\cite{knuth}) investigated the case $a(z)=e^z+1$. 
For these two cases explicit final solutions of 
(\ref{e2}) were obtained, but it is rather hopeless 
to expect the existence
of a useful closed form solution for general $a(z)$ and $b(z)$.
An asymptotic solution to (\ref{e2}) was
first suggested in Jacquet and Szpankowski \cite{js} who analyzed
the case $a(z)=1+(1+z)e^{-z}$. Recently, Flajolet and Richmond
\cite{fla} investigated asymptotically the above equation with
$a(z)=2z^b/(1+z)^b$ for some integer $b>0$. 
Here, analyzing
probabilistic counting
algorithms, we must
investigate (\ref{e2}) with $a(z)=1-e_d(z)e^{-z}$ where 
$e_d(z)=\sum_{i=0}^d
z^i/i!$. 

\section{Main Results}

In this section we present our main results. We start with another
description of the probabilistic counting algorithm
which will slightly differ from the
one presented in Section 1, but it helps us to establish
recurrence equations necessary for the analysis.
\par
Our new description goes as follows.
Let us consider an empty $bitmap$ string, that is, with all positions
filled by zeros. Assume that $N$ objects (e.g., data, persons, etc.)
can randomly insert (hit) a $1$ at any position of the $bitmap$, however,
probability of hitting the $j\geq 0$ position is equal to $2^{-j-1}$.
In terms of the probabilistic counting, 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 
($0^j$ denotes $j$ consecutive zeros).
Every object can hit only
one time. In addition, we count the number of
hits in any position of the $bitmap$, but we count the number of hits 
only up to some value $d+1$, where $d$ is a given parameter. In other words,
the $bitmap$ is a $d+1$-ary string. Clearly, the $bitmap$ will contain a lot
of $d+1$'s at the begining 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 $bitmap$. The parameter of interest 
is the length  
$R_{N,d}$ of the longest run of $d+1$'s in the front of the
$bitmap$. A precise definition of $R_{N,d}$ is
given in (\ref{e1}).
\par
Let $F_N(z)=Ez^{R_{N,d}}$ be the probability generating function 
of the estimator $R_{N,d}$. 
That is, $[z^j]F_N(z)$ (the $j$th coefficient
at $F_N(z)$) is the probability that the $bitmap$ is
$(d+1)^jc\ldots$ where $c<d$, and $(d+1)^j$ denotes $j$
consecutive  values ``$d+1$''. 
To derive the recurrence for $F_N(z)$,
one may represent the action of our algorithm as a splitting process
in a {\it digital tree\/}. Imagine 
$N$ persons flipping a fair coin, and those
who get $1$ (a hit) move to the right while the rest to the left.
The process continues until less than $d+1$ persons flip a $1$.
Imagine that at the first step $k$ persons flip $1$. Then, the contribution to
the generating function $F_N(z)$ is as follows: if $k\leq d$ then  we
need to add $z^0 \sum_{k\leq d} {N\choose k} 2^{-N}$, otherwise
the contribution becomes $z\sum_{d+1\leq k\leq N}
{N\choose k} 2^{-N}
F_{N-k}(z)$. In short, we obtain the following recurrence
\begin{equation}
F_N(z)=\sum_{k=0}^d {N\choose k} 2^{-N} + z \sum_{k=0}^{N-d-1}{N\choose k} 
2^{-N} F_k(z) ~, 
\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 moments
of $R_{N,d}$, namely: $ER_{N,d}=F_N^\prime(1)$ and 
$\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, $L(z)=\sum_{N\geq 0} F_N^\prime(1) z^N/N!$ and
$W(z)=\sum_{N\geq 0} F_N^{\prime\prime}(1) z^N/N!$. Define also
$\TL(z)=e^{-z}L(z)$ and $\TW(z)=e^{-z}W(z)$. Then, (\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 $f_d(z)=1-e_d(z)e^{-z}$ and $e_d(z)=1+z^1/1! + \cdots +z^d/d!$.
\par
Both functional equations fall into the general equation (\ref{e2})
which we repeat below
\begin{equation}
g(z)=\beta a(z/2)g(z/2) +b(z) ~.
\label{e6}
\end{equation}
where $\beta\leq 1$. Iterating (\ref{e6}), we obtain a general solution
in the form of (cf. \cite{js})
\begin{equation}
g(z)=\sum_{n=0}^\infty \beta^nb(z2^{-n}) \prod_{k=1}^n a(z2^{-k})
\label{e7}
\end{equation}
if $g(0)=0$. Define
\begin{equation}
\varphi(z)=\prod_{j=0}^\infty a(z2^j) ~,
\label{e8}
\end{equation}
provided the infinite product in (\ref{e8}) converges. 
Then, the general
solution (\ref{e7}) can be rewritten as
\begin{equation}
g(z)\varphi(z)=\sum_{n=0}^\infty \beta^n b(z2^{-n}) \varphi(z2^{-n}) ~.
\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}) and (\ref{e5}).
In Section 3 we present our detailed derivations.
\par
Now we are ready to present our main results.
\begin{theorem}
Consider the probabilistic 
counting algorithms
described above, and in particular the quantity $R_{N,d}$.
\med
{\rm (i)} The average value of $R_{N,d}$ becomes asymptotically as 
$N\con \infty$ 
\begin{equation}
ER_{N,d} \sim \log_2 N -1 -C_d +P_1(\log_2N) +
O(N^{-1/2+\varepsilon})
\label{e10}
\end{equation}
where $P_1(x)$ is a periodic function with period 1 and mean zero,
and with $L=\log 2$ we have

\begin{eqnarray}
C_d&=&{1\over L^2} \int_0^\infty e^{-x}e_d(x)\varphi(2x)
\frac{\log x}{x} dx \nonumber \\
&\sim& \log_2 d -0.5 +O(d^{-1/2+\eps}) \ \ \ \ \ \ \hbox{as} \ \ \
d\con \infty ~.
\label{e11}
\end{eqnarray}
{\rm (ii)} The variance of $R_{N,d}$  is for $N\con \infty$
\begin{eqnarray}
\var R_{N,d} \sim D_d -C_d^2 +P_2(\log_2N) +
O(N^{-1/2+\varepsilon}), \nonumber 
\end{eqnarray}
where
\begin{eqnarray}  
D_d -C_d^2\sim {1\over 12} + O(d^{-1/2+\eps}) 
\ \ \ \ \ \ \hbox{as} \ \ \
d\con \infty ~.
\label{e12}
\end{eqnarray}
In particular
\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 \\
&\sim& -C_d -1/6 +\log_2^2d +O(d^{-1/2+\eps}) \ \ \ \ \hbox{as} \ \ \
d\con \infty ~,
\label{e13}
\end{eqnarray}
and $P_2(x)$ is a periodic function with 
period 1.  \eod
\end{theorem}

Using numerical integration, we computed for the first few values
of  $d$  the constants $ER_{N,d}-\log_2N-P_1(\log_2N)$ and
$\var~ R_{N,d} -P_2(\log_2N)$. They are displayed in the 
table below. We note that the variance decreases substantially
for initial values of $d$ ($d\leq 2$) and then the decrease slows
down. From the table, one may conclude that $d\geq 5$
is a good  practical choice. 
\begin{table}[h]
\caption{Performance of the algorithm for small values of $d$
(neglecting fluctuations).}
\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}
\par
Our technique also allows to deal with the limiting distribution for $R_{N,d}$
and the limiting generating function. For this, we introduce 
the Poisson transform of $F_N(z)$ as
\begin{equation}
G(z,x)= e^{-x} \sum_{N=0}^\infty F_N(z){x^N\over N!} ~.
\label{e14}
\end{equation}
Then, after some algebra, one proves that $H(z,x)=G(z,x)-1$ satisfies
the following recurrence
\begin{equation}
H(z,x)=2f_d(x/2)H(z,x/2)+(z-1)f_d(x/2) ~,
\label{e15}
\end{equation}
which falls into our general functional equation (\ref{e6}).
In  particular, as above we can write a solution for $H(z,x)$ as
\begin{equation}
\varphi(x) H(z,x)= (z-1) \sum_{n=0}^\infty z^n \varphi(x2^{-n-1}) ~,
\label{e16}
\end{equation}
where $\varphi(x)$ is defined in (\ref{e8}). 

With the help of (\ref{e16}), we are able to derive the limiting generating 
function for $F_N(z)$ as $N$ becomes large. 




\begin{theorem}
Consider the probabilistic counting algorithm as
in Theorem 1.
For large $N$ the limiting generating function becomes
\begin{equation}
F_N(z) \sim z^{\log_{2} N} \varphi^*(- \log_2 z)/L +
P_3(\log_2N) +O(N^{-1/2+\varepsilon}) ~.
\label{e17}
\end{equation}
where $\varphi^*(s)$ is the Mellin transform of 
$\varphi(x)$ defined in (\ref{e8}).
\eod
\end{theorem}

In addition, in Section 3, 
we will present a conjecture (\ref{e29}) 
concerning
the limiting distribution for $R_{N,d}$.
Details and more precise statements are left to a journal version of the
paper.

For the reader's convenience we want to point out that the definition
and basic properties of the {\it Mellin integral transform}
are included in the paper \cite{usch} by U. Schmid {\it in this volume}.
\med

\noi
{\bf Remarks}
\par
(i) {\it Special Cases}. As mentioned before, the case $d=0$
was analyzed by Flajolet and Martin \cite{fm}. In addition,
Greenberg {\it et al.} \cite{gfl} 
investigated the function $\varphi(x)$ for $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}. We note that our analysis
is based on a quite different approach, namely, functional
equations, and  can be proved very successful for some
other algorithms (cf. Remark (iii)).
\par
\medskip
(ii) {\it Convergence in Probability}.  Theorem 1 implies
that $R_{N,d}$ converges {\it in probability} (pr.) to
$ER_{N,d}$. More precisely, by Theorem 1 and 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}} \sim {const \over \log^2_2N} \con 0$$
as $N\con \infty$.  This proves the announced convergence.
It is not clear, however,  whether one can
extend this convergence to the {\it almost sure}
convergence. 

\medskip
(iii) {\it Other Problems}. As mentioned in the abstract,
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. A good
representation of such a splitting process is a digital
tree (i.e., a trie \cite{knuth}). 
For example, consider a multiaccess system with a large number
of users. The following ``conflict resolution" algorithm found to be
very 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}) and its solution (\ref{e9}).
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 obtain some asymptotics. Finally,
several other problems fall into the ``splitting process"
scenario. We mention here: selecting the loser \cite{prodinger},
estimating the number of questions necessary to identify the
number of distinct objects \cite{pittel}, selecting $d$
finalists in a contest where questions are answered randomly,
and so forth.  


\section{Analysis}

In this section we present a sketch of proof for Theorem 1. We also
offer some remarks regarding Theorem 2.
\par
We start with the average value $ER_{N,d}$. Its modified exponential
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!$.
Iterating this equation, as in (\ref{e6}) -- (\ref{e9}), we finally obtain
\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) ~,
\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 an 
asymptotic behavior of $\TL(z)$
as $z\con \infty$, and then by {\it depoissonization} \cite{js}
to evaluate the coefficients $ER_{N,d}$ of $L(z)$. 
To obtain the asymptotics of $\TL(z)$ we apply the Mellin transform
technique (cf. \cite{frs} and \cite{fo}).
We shall use the
following depoissonization lemma proved in Rais, Jacquet and Szpankowski
\cite{rjs}. (An older and less versatile version of the depoissonization
lemma may be found in
Jacquet and Szpankowski \cite{js}.)

\medskip
\noindent
{\bf Depoissonization Lemma}\ \sl
Let $S_\theta$ be a cone 
$S_\theta=\{z:~ |{\rm arg} z| < \theta~,~ 0<\theta<\pi/2\}$.
If for $z\in S_\theta$ and $z\con \infty$ the following holds for all
$u$ in a compact set $\cal U$
\begin{equation}
|D(z,u)|<\beta_1|z|^\varepsilon
\label{e22}
\end{equation}
for some $\beta_1, \varepsilon>0$, and for $z\not\in S_\theta$ and 
all $u\in \cal U$
\begin{equation}
\left|D(z,u)e^z\right|<\beta_2|z|^\varepsilon e^{\alpha |z|}
\label{e227}
\end{equation}
for some $0<\alpha <1$ and a constant $\beta_2>0$, then for large $n$
uniformly in $u\in \cal U$ the generating function $D_n(u)
=[z^n/n!]D(z,u)e^z$ satisfies
\begin{equation}
D_n(u)=D(n,u)+O(n^{-1/2+\varepsilon})
\label{e24}
\end{equation}
with $\varepsilon<1/2$.  \eod
\rm
\medskip


Using the above idea, we first apply the Mellin transform to
(\ref{e20}). 
Let $Q_1(z)=\TL(z)\varphi(z)$ and $Q_1^*(s)$ be 
its Mellin transform. Since
the sum in (\ref{e20}) is a harmonic sum, we have (cf. \cite{frs})
\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 $\varphi^*(s)$ is the Mellin transform of $\varphi(z)$, and
$\varphi^*(s)=\Phi^*(s)/(2^{-s}-1)$. Note that $\Phi^*(s)$ is an
entire function (cf. \cite{gfl}). Using the inverse of the Mellin
transform (by computing the residues of $Q_1^*(s)$) 
and $\varphi(z)\sim 1+O(z^{-M})$, 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 \cite{fo} or some Tauberian theorems. Details
%are left for a journal version of this paper.}
for $z\con \infty$ 
\begin{equation}
\TL(z) \sim \log_2 z \cdot {\Phi^*(0) \over L} -{\Phi^*(0) \over L}-
{\Phi^{*\prime}(0) \over L^2} +P(z)
\label {26}
\end{equation}
where
$$
\Phi^*(0)=\int_0^\infty e^{-x}e_d(x)\varphi(2x){dx\over x} ~,
$$
$$
\Phi^{*\prime}(0)=\int_0^\infty e^{-x}e_d(x)\varphi(2x){\log x\over x} dx ~,
$$
and $P(z)$ is a fluctuating function with a small amplitude.
\par
We need to evaluate $\Phi^*(0)$ and $\Phi^{*\prime}(0)$. The former
is rather easy, and by properties of the Mellin transform
we find out that $\Phi^*(0)=L=\log 2$. The latter quantity
is harder to estimate. To do so, we first present another evaluation
of $\Phi^*(0)$ which can be extended to obtain
$\Phi^{*\prime}(0)$. 
Note that $\varphi(2x)-\varphi(x)=e^{-x}e_d(x)\varphi(2x)$.
Define also a function $\1(x)$ as follows 
$$
\1(x)=\left\{\begin{array}{ll}
1& \mbox{if $x\geq 1$} \\
0&\mbox{if $x<1$} ~.
\end{array}
\right.
$$
Then, we can write
\begin{eqnarray*}
\Phi^*(0)&=&\int_0^\infty (\varphi(2x)-\varphi(x)){dx\over x}\\
&=&\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}^\infty {dx\over x}=L ~.
\end{eqnarray*}
\par
In a similar manner we can deal with $\Phi^{*\prime}(0)$. This time,
however, the calculation is more involved. Nevertheless, we obtain
the following
\begin{eqnarray*}
\Phi^{*\prime}(0)&=&-L^2/2-L \int_0^\infty (\1(x)-\varphi(x)){dx\over x} \\
&=&\int_0^1\varphi(x){dx\over x}+\int_1^\infty(\varphi(x)-1){dx\over x} \\
&\sim& O(d^{-1/2}) - \int_1^\infty e_d(x)e^{-x}{dx\over x} \ \ \ \ \
d\con \infty
\end{eqnarray*}
where the last integral can be analyzed using the {\it incomplete
gamma} function. In particular, we can prove that for $d\con \infty$
we have
$C_d={1\over L^2} \Phi^{*\prime}(0)=\log_2 d -1/2+O(d^{-1/2+\eps})$.
Finally, using the Depoissonization Lemma we establish 
Theorem 1(i).  
\par
The proof of Theorem 1(ii) concerning the 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 2 (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 the 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 
asymptotics of $\TW(z)$, and also $F_N^{\prime\prime}(1)$,
we proceed as before through the Mellin transform and 
depoissonization. Let $Q_2(z)$ and $Q_2^*(s)$ denote respectively
the RHS of (\ref{e28}) and its Mellin transform.
Then,
$$
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. Computing residues of
the above, one immediately proves for $z \con \infty$
$$
Q_2(z) \sim \log_2^2 z -(3+2C_d)\log_2 z +2+3C_d+D_d+ P(\log_2z)
$$
where $C_d$ was defined before, 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 ~.
$$
We can analyze $D_d$ in the same manner as before.
After some algebra we arrive at
\begin{eqnarray*}
D_d &\sim& C_d-1/6+2/L^2 \int_1^\infty e_d(t)e^{-t} {\log t 
\over t} dt \\
&\sim& C_d - 1/6+\log_2^2 d +O(d^{-1/2+\eps})
\end{eqnarray*}
as $d\con \infty$. After applying the Depoissonization Lemma,
we complete the proof of Theorem 1(ii).
\par
The limiting generating function $\lim_{N\con \infty} F_N(z)$
can be analyzed in the same manner as above but this
time the
solution (\ref{e16}) should be used to
derive  Theorem 2.

With regard to  the limiting distribution 
the Depoissonization Lemma applied to the bivariate function $H(z,x)$
expressed as in (\ref{e16}) strongly suggests 
\begin{equation}
\varphi\left(2^{-t-1-\{\log_2N+t\}}\right)
\label{e29}
\end{equation}
as an approximation for
$
\pr\{R_{N,d}-\log_2N>t\}
$ for $t$ fixed and $N\con\infty$. 
(In the expression (\ref{e29}) $\{x\}$ denotes the fractional part of
$x$.) 
The fluctuating term is due to the fact
that a discrete parameter is approximated by a continuous function.
Detailed derivations are left to a journal version
of the paper.

\bigskip

{\bf Acknowledgment.} The first two
authors want to thank M. Drmota and P.~Grabner
for interesting discussions.

\begin{singlespace}

\begin{thebibliography}{99}

\small

\bibitem{bb}
G. Brassard and P. Bratley,
{\it Algorithmics. Theory and Practice},
Prentice Hall, Englewood Cliffs, 1988.
\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{fo}
P. Flajolet and A. Odlyzko,
Singularity Analysis of Generating Functions,
{\it SIAM J. Disc. Methods}, 3, 216-240, 1990.
\bibitem{fla}
P. Flajolet and B. Richmond,
Generalized Digital Trees and Their Difference-Differential Equations,
{\it Random Structures and Algorithms}, 3,  1992, in press.
\bibitem{frs}
P. Flajolet, M. R\'{e}gnier and R. Sedgewick,
Some Uses of the Mellin Transform Techniques in the
Analysis of Algorithms,
in
{\it Combinatorial Algorithms on Words},
Springer NATO ASI Ser. F12, 241-254, 1985.
\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{js}
P. Jacquet and W. Szpankowski,
Ultimate Characterizations of the Burst Response of an Interval Searching
Algorithm: A Study of a Functional Equations,
{\it SIAM J. Computing}, 18, 777-791, 1989.
\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{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{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{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 Mathematics}, to appear.
\bibitem{rjs} 
B. Rais, P. Jacquet, and W. Szpankowski, Limiting Distribution for the
Depth in Patricia Tries, {\it SIAM Journal on Discrete Mathematics}, 
to appear.
\bibitem{usch}
U. Schmid, The Average CRI-length of a Tree Collision Resolution
Algorithm in Presence of Multiplicity-Dependent Capture Effects,
{\it this Volume}.
\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}



