%Inf. Proc. Letters

\input amstex
\documentstyle{amsppt}


\font\sc=cmcsc10
\hfuzz=10pt

\NoRunningHeads
\TagsOnRight
\topmatter
\title
An asymptotic comment on a paper by Analyti and Pramanik
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address \flushpar TU Vienna\newline
Department of Algebra and Discrete Mathematics 
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\keywords Mellin transform
\endkeywords
\email proding\@email.tuwien.ac.at
\endemail
\endtopmatter

\document

In \cite{1} the authors   studied (in the context of a hashing problem)
the quantity
$$
B(b,m)=\frac{1}{\binom{2^b}{m}}\sum_{k=0}^bk\left(\binom{2^k}{m}2^{m(b-k)}
-\binom{2^{k-1}}{m}2^{m(b-k+1)}\right).
$$
They were already successful in approximating $B(b,m)$ by
$$
B(m)=\sum_{k\ge0}k\left(e^{-m^2/2^{k+1}}-e^{-m^2/2^{k}}\right),
$$
but the further analysis of this quantity is not very precise.
The main
interest in this short note is to sketch the (by now classical) asymptotic
evaluation of this sum.  We refer for the necessary details to the brilliant
survey \cite2.

First, it is customary to set $x=m^2$, so that we have
$$
f(x)=\sum_{k\ge0}k\left(e^{-x/2^{k+1}}-e^{-x/2^{k}}\right).
$$
The next step is to compute the Mellin transform
$$
\aligned
f^\ast(s)&=\int_0^\infty f(x)x^{s-1}dx\\& 
=\int_0^\infty e^{-x}x^{s-1}dx\cdot \sum_{k\ge0}k\left({2^{(k+1)s}}-{2^{ks}}\right)\\
&=\Gamma(s)\cdot \left(2^s-1\right)
\sum_{k\ge0}k{2^{ks}}\\
&=\Gamma(s)\cdot \left(2^s-1\right)\frac{2^{s}}{\left(2^s-1\right)^2}\\
&=\Gamma(s)\cdot \frac{2^{s}}{2^s-1}.
\endaligned
$$
The original function $f(x)$ is found from the
tranformed function $f^\ast(s)$ by a contour integral:
$$
f(x)=\frac{1}{2\pi i}\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\Gamma(s)\cdot \frac{2^{s}}{2^s-1}x^{-s}ds.
$$
This function will be evaluated asymptotically (for $x\to\infty$)
by shifting the integral
to the right, and collecting the negative residues.
The pole at $s=0$ is the hardest to handle, since it is a double pole.
Since $\Gamma(s)\sim\frac1s(1-\gamma s)$, 
$\frac{2^{s}}{2^s-1}\sim\frac{1}{s\log2}\big(1+\frac{s\log2}{2}\big)$,
and $x^{-s}\sim 1-s\log x$, 
we find the negative residue at $s=0$ to be
$\log_2x+\frac{\gamma}{\log2}-\frac12$. There are also simple poles at
$s=2k\pi  i/\log2$, with negative residue
$-\Gamma\big(\frac{2k\pi i}{\log2}\big)\frac{1}{\log2}
e^{-2k\pi i\cdot \log_2x}$.
 This gives a contribution
$$
-\frac{1}{\log2}\sum_{k\neq0}\Gamma\Big(-\frac{2k\pi i}{\log2}\Big)
e^{2k\pi i\cdot \log_2x},
$$
where we interchanged $k$ and $-k$ for convenience. If we set 
$$
\delta(x)=\frac{1}{\log2}\sum_{k\neq0}\Gamma\Big(-\frac{2k\pi i}{\log2}
\Big)
e^{2k\pi ix},
$$
we see that $\delta(x)$ is a continuous
periodic function of period 1 and small amplitude. 

Going back to the original
sum $B(m)$, we find the result
$$
B(m)=2\log_2m+\frac{\gamma}{\log2}-\frac12-\delta(2\log_2m)+O\big(\frac
1{m^2}\big).
$$
The authors formula
$$
B(2^{l/2}m)\sim B(m)+l
$$
is thus an easy consequence of our precise asymptotic formula.




\Refs

\ref\no1\by A.Analyti and S.Pramanik\paper Performance analysis of a main
memory multi-directory hashing technique\jour Information Processing
Letters \vol45\yr1993\pages 191--197
\endref

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

\endRefs



\enddocument
