%In  Computing 


\input amstex
\documentstyle{amsppt}


\redefine\ll{\lambda}
\define\mean{\left[P_1^2\right]_0}



\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\tenit Order Statistics and Probabilistic Counting
 \hfil\tenrm\number\pageno}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13

\font\sc=cmcsc8









\topmatter
\title
A RESULT IN ORDER STATISTICS \\
RELATED TO \\
PROBABILISTIC COUNTING
\endtitle
\author
Peter Kirschenhofer and Helmut Prodinger
\endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address{Department of Algebra and Discrete Mathematics\newline
TU Vienna\newline
 Wiedner Hauptstra\ss e 8-10/118\newline A-1040 Vienna\newline Austria}
\endaddress
\abstract
Considering geometrically distributed random variables the $d$-maximum
of these events is investigated, i.e. the $d$-th largest element
(with repetitions allowed). The quantitative behaviour of expectation
and variance is analyzed thoroughly. In particular the asymptotics of the
variance for $d$ getting large is established by means of nontrivial 
techniques from combinatorial analysis and complex variable theory.
These results apply to probabilistic counting algorithms, where
the cardinalities of large sets are estimated.
\bigskip
\flushpar
{\sc Zusammenfassung.} Bez\"uglich geometrisch verteilter zuf\"alliger
Ver\"anderlicher wird das $d$-Maximum solcher Ereignisse studiert, also
das $d$-gr\"o\ss te Element, wobei Wiederholungen erlaubt sind. Das
quantitative Verhalten von Erwartungswert und Varianz wird ausgiebig
analysiert. Insbesondere wird das Verhalten der Varianz f\"ur gro\ss e
$d$ mit Hilfe nichttrivialer Techniken aus Kombinatorik und komplexer
Analysis untersucht. Diese Resultate haben Anwendungen bei probabilistischen
Z\"ahlalgorithmen, die zur Sch\"atzung der Kardinalit\"aten  gro\ss er
Mengen verwendet werden.





\endabstract
\endtopmatter



\document

%\rightline{April 23, 1992}

\heading
1. Introduction
\endheading

{\sl Szpankowski and Rego} \cite{14} have considered $n$ independently
and identically distributed geometric random variables
$X_1,\dots,X_n$. Their parameter
of interest was the maximum, $\operatorname{max}\{X_1,\dots,X_n\}$. 

The aim of this paper is threefold:
\roster

\item"{$\bullet$}"
A slightly more direct approach will be used to this problem;\linebreak 
{\sl Szpankowski and Rego} set up  recurrences for the expectation and
the second moment. These recurrences
are solved by {\sl generating function techniques}. 
This is somewhat superfluous as we can directly compute the probabilities
for these {\sl max}--statistics.

\item"{$\bullet$}"
In the main part the following 
generalization will be considered: Let $d\ge 1$ be an integer.
We consider the $d$--maximum, i.e. the $d$--th largest element (with
repetitions allowed). ($d=1$ is the maximum.)
To  be more precise, if there are numbers
$x_1,\dots,x_n$ and we sort them in descending order as
$y_1\ge \dots \ge y_n$, then the  $d$--maximum 
$\operatorname{max}_d\{x_1,\dots,x_n\}$ is $y_d$.
 It will turn out, that, by choosing
$d$ to be large, the variance can be made quite small. 
We will give quantitative asymptotic results. 
This is a nontrivial task since the expectation contains periodic
fluctuations which give an essential contribution to the variance.

\item"{$\bullet$}" 
An important observation is the {\sl application\/} of these
results to {\sl probabilistic counting}, \cite 2. Without going into
details, $n$ data values produce an infinite {$0,1$--string} with only finitely 
many 1's, looking like
$$
1\,1\,1\dots1\,
 \text{{\bf 0}} \, \sigma\, \sigma\, \sigma\dots\sigma
\, \text{{\bf 1}}\, 0\, 0\, 0\dots,
$$
where $\sigma\in\{0,1\}$. 
The region between the first 0 and the last 1 is called the
{\sl fringe}. The parameter $R_n$ to estimate $\log_2n$, used by
{\sl Flajolet and Martin}, is the {\sl index of the first 0}. This parameter
may by analyzed according to very delicate observations, compare
\cite 2, \cite 9 and \cite {11}.
 The index of the last 1 is just {Szpankowski and
Rego's } parameter  minus $1$ (assuming 
equal probabilities for 0 and 1). (One has to subtract 1 since
the indices in the string start with 0 and the geometric random variable 
takes only values $\ge 1$.)  It is less accurate
than the original one used by {\sl Flajolet and Martin}, but with
the parameter $d$, e.g. for $d=3$, we can beat $R_n$ with 
respect to the variance. However, in 
\cite 2 there
are also other variations reported in order to make the variance small.
Nevertheless we mention that even an arbitrarily small variance cannot
compensate the effect of approximating a discrete quantity by a continuous
one.
Furthermore it should be stated explicitely that the applicability is somehow
limited in the following sense. The original algorithm of Flajolet and
Martin can be used to compute the cardinality of a multiset. This is
especially useful in database applications when the number of
different elements in the union of several databases is of interest.
For $d\ge2$ this doesn't  work well, because the $d$-maximum is sensitive
(though not much) to multiple appearences of the same element.

\endroster

\heading
2. Expectation and Variance
\endheading

Let $X$ be a random variable distributed according to the geometric
distribution with parameter $p$; as usual, set $q=1-p$. It is convenient
to define $Q=q^{-1}$ and $L=\log Q$. Then, 
\define\Prob{\operatorname{Prob}}
$\Prob \{X\le k\}=1-q^k$ and $\Prob\{X>k\}=q^k$. Therefore
\redefine\max{\operatorname{max}}
$$
\aligned
&\Prob\left\{\max_d\{X_1,\dots,X_n\}\le k\right\}\\
&=\sum_{\lambda=0}^{d-1}\Prob\{\lambda \text{ elements are }> k
\text{ and the others are }\le k\}\\
&=\sum_{\lambda=0}^{d-1}\binom n\lambda q^{k\lambda}\left(1-q^k\right)
^{n-\lambda}.
\endaligned
$$
Let $E_n^{(d)}$ be the {\sl expectation} of the $d$--maximum. We have
$$
\aligned
E_n^{(d)}&=\sum_{k\ge 0}\Prob\left\{\max_d\{X_1,\dots,X_n\}>k\right\}\\
&=\sum_{k\ge 0}
\left[1-\sum_{\lambda=0}^{d-1}\binom n\lambda q^{k\lambda}\left(1-q^k\right)
^{n-\lambda}\right]
\endaligned
$$
We expand $\left(1-q^k\right)^{n-\lambda}$ according to the binomial theorem, 
interchange the sums and combine the ``1" with the instance
$\lambda =0$ to get
$$
E_n^{(d)}=
-\sum_{i=1}^n\binom ni (-1)^i\frac{1}{1-q^i}-
\sum_{\lambda =1}^{d-1}\binom n\lambda
\sum_{i=0}^{n-\lambda}\binom {n-\lambda}i (-1)^i\frac{1}{1-q^{\lambda+i}}.
$$
Observe that the first sum is just $E_n^{(1)}$.
Alternating sums of the type
$$
\sum_{k=s}^n \binom nk \, {(-1)}^k f(k)
$$
are most easily evaluated asymptotically by {\sl Rice's method}, compare
\cite{5}:
\proclaim{Lemma 1} 
Let $\Cal C$ be a curve surrounding the points $s,s+1,\dots,n$ 
$(s\in\Bbb{N})$
in the complex plane and let $f(z)$ be analytic inside $\Cal C$. Then
$$
\sum_{k=s}^n \binom nk \, {(-1)}^k f(k)=
-\frac 1{2\pi i} \int_{\Cal C} [n;z] f(z) dz, 
$$
where
$$
[n;z]=\frac{(-1)^{n-1} n!}{z(z-1)\dots(z-n)}.\qed
$$
\endproclaim

This lemma is useful, because the integral may be asymptotically 
evaluated by collecting the residues of $[n;z]f(z)$ with $\Re z<s$.
Consider the instance of Szpankowski and Rego,
$$
E_n^{(1)}=-\sum_{i=1}^n\binom ni (-1)^i\frac{1}{1-Q^{-i}}
=\sum_{i=1}^n\binom ni (-1)^if(i)
$$
with
$$
f(z)=-\frac{1}{1-Q^{-z}}.
$$
At $z=0$, the local expansion looks like
$$
f(z)\sim -\frac{1}{Lz}\left(1+\frac{Lz}{2}\right).
$$
The quantity $[n;z]$ has also a pole at $z=0$;
$$
[n;z]\sim -\frac{1}{z}\Big(1+zH_n\Big)
$$
with a {\sl harmonic number} $H_n=1+\frac 12+\dots+\frac 1n$.
The residue is
\footnote{$[z^n]f(z)$ denotes the coefficient of $z^n$ in the
(Laurent-) series $f(z)$.}
$$
\left[z^{-1}\right]\frac{1}{Lz}\left(1+\frac{Lz}{2}\right)
\frac{1}{z}\Big(1+zH_n\Big)=\frac 12+\frac{H_n}{L}.
$$

Observe that $H_n\sim \log n+\gamma$.

There are also simple poles at $z=\chi_k=\frac{2k\pi i}{L}$, 
$k\in\Bbb Z\setminus\{0\}$ with residue
$$
-\frac{[n;\chi_k]}{L}\sim -\frac 1L\Gamma(-\chi_k)n^{\chi_k}
\qquad (n\to\infty).
$$
Collecting all residues
we obtain again the result from Szpankowski and Rego:

\proclaim{Theorem 2} 
$$
E_n^{(1)}\sim \log_Qn+\frac{\gamma}{L}+\frac 12 +P_1\left(\log_Qn\right)
$$
where $P_1(x)$ is a continuous  periodic function of period 1,
mean zero, small amplitude and Fourier expansion
$$
P_1(x)=-\frac 1L\sum_{k\ne 0}\Gamma\left(-\chi_k\right)e^{2\pi i kx}.\qed
$$
\endproclaim
To perform the generalization to the general case we only have to consider
the extra terms
$$
-\sum_{\lambda =1}^{d-1}\binom n\lambda
\sum_{i=0}^{n-\lambda}\binom {n-\lambda}i (-1)^i\frac{1}{1-Q^{-\lambda-i}}.
$$
To this end, let $N:=n-\lambda$ and consider
$$
\sum_{i=0}^{N}\binom {N}i (-1)^if(i),
$$
with
$$
f(z)=\frac{1}{1-Q^{-\lambda-z}}.
$$
Now there is only a simple pole at $z=-\lambda$. We find immediately that
$$
\operatornamewithlimits{Res}_{z=-\lambda}[N;z]\frac{1}{1-Q^{-\lambda-z}}
=\frac{1}{L}\frac{N!(\lambda-1)!}{(N+\lambda)!}.
$$
Therefore the correction is (apart from the fluctuations) asymptotic to
$$
-\frac 1L\sum_{\lambda =1}^{d-1}\binom n\lambda
\frac{(n-\lambda)!(\lambda-1)!}{n!}=-\frac 1LH_{d-1}.
$$
Hence we have 
\proclaim{Theorem 3} As $n\to\infty$, we have
$$
E_n^{(d)}\sim \log_Qn+\frac{\gamma}{L}+\frac 12 -\frac 1L
H_{d-1}+P_1\left(\log_Qn\right)
$$
where $P_1(x)=P_{1,d}(x)$ is a continuous  periodic function of period 1,
mean zero, small amplitude and Fourier expansion
$$
P_1(x)=-\frac 1L\sum_{k\ne 0}e^{2\pi i kx}\Gamma\left(-\chi_k\right) 
\left(1+\sum_{\ll=1}^{d-1}\frac{(\ll-1-\chi_k)_\ll}{\ll !}\right).\qed
$$
\endproclaim
With regard to the variance we start with the second moment, which
is easily computed as
$$
\aligned
&\sum_{k\ge 0}(2k+1)
\left[1-\sum_{\lambda=0}^{d-1}\binom n\lambda q^{k\lambda}\left(1-q^k\right)
^{n-\lambda}\right]\\
&=-\sum_{i=1}^n\binom ni(-1)^i
\frac{1+Q^{-i}}{\left(1-Q^{-i}\right)^2}\\
&-\sum_{\lambda=1}^{d-1}\binom n\lambda
\sum_{i=0}^{n-\lambda}\binom {n-\lambda}i(-1)^i
\frac{1+Q^{-\lambda-i}}{\left(1-Q^{-\lambda-i}\right)^2}.
\endaligned
$$
Let's start with the main term
$$
\sum_{i=1}^n\binom ni(-1)^if(i)
$$
with
$$
f(z)=-\frac{1+Q^{-z}}{\left(1-Q^{-z}\right)^2}.
$$
At $z=0$ there is altogether a triple pole; we have
$$
f(z)\sim-\frac{2}{L^2z^2}
\left(1+\frac{Lz}{2}+\frac{L^2z^2}{6}\right).
$$
Also,
$$
[n;z]\sim -\frac 1z
\left(1+zH_n+z^2\frac{H_n^2+H_n^{(2)}}{2}\right),
$$
(with $H_n^{(2)}=\sum_{k=1}^n\frac{1}{k^2}$, a harmonic number of order 2)
and the residue of $[n;z]f(z)$ is
$$
\aligned
&\frac{H_n^2}{L^2}+\frac{H_n^{(2)}}{L^2}+\frac{H_n}{L}+\frac 13\\
&\sim \log_Q^2n+\frac{2\gamma\log_Qn}{L}+\frac{\gamma^2}{L^2}
+\frac{\pi^2}{6L^2}+\log_Qn+\frac\gamma L +\frac 13.
\endaligned
$$
For the correction, consider (with $N=n-\lambda$)
$$
\sum_{i=0}^N\binom Ni(-1)^if(i)
$$
with
$$
f(z)=\frac{1+Q^{-\lambda-z}}{\left(1-Q^{\lambda-z}\right)^2}.
$$
At $z=-\lambda$ there is a double pole; with $w=\lambda+z\to 0$ we have
$$
f(z)\sim \frac{2}{L^2w^2}\left(1+\frac{Lw}{2}\right).
$$
Furthermore,
$$
[N;z]\sim \frac{N!(\lambda-1)!}{(N+\lambda)!}
\Big[1+w\left(H_{N+\lambda}-H_{\lambda-1}\right)\Big],
$$
and the residue of $[N;z]f(z)$ at $z=-\lambda$ is
$$
\frac{N!(\lambda-1)!}{(N+\lambda)!}
\frac{2}{L^2}\left(\frac L2+H_{N+\lambda}-H_{\lambda-1}\right).
$$
We can sum this up as follows:
$$
\aligned
&-\sum_{\lambda=1}^{d-1}\binom n\lambda 
\frac{(n-\lambda)!(\lambda-1)!}{n!}
\frac{2}{L^2}\left(\frac L2+H_{n}-H_{\lambda-1}\right)\\
&=-\sum_{\lambda=1}^{d-1}\frac 1\lambda
\left(\frac 1L+\frac{2}{L^2}H_n-\frac{2}{L^2}H_{\lambda-1}\right)\\
&=-\frac 1L H_{d-1}-\frac{2}{L^2}
H_nH_{d-1}+\frac{H_{d-1}^2}{L^2}-\frac{H_{d-1}^{(2)}}{L^2}
\endaligned
$$
Altogether we find for the second moment (apart from the fluctuations)
the asymptotic equivalent
$$
\aligned
&\log_Q^2n+\frac{2\gamma\log_Qn}{L}+\frac{\gamma^2}{L^2}
+\frac{\pi^2}{6L^2}+\log_Qn+\frac\gamma L +\frac 13\\
&-\frac 1LH_{d-1}-\frac{2H_{d-1}}{L}\log_Qn
-\frac{2H_{d-1}}{L^2}\gamma+\frac{H_{d-1}^2}{L^2}-\frac{H_{d-1}^{(2)}}{L^2}.
\endaligned
$$
Now for the variance we must subtract the square of the expectation. There
are many terms cancelling, and we end up with

\proclaim{Proposition 4} The variance $V_n^{(d)}$ fulfills
$$
V_n^{(d)}\sim \frac{\pi^2}{6L^2}+\frac{1}{12}-\frac{H_{d-1}^{(2)}}{L^2}
-\left[P_1^2\right]_0+P_2\left(\log_Qn\right). \qed
$$
where $P_2(x)$ is a continuous periodic function of period 1 and mean 0, and
$\left[P_1^2\right]_0$ is the ``mean'' of the square of the function
$P_1(x)$ from Theorem 3.
\endproclaim

\heading
3. An Analysis of the Function $P_1(x)$
\endheading

First, by the elementary formula
$$
\sum_{k=0}^r\binom{k+a}k=\binom{r+a+1}r,
$$
we may rewrite
$$
P_1(x)=-\frac 1L\sum_{k\ne 0}e^{2\pi i kx}\Gamma\left(-\chi_k\right) 
\sum_{\ll=0}^{d-1}\frac{(\ll-1-\chi_k)_\ll}{\ll !}
$$
as
$$
P_1(x)=-\frac 1L\sum_{k\ne 0}e^{2\pi i kx}\Gamma\left(-\chi_k\right) 
\binom{d-1-\chi_k}{d-1}.
$$
Therefore the mean $\left[P_1^2\right]_0$ of $P_1^2(x)$ is
$$
\mean=\frac{1}{L^2}\sum_{k\ne 0}\left|\Gamma\left(-\chi_k\right)\right|^2
\binom{\chi_k-1}{d-1}\binom{-\chi_k-1}{d-1};
$$
it is this quantity that we are going to study thoroughly in this section.

\proclaim{Lemma 5} $\displaystyle{
\binom{a-1}{n}\binom{-a-1}{n}=\sum_{k=0}^n\binom{a}{k}\binom{-a}{k}
}$
\endproclaim
\demo{Proof}
We use Euler's first identity for hypergeometric series \cite 7, \cite 8
$$
{_2F_1}(c-a,c-b;c;x)={_1F_0}(c-a-b;x)\, {_2F_1}(a,b;c;x)
$$
in the special instance $c=1$, $b=-a$ where it takes the form
$$
\sum_{n\ge 0}\frac{(1-a)^{(n)}(1+a)^{(n)}}{n!^2}x^n=
\frac{1}{1-x}\sum_{n\ge 0}\frac{a^{(n)}(-a)^{(n)}}{n!^2}x^n
$$
with the Pochhammer symbol $ a^{(n)}=a(a+1)\dots (a+n-1)$.
Now comparing the coefficients of $x^n$ and
observing that
$$
\frac{(1-a)^{(n)}(1+a)^{(n)}}{n!^2}=\binom{n-a}{n}\binom{n+a}{n}
=\binom{-a-1}{n}\binom{a-1}{n}
$$
resp.
$$
\frac{a^{(k)}(-a)^{(k)}}{k!^2}
=\binom{a+k-1}{k}\binom{-a+k-1}{k}=\binom{-a}{k}\binom{a}{k}
$$
gives the desired identity. \qed
\enddemo

{\bf Remark.} Once the formula is {\sl known}, it may of course also
be proved by induction.

\smallskip

An immediate consequence is the formula
$$
\mean=\frac{1}{L^2}\sum_{j=0}^{d-1}\frac{1}{j!^2}\sum_{k\ne 0}
\left|\Gamma\left(j-\chi_k\right)\right|^2.
$$
The following lemmata evaluate the inner sums. A proof for the special
instance $Q=2$, using series transformation results due to Ramanujan, is
given in \cite{10}. In the Appendix, we sketch an alternative proof
for general $Q>1$
using the Mellin transform combined with the residue calculus.

\proclaim{Lemma 6} If $j\ge 1$, 
$$
\align
\sum_{k\ne 0}\Gamma(j+\chi_k)\Gamma(j-\chi_k)
&=2L(2j-1)!\sum_{h\ge 0}\binom{-2j}h\frac{1}{Q^{h+j}-1}\\
&+L(2j-1)!2^{-2j}-(j-1)!^2.
\endalign
$$
\endproclaim

\proclaim{Lemma 7} 
$$
\sum_{k\ne 0}\Gamma(\chi_k)\Gamma(-\chi_k)
=\frac{\pi^2}{6}+\frac{L^2}{12}-L\log 2-2L\sum_{h\ge 1}
\frac{(-1)^{h-1}}{h\left(Q^h-1\right)}
$$
\endproclaim

Now this gives us our final formula which we therefore state as a 
proposition.

\proclaim{Proposition 8}
$$
\align
\mean&=\frac{\pi^2}{6L^2}+\frac{1}{12}-\frac{\log 2}{L}
-\frac 2L \sum_{h\ge 1}
\frac{(-1)^{h-1}}{h\left(Q^h-1\right)}\\
&+\frac{2}{L}\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j
\sum_{h\ge 0}\binom{-2j}h\frac{1}{Q^{h+j}-1}\\
&+\frac 1L\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j 2^{-2j}
-\frac{H_{d-1}^{(2)}}{L^2}
\endalign
$$
\endproclaim

\head
4. Behaviour of the Variance for large $d$
\endhead

Combining  Propositions 4 and 8  we have proved that the main
term of $V_n^{(d)}$ for $n\to\infty$ is given by
$$
\align
&\frac{\log 2}{L}-\frac 1L\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j 2^{-2j}
+\frac 2L \sum_{h\ge 1}
\frac{(-1)^{h-1}}{h\left(Q^h-1\right)}\\&-
\frac{2}{L}\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j
\sum_{h\ge 0}\binom{-2j}h\frac{1}{Q^{h+j}-1}
+P_2(\log_2n)
\endalign
$$
where $P_2(x)$ has mean zero.

In this section we want to analyze the nonfluctuating part of the above 
quantity for $d\to\infty$.

We start with the first sum and prove, as the main step,

\proclaim{Lemma 9}
$$
4^{-j}\frac{1}{2j}\binom{2j}j=
-[t^j]\log \frac{1+\sqrt{1-t}}{2}
$$
\endproclaim
\demo{Proof}
We have
$$
\align
[t^j]\log \frac{1+\sqrt{1-t}}{2}
&=\frac 1j[t^{j-1}]\left(\log 
\frac{1+\sqrt{1-t}}{2}\right)^\prime\\
&=-\frac 12\frac 1j[t^{j-1}]\frac{1}{\sqrt{1-t}\left(
1+\sqrt{1-t}\, \right)}.
\endalign
$$
To find the coefficient in this sum we use the {\sl formal residue
calculus\/}, as described in \cite{6}, with the substitution
$$
t=\frac{4u}{(1+u)^2}\qquad\text{and}\qquad
dt=\frac{4(1-u)}{(1+u)^3}du.
$$
$$
\align
&[t^{j-1}]\frac{1}{\sqrt{1-t}\left(1+\sqrt{1-t}\, \right)}\\
&=[t^{-1}]t^{-j}\frac{1}{\sqrt{1-t}\left(1+\sqrt{1-t}\,\right)}\\
&=[u^{-1}]4^{-j}u^{-j}
(1+u)^{2j}\frac{1+u}{1-u}\frac{1+u}{2}\frac{4(1-u)}{(1+u)^3}\\
&=\frac 12 4^{1-j} [u^{j-1}](1+u)^{2j-1}=\frac 12 4^{1-j}
\binom{2j-1}{j-1},
\endalign
$$
and this is clearly equivalent to the announced formula. \qed
\enddemo

As an immediate consequence of the lemma we get

\proclaim{Proposition 10} As $d\to\infty$,
$$
\frac 1L\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j2^{-2j}
=\frac{\log 2}{L}+\frac{1}{\sqrt\pi}d^{-1/2}+\Cal O(d^{-3/2}).
$$
\endproclaim
\demo{Proof} We have
$$
\align
\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j2^{-2j}
&=-[t^{d-1}]\frac{1}{1-t}\log\frac{1+\sqrt{1-t}}{2}\\
&=[t^{d-1}]\frac{\log 2}{1-t}
-[t^{d-1}]\frac{1}{1-t}\log\left({1+\sqrt{1-t}}\,\right)\\
&=\log 2-[t^{d-1}]\frac{1}{1-t}\log\left({1+\sqrt{1-t}}\,\right)
\endalign
$$
The latter generating function has its dominating singularity at $t=1$
and behaves as
$$
-\frac{1}{1-t}\log\left({1+\sqrt{1-t}}\right)
=\frac{1}{\sqrt{1-t}}+\Cal O\left((1-t)^{-3/2}\right)
\qquad (t\to 1),
$$
so that by {\sl singularity analysis\/} \cite{4} the coefficient of
$t^{d-1}$ behaves like
$$
\frac{1}{\sqrt\pi}d^{-1/2}+\Cal O(d^{-3/2})\qquad (d\to \infty). \qed
$$
\enddemo

It remains to treat the more complicated sum
$$
\Sigma_{d-1}=
\sum_{j=1}^{d-1}\frac{1}{2j}\binom{2j}j
\sum_{h\ge 0}\binom{-2j}h\frac{1}{Q^{h+j}-1}.
$$
Observe
that
$$
\align
\sum_{h\ge 0}\binom{-2j}h\frac{1}{Q^{h+j}-1}
&=
\sum_{h\ge 0}\binom{-2j}h \frac{1}{Q^{h+j}}\sum_{m\ge 0}Q^{(-h-j)m}\\
&=\sum_{m\ge 1}\left(Q^{-m}\left(1+Q^{-m}\right)^{-2}\right)^j.
\endalign
$$
Now it follows from a simple substitution in Lemma 9 that

$$
\frac{1}{2j}\binom{2j}j
\left(\frac{1}{Q^{ m}(1+Q^{-m})^2}\right)^j=
-[t^j]\log
\left(
\frac{1+\sqrt{1-\frac{4t}{Q^m(1+Q^{-m})^2}
}
}{2}
\right).
$$
Therefore we have
$$
\Sigma_{d-1}=-[t^{d-1}]\frac{1}{1-t}
\log \left(
\frac{1+\sqrt{1-\frac{4t}{Q^m(1+Q^{-m})^2}
}
}{2}
\right).
$$
Observing that
$$
\align
\Sigma_\infty&=-\sum_{m \ge 1}
\log \left(
\frac{1+\sqrt{1-\frac{4t}{Q^m(1+Q^{-m})^2}
}
}{2}
\right)\\
&=-\sum_{m \ge 1}
\log \frac{1}{1+Q^{-m}}=\sum_{m \ge 1}
\log \left(1+Q^{-m}\right)
\endalign
$$
we  find by singularity analysis

\proclaim{Proposition 11} For any $\varepsilon>0$, we have for $d\to\infty$
$$
\frac 2L\Sigma_{d-1}=\frac 2L \sum_{m \ge 1}
\log \left(1+Q^{-m}\right)
+\Cal O\left(
\left(\frac{4}{Q(1+Q^{-1})^2}\right)^{d-\varepsilon}
\right)
$$
\endproclaim

The main term coincides with
$$
\frac{2}{L}\sum_{h \ge 1}
\frac{(-1)^{h-1}}{h(Q^h-1)},
$$
whereas, for $Q>1$, the remainder term is exponentially small for 
$d\to\infty$ compared with the remainder term from Proposition 10.
Altogether we have proved:

\proclaim{Theorem 12} The nonfluctuating part of the main asymptotic term of
the variance $V_n^{(d)}$ for $n\to\infty$ behaves for $d\to\infty$ as
$$
\frac{1}{\sqrt\pi}d^{-1/2}+\Cal O\big(d^{-3/2}\big).
$$
\endproclaim

{\bf Remark.} This analysis is of more than local interest; the periodic
function $P_1(x)$ is not uncommon in the {\sl Analysis of Algorithms\/}.
We mention e.g. \cite{13}.





\heading
5. Application to Probabilistic Counting
\endheading

To continue the discussion from the Introduction, let us just mention that 
(by means of a {\sl hash function\/}) 
each data value produces exactly one bit, and it
is in position $k\ge 0$ with probability $2^{-k-1}$. The OR--composition
of all the bits (1's) constitutes the string, as seen in the Introduction.
Now this is exactly a {\sl geometric probability}. 
The result of Flajolet and
Martin states, that (apart from the fluctuations) the 
{\sl average value\/} of
$R_n$ is asymptotic to $\log_2n-0.37$; the Szpankowski--Rego parameter $-1$
has an average of $\log_2n+0.33$, whence we deduce the average size of
the fringe to be less than 1.

 The {\sl variance\/} in the  Flajolet--Martin--instance
 is approximately $1.257$ and in the Szpankowski--Rego--instance 
$3.507$. 

Below we give the limiting values of the variances $V_n^{(d)}$
for $N\to\infty$ and some values of $d$ for the special instance
$q=\frac 12$, i.e. $Q=2$.

$$
\alignat 2
&d&\quad&\lim V_n^{(d)}\\
&1&\quad&3.5070\\
&2&\quad&1.4256\\
&3&\quad&0.9053\\
&4&\quad&0.6740
\endalignat
$$

Finally we mention that from the algorithmic point of view it is easy to
maintain the parameter of interest. It is not even necessary to keep the
whole actual bit string (the OR--composition). It is sufficient to store
the actual $d$ data values with highest entries.



\heading
Appendix
\endheading

As announced in Section 3 we sketch here a derivation of the formula
from Lemma 6 (Lemma 7 can be proved in a quite similar manner).

We start from the left hand side and interpret the sum as the collection
of the residues at the poles $\chi_k$, $k\ne 0$, of the function
$$
L \frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}.
$$
Therefore we have
$$
\align
\sum_{k\ne 0}|\Gamma(j+\chi_k)|^2&=
\frac{L}{2\pi i}\int\limits_{(1/2)}
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}dz\\
&-\frac{L}{2\pi i}\int\limits_{(-1/2)}
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}dz-\Gamma(j)^2.
\endalign
$$
($\Gamma(j)^2$ is the residue at $z=0$.)

Now we use the decomposition
$$
\frac{1}{e^{Lz}-1}=-1-\frac{1}{e^{-Lz}-1}
$$
for the second integral  and get

$$\align
&-\frac{L}{2\pi i}\int\limits_{(-1/2)}
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}dz\\&=
\frac{L}{2\pi i}\int\limits_{(-1/2)}
\Gamma(j+z)\Gamma(j-z)dz
+\frac{L}{2\pi i}\int\limits_{(-1/2)}
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{-Lz}-1}dz\\
&=\frac{L}{2\pi i}\int\limits_{(0)}
\Gamma(j+z)\Gamma(j-z)dz
+\frac{L}{2\pi i}\int\limits_{(1/2)}
\frac{\Gamma(j-z)\Gamma(j+z)}{e^{Lz}-1}dz.
\endalign
$$
Therefore
$$\align
&\sum_{k\ne 0}|\Gamma(j+\chi_k)|^2\\ &=
\frac{2L}{2\pi i}\int\limits_{(1/2)}
\frac{\Gamma(j+z)\Gamma(j-z)}{e^{Lz}-1}dz
+\frac{L}{2\pi i}\int\limits_{(0)}
\Gamma(j+z)\Gamma(j-z)dz-\Gamma(j)^2\\
&=I_1+I_2-\Gamma(j)^2.
\endalign
$$
$I_1$ is evaluated by shifting the contour to the {\sl right\/}
and collecting the {\sl negative\/} residues, which gives
$$
\align
I_1&=-2L\sum_{m\ge j}
\frac{\Gamma(j+m)}{e^{Lm}-1}\frac{(-1)^{j-m+1}}{(m-j)!}\\
\intertext{and with $m=h+j$}
&=2L\sum_{h\ge 0}
\frac{(h+2j-1)!(-1)^h}{h!}\frac{1}{Q^{h+j}-1}\\
&=2L(2j-1)!\sum_{h\ge 0}
\binom{-2j}h  \frac{1}{Q^{h+j}-1}.
\endalign
$$
Integral $I_2$ is of interest for itself and appears already in
early references to the {\sl Mellin transform technique\/} as by Nielsen
\cite{12, p.224}. 

We start with the function
$$
f(x)=\frac{x^j}{(1+x)^{2j}}
$$
and perform its Mellin transform (see, e.g., \cite 3 for definitions)
$$
f^*(s)=\int_0^\infty f(x)x^{s-1}dx=B(j+s,j-s)=
\frac{\Gamma(j+s)\Gamma(j-s)}{\Gamma(2j)}
$$
with the Beta function $B(z,w)$ (compare \cite{1}). The
{\sl fundamental strip\/} is $\langle -j,j\rangle$. Therefore the inversion
formula for the Mellin transform gives
$$
f(x)=\frac{1}{2\pi i}\int\limits_{(0)}
\frac{\Gamma(j+s)\Gamma(j-s)}{\Gamma(2j)}
x^{-s}ds.
$$
Now we may evaluate at $x=1$ and get the
formula
$$
\frac{1}{2\pi i}\int\limits_{(0)}
\Gamma(j+s)\Gamma(j-s) ds=\Gamma(2j)2^{-2j}.
$$
This completes the proof of Lemma 6.









\comment
It is fun to sketch the derivation of the asymptotic series for $H_n^{(2)}$
by means of the Mellin transform, as indicated in \cite{FRS}:
Let
$$
h(x)=\sum_{k\ge 1}\left(\frac{1}{k^2}-\frac{1}{(x+k)^2}\right)=
\sum_{k\ge 1}\frac{1}{k^2}\left(1-\frac{1}{\left(1+\frac xk\right)^2}\right),
$$
then 
$h(n)=H_n^{(2)}$. The Mellin transform $h^*(s)$ is
$$
\aligned
\int\limits_0^\infty h(x)x^{s-1}dx&=\sum_{k\ge 1}\frac{1}{k^2}
k^s\cdot \int\limits_0^\infty\left(1-\frac{1}{(1+x)^2}\right)x^{s-1}dx\\
&=\zeta(2-s)\frac{\pi(s-1)}{\sin \pi s}.
\endaligned
$$
Thus, by the Mellin inversion formula,
$$
h(x)=\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}^{-\frac 12+i\infty}
\zeta(2-s)\frac{\pi(s-1)}{\sin \pi s}ds.
$$
The negative residues of the integrand to the right (at $s=0,1,2,\dots$)
constitute the terms of the asymptotic expansion; they are
(with $B_{2k}$ being Bernoulli numbers)
$$
H_n^{(2)}\sim\frac{\pi^2}{6}-\frac 1n+\frac{1}{2n^2}-
\sum_{k\ge 1}B_{2k}n^{-1-2k}.
$$
\endcomment





\Refs

\ref \no 1 \by M.Abramowitz, I.A.Stegun \book Handbook of Mathematical
Functions \publ Dover \publaddr  New York \yr 1970 \endref

\ref \no 2 \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 3\by P.Flajolet, M.R\'egnier and R.Sedgewick
\paper Some Uses of the Mellin Integral Transform in the
Analysis of Algorithms \book Combinatorics on Words
\publ Springer NATO ASI Series F, Vol. 12 \publaddr Berlin \yr 1985 \endref

\ref \no 4 \by P.Flajolet and A.Odlyzko \pages  216--240\paper
Singularity Analysis of Generating Functions\yr 1990 \vol  3
\jour SIAM J. Disc. Math. 
\endref

\ref \no 5 \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 6\by I.P.Goulden and D.M.Jackson\book Combinatorial Enumeration
\publ John Wiley \& Sons\publaddr New York\yr 1983\endref

\ref \no 7\by R.L.Graham, D.E.Knuth and O.Patashnik \book Concrete Mathematics
\publ Addison-Wesley\publaddr Reading, MA \year1989\endref

\ref\no 8\by P.Henrici \book  Applied and Computational Complex Analysis 
Volume 1 \publ John Wiley \& Sons\publaddr New York\yr 1974\endref


\ref \no 9 
\paper On the Analysis of Probabilistic Counting 
\jour Number Theoretic Analysis, E.Hlawka, R.F.Tichy (Eds.),
Lecture Notes in Mathematics \vol 1452
\yr 1990 \pages 117--120
\by P.Kirschenhofer and H.Prodinger
\endref

\ref \no 10\by P.Kirschenhofer and H.Prodinger 
\paper On Some Applications of Formul\ae of Ramanujan in the 
Analysis of Algorithms
\jour Mathematika \vol 38 \pages 14--33
 \yr 1991 
\endref

\ref \no 11 \paper
How to Count Quickly and Accurately: A Unified Analysis of Probabilistic
Counting and Other Related Problems
\jour ICALP92, W.Kuich (Ed.), Lecture Notes in Computer Science
\vol 623 \pages 211--222 \by P.Kirschenhofer, H.Prodinger and W. Szpankowski
\yr 1992
\endref


\ref\no 12\by N.Nielsen \book Handbuch der Theorie der Gammafunktion\publ
Teubner\publaddr Leipzig\yr 1906
\endref

\ref \no 13   \paper \"Uber l\"angste 1-Teilfolgen in  0-1--Folgen
\jour  in:  Zahlentheoretische  Analysis  II,
E.Hlawka, Ed., Lecture Notes in Mathematics 
\vol 1262 \yr 1987 \pages  124--133
\by H.Prodinger 
\endref

\ref \no 14\by W.Szpankowski and V.Rego \jour Computing
\vol 43\pages 401--410 \yr 1990 \paper Yet another Application of a
Binomial Recurrence: Order Statistics\endref




 

\endRefs

\enddocument

