\input amstex
\documentstyle{amsppt}





\TagsOnRight
\vsize = 19.58 cm
\hsize = 13.33 cm
\topmatter

\title ON THE ANALYSIS OF PROBABILISTIC COUNTING \endtitle
\author Peter Kirschenhofer and Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address{ TU Vienna, Wiedner Hauptstra{\ss}e 8-10, A-1040 Vienna, Austria} 
\thanks{The second author wants to thank M. Drmota for his advice and
patience concerning \TeX.}
\endthanks
\endaddress
\abstract{ In this note an alternative analysis of a probabilistic counting
algorithm due to Flajolet and Martin is presented. The asymptotic evaluation
of certain combinatorial sums is performed via residue calculus instead of 
Flajolet's Mellin transform approach that had to use some unpleasant real
analysis.}
\endabstract

\endtopmatter

\document

\heading 1. Introduction \endheading

A basic probabilistic counting procedure to estimate the number $n$
of distinct elements in a multiset $M$ uses the following idea
(compare \cite{1}): We map the possible domain into the set of sufficiently
long strings of 0 and 1 such that each string is taken as a value of this
mapping with equal probability (a so-called "hash-function"). The bitwise
OR-composition of all the images of the elements of $M$ contains information
on the size of n: the position of the leftmost zero is used as an estimate
of $\log_2 n$. Let $R$ be this quantity. In \cite{1} it is shown 
that the expected value $\overline{R_n}$ of $R$ fulfills

\proclaim {Theorem 1}
$$
\aligned 
\overline{R_n}  &\sim {\log_2 n} + C_1 + \delta_1(\log_2 n)  \\
\text{where}\ 
C_1 &= -\frac 12  + \frac{\gamma}{\log 2} +\log\left( \frac 23 
\prod_{p=1}^\infty \left[ \frac{(4p+1)(4p+2)}{4p(4p+3)}
\right]^{(-1)^{\nu (p)}} \right), \\
\nu (p)&= \text{the number of ones in the binary representation of $p$}, \\
\text{and}\ 
\delta_1(x)&= {1 \over \log 2} \sum_{k\ne 0}
\,\Gamma\left( {2k\pi i\over\log 2} \right)\,
N \left( {2k\pi i\over\log 2} \right),\\
\text{with}\  N(s)&=\ \text{the analytic continuation of}\  
\sum_{j\ge 1} \frac {(-1)^{\nu(j)}} {j^s}.
\endaligned
$$
\endproclaim

We mention that $\delta_1(x)$ is a continuous periodic function of 
period 1 with very small amplitude and mean zero, so that for practical
purposes this periodic fluctuations may be safely ignored.

The variance $\sigma_n^2$ of the random variable $R$ is very small:

\proclaim{Theorem 2}
$$
\sigma_n^2 \sim \frac{\pi^2}{6 \log^2 2} -
\frac{N{'}(0)^2}{\log^2 2} -
\frac{N{''}(0)}{\log^2 2} + \frac 1{12} -[\delta_1^2]_0
+ \delta_2(\log_2 n),
$$
where $N(s)$ is defined in Theorem 1, $[\delta_1^2]_0$ is the mean of
$\delta_1^2(x)$, and $\delta_2(x)$ is again a periodic function of very 
small amplitude and mean zero.

Numerically $$\sigma_n^2 \sim 1.257\ldots\ .$$
\endproclaim

Observe the somewhat erroneous expression for $\sigma_n^2$ in \cite{1}
whereas the numerical approximation therein is correct.

In \cite{1} the Theorems are achieved by evaluating certain combinatorial
sums by the use of Mellin's integral transform.

In this note we gain the results by a more concise method which has 
proved to be successful already in a number of other situations
(\cite{2},\cite{3},\cite{4}). 

\heading 2. The Analysis \endheading

Let $q_{n,k}$ be the probability that for a multiset of $n$ distinct elements
$R\ge k$. In \cite {1} it is shown that
$$
q_{n,k} = \sum_{j=0}^{2^k-1}{(-1)^{\nu (j)} \left( 1- \frac j{2^k}
\right) ^n}.
\tag 1
$$
Observing that
$$
\overline{R_n} = \sum_{l\ge 1}{q_{n,l}}  \tag 2
$$
and
$$
\sigma_n^2=2\sum_{l\ge1}{l\, q_{n,l}} - \overline{R_n} - \overline{R_n}^2,
\tag 3
$$
we have to evaluate certain alternating sums asymptotically.

For $\overline{R_n}$ we have from (2) and (1)
$$
\overline{R_n} = \sum_{k=1}^{n} \binom nk (-1)^k
\sum_{l\ge 1}  \sum_{j=1}^{2^l-1} (-1)^{\nu (j)} \left( \frac j{2^l}
\right)^k,
$$
so that $\overline{R_n}$ is of the form
$$
\overline{R_n} = \sum_{k=1}^{n} \binom nk (-1)^k f(k), \tag 4
$$
with
$$
f(z)=\sum_{l\ge 1} \sum_{j=1}^{2^l-1}(-1)^{\nu (j)}
\left(\frac j{2^l}\right)^z.
$$

Using residue calculus it can be seen that the sum in (4) may be rewritten
as a contour integral:
$$
\overline{R_n}=-\frac 1{2\pi i} \int_{C} [n;z] f(z) dz, 
\tag 5
$$
$$ \text {with}\quad  [n;z]=\frac{(-1)^{n-1} n!}{z(z-1)\cdots (z-n)},$$
where $C$ surrounds the singularities $z=1,2,\dots ,n$ of the integrand.

Expanding the contour of integration in a well-suited manner (compare
\cite 4 for technical details), we find
$$ 
\overline{R_n} \sim \sum \text {Res}_{z=z_i} \Big( [n;z] f(z)
\Big) 
\tag 6 
$$
where the sum is taken over all poles $z_i$ of $[n;z]f(z)$ with real part
larger than some fixed $c$ that differ from $1,...,n$.
 
In our instance we may write
$$ 
f(z)=f_1(z)-f_2(z),
$$
where
$$
\aligned
f_1(z)&=\sum_{l\ge 1} \lim_{k\to\infty}\sum_{j=1}^{2^k-1}
(-1)^{\nu (j)} \left(\frac j{2^l}\right)^z \\
&=\frac 1{2^z-1}N(-z),
\endaligned
$$ 
and
$$
f_2(z)=\sum_{l\ge 1} \lim_{k\to\infty}\sum_{j=2^l}^{2^k-1} (-1)^{\nu (j)}
\left(\frac j{2^l}\right)^z.
$$

From \cite 1 it follows immediately that 
$f_2(z)$ is analytic for $\Re z>-1$
with $f_2(0)=0$.

If we use $c=-\frac 12$ in (6) and take into account the residues at the
poles      
$z=\chi _k =2k\pi i/L$, $k \in \text{\bf Z}$; $L=\log 2$, 
of $[n;z]f_1(z)$ we find:

i) For $z \to 0$
$$
\aligned
\frac 1{2^z-1} &\sim \frac 1{Lz} - \frac 12 ,\\
N(-z) &\sim N(0) - zN'(0), \quad \text {where}\quad N(0)=-1, \\
[n;z] &\sim -\frac 1z - H_n, \quad \text{where}\ 
\quad H_n=\sum_{k=1}^n \frac 1k,
\endaligned
$$
so that
$$
\text{Res}_{z=0}\Big([n;z]f_1(z)\Big) \sim \frac{\log n}L + 
\left(\frac {\gamma}L + \frac{N^\prime(0)}L - \frac 12\right)
$$


ii) For $z \to \chi_k,\quad k\ne 0$
$$
\aligned
\frac 1{2^z-1} &\sim \frac 1{L(z-\chi _k)}, \\
N(-z) &\sim N(-\chi _k),  \\
[n;z] &\sim n^{\chi _k}\Gamma(-\chi _k),
\endaligned
$$
so that
$$
\text{Res}_{z=\chi _k}\Big([n;z]f_1(z)\Big) \sim
\frac 1L N(-\chi _k)\Gamma(-\chi _k)e^{2k\pi i\log_2 n}.
$$

iii) Since $f_2(0)=0$, we have
$$
\text{Res}_{z=0}\Big([n;z]f_2(z)\Big)=0.
$$
Combining these results we rederive Theorem 1.

For the evaluation of $N'(0)$ we use the following formula
$$
N'(0) = \log{\frac 23} + \sum_{p\ge 1} (-1)^{\nu (p)}
\log \frac {(4p+1)(4p+2)} {4p(4p+3)} 
\tag 7
$$
which occurs by grouping terms four by four.

The analysis of the variance follows the same idea.
We have
$$
\sum_{l\ge 1} l\,q_{n,l}=\sum_{k=1}^n\binom nk (-1)^k g(k)
$$
with
$$
g(z)=\frac{2^z}{(2^z-1)^2}N(-z)-g_2(z),
$$
where $g_2(z)$ is analytic for $\Re z > -1$ and fulfills $g_2(0)=0$.

Calculating the residues of
$$
[n;z]\frac{2^z}{(2^z-1)^2}N(-z)
$$
we find that, apart from periodic fluctuations of mean zero,
$$
\aligned
\sum_{l\ge 1} l\,q_{n,l} &\sim \frac 12 \frac{\log^2 n}{L^2}+
\left\{ \frac{\gamma}{L^2} + \frac{N'(0)}{L^2} \right\} \log n \\
&+\frac{\gamma ^2}{2L^2}+ \frac{\pi ^2}{12L^2}+
\frac{\gamma N{'}(0)}{L^2} - \frac{N{''}(0)}{2L^2} - 
\frac 1{12}.
\endaligned
\tag 8
$$
From (8) we gain Theorem 2 immediately.

\Refs

\ref \no 1 \by P. Flajolet and G.N. Martin \pages 182--209
\paper Probabilistic
Counting Algorithms for Data Base Applications \yr 1985 \vol 31 
\jour J. Comput. Syst. Sci. \endref

\ref \no 2 \by P. Flajolet and R. Sedgewick \pages 748--767 \paper
Digital Search Trees Revisited \yr 1986 \vol 15 \jour SIAM J. Comput. 
\endref
 
\ref \no 3 \by P. Kirschenhofer and H. Prodinger \yr 1990 \paper
Approximate Counting: An Alternative Analysis \jour RAIRO
Informatique Th\'eorique \toappear \endref

\ref \no 4 \by U. Schmid \yr 1986 \paper Analyse von Collision-Resolution
Algorithmen in Random-Access- Systemen mit dominanten 
\"Ubertragungskan\"alen
\jour Dissertation TU Wien \endref

\endRefs

\enddocument

