%Letter to the Editor, Inf. Proc. Letters
\documentstyle[11pt]{article}
\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\t{\tilde}
\def\half{{1\over 2}}
\def\med{\medskip\parsec}
\def\binom nk{{n \choose k}}
\def\C{{\cal C}}
\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{\tilde{L}}
\def\Tl{\tilde{l}}
\def\TW{\tilde{W}}
\def\Tw{\tilde{w}}
\def\TT{\tilde{T}}
\def\Tt{\tilde{t}}
\def\TR{\tilde{R}}
\def\Tr{\tilde{r}}
\def\TM{\tilde{M}}
\def\Tm{\tilde{m}}
\def\sech{\text{sech}}
\vsize=8.5in
\voffset=-0.7in
\hoffset=-0.7in
\begin{document}
\begin{center}
{\LARGE Letter to the Editor} \\
\big
%{\bf Comments to ``Reducing Conflict Resolution Time for Solving
%Graph Problems in Broadcast Communications''} \\
%by {\sl Chang-Biau Yang\/}, {\sl Information Processing Letters\/}
%{\bf 40}, 295--302, 1992.
{\bf A Note on Binomial Recurrences Arising in the Analysis of Algorithms}
\end{center}
\par
\bigskip
\noi
\begin{tabular}{l@{\hspace{0.7in}}l}
Helmut Prodinger\footnotemark&Wojciech Szpankowski\footnotemark\\
Department of Algebra\&Discrete Mathematics&Department of Computer Science\\
Technical University of Vienna&Purdue University\\
Vienna A-1040&W. Lafayette, IN 47907\\
Austria&U.S.A.\\
\end{tabular}
\footnotetext[1]{This work is supported by Fonds zur F\"{o}rderung der
Wissenschaftlichen Forschung Project P7497-TEC}
%\footnotetext{This work is supported by Fonds zur F\"{o}rderung der
%Wissenschaftlichen Forschung Project P7497-TEC}
\footnotetext{This research was supported by the NSF Grants INT-8912631,
CCR-8900305 (its extension CCR-9201078) and NCR-9206315,
in part by AFOSR grant 90-0107, and in part by grant R01 LM05118 from the
National Library of Medicine.}
\par
\bigskip\bigskip
Chang-Biau Yang in
``Reducing Conflict Resolution Time for Solving
Graph Problems in Broadcast Communications"
{\it Information Processing Letters\/},
{\bf 40}, 295--302, 1992 analyzed the following recurrence
(we replace the authors notation $C^n_k$ for a binomial coefficient
by the more common $\binom nk$)
%Replacing the unpleasant notation $C^n_k$ for a binomial coefficient
%by the more common $\binom nk$, the author studies (Eq. 2) the recursion
$$
g_n=1+\sum_{k=0}^n2^{1-n}\binom nk g_k \eqno(1)
$$
for $n\ge 2$ and $g_0=g_1=1$.
The author presents a lengthy derivation for
the following bounds on $g_n$:
$$
\frac 83\le\frac{g_n}{n}\le 3
$$
However, such recursions were intensively studied since the appearance of
Knuth's books \cite{knuth} in the context of {\it tries\/},
and have gained more attention in the past few years in the context of
{\it conflict resolution protocols} \cite{mf}, \cite{spa1},
analysis of extendible hashing \cite{flajolet}, \cite{spa3}, and
so forth.
The exact answer to (1) is (cf. \cite{knuth}, \cite{spa1})
$$
g_n=1+\sum_{k=2}^n (-1)^k {n \choose k} {2k-2 \over 1-2^{1-k}} ~. \eqno(2)
$$
Much more can be said. The asymptotic expansion of (2) leads to
(cf. \cite{mf}, \cite{knuth}, \cite{spa1}, \cite{spa3})
$$
g_n=\frac{2}{\log 2}n+ n\delta(\log_2n)+
{\it smaller\ order\ terms} ~, \eqno(3)
$$
where
$\delta(x)$ is a periodic function of period 1, small amplitude, mean 0
and known Fourier coefficients. Note that $2/\log 2= 2.8853\dots\ $.
Computing the variance of the conflict resolution session
(the quantity analyzed by C. Yang) is much harder,
but it can be done using a general methodology explained briefly below.
The difficulty arises from a new sort of recurrence that must be solved.
This recurrence (for the second factorial moment of $g_n$) is
of the following type
$$
h_n=2ng_n+2^{1-n}\sum_{k=0}^n{n \choose k} g_kg_{n-k} -n(n+1)+
2^{1-n}\sum_{k=0}^n{n \choose k} h_k ~. \eqno(4)
$$
The above recurrence is difficult to solve mainly due to the
appearance of $g_n$ (cf. (2)) in the second term above.
But, even the first term is not quite trivial to handle.
In Kirschenhofer, Prodinger and Szpankowski \cite{kps1,kps2} asymptotic
expansions of $h_n$ and the variance (i.e., $h_n+g_n-g_n^2$) are
presented. Such an analysis involves
non trivial identities from the theory of modular functions and Ramanujan's
identities (cf. \cite{kp2}).
The interested reader is referred to the new book of
Hosam Mahmoud \cite{mahmoud} which treats this subject
in a more detailed way.
In this short note we only indicate how (2) and (3) can be obtained.
Consider a general recurrence equation of the following type
$$
x_n=a_n+2^{1-n}\sum_{k=0}^n {n \choose k} x_k \ \ \ \ \ \ n\geq 2 ~,
\eqno(5)
$$
given $x_0$ and $x_1$, where $a_n$ is any sequence.
(For (1) we need to assume that $a_n=1$ and $x_0=x_1=1$.)
In \cite{knuth,spa1,spa2} it is shown that
such a recurrence possesses the following solution
$$
x_n=x_0+\sum_{k=0}^n (-1)^k{n \choose k}{k\bar{x}_1+\hat{a}_k -\bar{x}_0
\over 1-2^{1-k}} \eqno(6)
$$
where $\bar{x}_0=a_0+x_0$ and $\bar{x}_1=a_1+x_0$. The inverse relationship
$\hat{a}_n$ is defined as follows (cf. Knuth \cite{knuth})
$$
\hat{a}_n =\sum_{k=0}^n{n \choose k} (-1)^k a_k ~. \eqno(7)
$$
For example, if $a_n=1$, then $\hat{a}_n=\delta_{n,0}$. Using this,
we can easily obtain solution (2) of the recurrence (1).
The asymptotic expansion of the alternating sum (6) requires some
tools from complex analysis \cite{henrici}.
Consider a general alternating
sum of the following type
$$
x_n=\sum_{k=2}^n (-1)^k{n \choose k} f_k ~,
\eqno(8)
$$
An asymptotic expansion of the above sum can be either obtained by
Rice's method as popularized by Knuth \cite{knuth} and
Flajolet and Sedgewick \cite{fs} (see also \cite{kp})
or by the Mellin-like transform
as shown by Knuth \cite{knuth} and generalized by Szpankowski
\cite{spa2}. We discuss below only the Mellin-like approach.
In Szpankowski \cite{spa2} it is proved that the alternating sum (8) can
be evaluated by the following complex integral
$$
x_n={1\over 2 \pi i} \int_{-3/2-i \infty}^{-3/2+i\infty}
\Gamma(z) n^{-z} f(-z) dz + \hbox{{\it smaller order terms}} ~, \eqno(9)
$$
where $\Gamma(z)$ is the gamma function \cite{henrici},
$f(z)$ is an analytical continuation
of $f_k$, that is, $f(k)=f_k$. The above formula holds under some
mild conditions on the behaviour of $f(z)$ at infinity. In passing, we note
that the integral (9) is usually {\it very easy} to evaluate
asymptotically by
Cauchy's residue theorem \cite{henrici}.
In the case of the recurrence (1) with the explicit solution (2),
we apply (9) to obtain
$$
g_n\sim - {1\over 2 \pi i} \int_{-3/2-i \infty}^{-3/2+i\infty}
{(2z+2) \Gamma(z) n^{-z} \over 1-2^{1+z}}\, dz ~.
\eqno(10)
$$
Noting that $z_0=-1$ is a double pole of the function
under the integral and computing the residue at $z_0$, we obtain the
first term in (3). The second term (oscillating function
$\delta(\log_2 n)$) is derived from the infinite number
of poles of the form
$z_k=-1+2\pi k i/\log 2$ of the denominator.
Details can be found in the references already
mentioned above.
In passing, we note that in fact much more was done in this area.
We refer to seminal works %of such prominent researchers as
Knuth and Flajolet,
and some others, like (in alphabetical order) Jacquet, Kirschenhofer,
Prodinger, R\'egnier, Schmid, Sedgewick and Szpankowski.
\big
{\bf Added in the Proof}. Yet another binomial recurrence was consider by
Ressler in his recent paper ``Random List Permutations in Place'',
{\it Information Processing Letters}, {\bf 43}, 271-275, 1992. Namely,
for $n\geq 0$
$$
T_{n+1}=n+2^{1-n}\sum_{k=0}^n {n \choose k} T_k
\eqno(11)
$$
with $T_0=0$, and Ressler proved that $T_n\leq n\log_2 n$.
This recurrence does not fall exactly under
our general scheme (5). In fact, it is harder to solve, and
it appears in the analysis of another digital tree, namely, {\it digital
search tree} (cf. \cite{flajolet2}, \cite{fs}, \cite{fr},
\cite{knuth}, \cite{spa5}).
More generally, as in \cite{spa5} consider the following recurrence
for $n\geq 1$
$$
x_{n+1}=a_{n+1}+2^{1-n}\sum_{k=0}^n {n \choose k} x_k
\eqno(12)
$$
with $x_0=0$. It is proved in \cite{spa5} that the above recurrence
has the following solution
$$
x_n=- \sum_{k=2}^n (-1)^k {n \choose k} \hat{x}_{k-2}
\eqno(14)
$$
where
$$
\hat{x}_n = Q_n \sum_{i=1}^{n+1} (\hat{a}_i-\hat{a}_{i+1}-a_1)/Q_{i-1}
\eqno(15)
$$
with $Q_n=\prod_{k=1}^n(1-2^{-k})$.
Note that the solution (14) has the form of the alternating sum as
in (8), hence the methodology discussed above can be directly applied
to obtain an asymptotic expansion of (14).
In particular, for the recurrence (11) studied by Ressler we can easily prove
that $T_n=\sum_{k=2}^n (-1)^k {n \choose k} Q_{k-2}$, and
$$
ET_n=n\log_2n+n\left({\gamma-1\over \log 2}+{1\over 2}
-\alpha+\delta_1(\log_2n)\right) +O(\log n) ~,
\eqno(16)
$$
where $\gamma=0.57721\ldots$ is Euler's constant and
$\alpha=\sum_{n\geq 1}1/(2^n-1)=1.60669\ldots~$, and
$\delta_1(x)$ is a continuous periodic function
of period $1$, mean $0$ and very small amplitude ($< 10^{-6}$).
For more details, the reader is referred to the literature cited above.
\begin{singlespace}
\begin{thebibliography}{99}
\bibitem{capetanakis}
J. Capetanakis, Tree Algorithms for Packet Broadcast Channels,
{\it IEEE Trans. on Inf. Theory}, 25, 505-515 (1979).
\bibitem{flajolet}
P. Flajolet, On the Performance Evaluation of Extendible Hashing and Trie
Searching, {\it Acta Informatica} 20, 345-369 (1983).
\bibitem{flajolet2}
P. Flajolet,
Analytic Analysis of Algorithms, {\it Proc. ICALP 92}, Vienna,
Lecture Notes in Computer Science, vol. 623, Springer Verlag,
186-210 (1992).
\bibitem{fs}
P. Flajolet and R. Sedgewick,
Digital Search Trees Revisited,
{\it SIAM J. Computing}, 15, 748-767 (1986).
\bibitem{fr}
P. Flajolet and B. Richmond,
Generalized Digital Trees and Their Difference-Differential Equations,
{\it Random Structures \& Algorithms}, 3, 305-320 (1992).
\bibitem{henrici}
P. Henrici,
{\it Applied and Computational Complex Analysis}, Vol 2.,
John Wiley\&Sons, New York 1977.
\bibitem{jr}
P. Jacquet and M. R\'{e}gnier, Limiting Distributions for Trie Parameters,
{\it Lecture Notes in Computer Science}, 214, 196-210 (1986).
\bibitem{js}
P. Jacquet and W. Szpankowski, Analysis of Digital Tries with
Markovian Dependency, {\it IEEE Transactions on Information Theory},
37, 1470-1475 (1991).
\bibitem{kp}
P. Kirschenhofer and H. Prodinger,
Further Results on Digital Search Trees,
{\it Theoretical Computer Science}, 58, 143-154 (1988).
\bibitem{kp2}
P. Kirschenhofer and H. Prodinger,
On Some Applications of Formulae of Ramanujan in the Analysis of
Algorithms,
{Mathematika}, 38, 14-33 (1991).
\bibitem{kps1}
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the Variance of the External Path length in a Symmetric Digital Tries,
{\it Discrete Applied Mathematics}, 25, 129-143 (1989).
\bibitem{kps2}
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the balance Property of Patricia Tries: External Path Length Viewpoint,
{\it Theoretical Computer Science}, 68, 1-17 (1989).
\bibitem{knuth}
D.E. Knuth,
{\it The Art of Computer Programming. Vol. 3},
Addison-Wesley, Reading MA 1973.
\bibitem{mf}
P. Mathys and P. Flajolet,
$Q$-ary Collision Resolution Algorithms in
Random-Access Systems with Free or Blocked Channels Access,
{\it IEEE Trans. Information Theory}, 31, 217-243 (1985).
\bibitem{mahmoud}
H. Mahmoud,
{\it Evolution of Random Search Trees},
John Wiley \& Sons, New York 1992.
\bibitem{schmid}
U. Schmid,
On a Tree Collision Resolution Algorithm in Presence of Capture,
{\it RAIRO, Theoretical Informatics}, 26, 163-197 (1992).
\bibitem{spa1}
W. Szpankowski,
On a Recurrence Equation Arising in the Analysis of
Conflict Resolution Algorithms,
{\it Stochastic Models}, 3, 89-114 (1987).
\bibitem{spa2}
W. Szpankowski,
The Evaluation of an Alternating Sum with Applications to the
Analysis of Some Data Structures,
{\it Information Processing Letters}, 28, 13-19 (1988).
\bibitem{spa3}
W. Szpankowski, Some Results on V-ary Asymmetric Tries, {\it Journal of
Algorithms}, 9, 224-244 (1988).
\bibitem{spa4}
W. Szpankowski, Patricia Tries Again Revisited,
{\it Journal of the ACM,} 37, 691-711 (1991).
\bibitem{spa5}
W. Szpankowski,
A Characterization of Digital Search Trees from the Successful Search
Viewpoint, {\it Theoretical Computer Science}, 85, 117-134 (1991).
\end{thebibliography}
\end{singlespace}
\end{document}
exit