\documentstyle[12pt,ctagsplt,righttag,theorem]{amsart}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Numbering
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\thefigure{\arabic{figure}}
\def\thetable{\arabic{table}}
\def\thesection{\arabic{section}}
\def\theequation{\arabic{equation}}
\def\paragraph{\@startsection{\@string\paragraph}{4}{\z@}{\parindent}{-1em}
{\defaultfont\it}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Items
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\labelitemi{\bf --}% \normalshape already done by \itemize
\def\labelitemii{$\m@th\ast$}
\def\labelitemiii{$\m@th\cdot$}
\def\labelitemiv{$\m@th\bullet$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Dimensions (fullpage is not standard LaTeX)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt
\topmargin 0pt \textwidth 6.5in \textheight 8.5in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Macros for the user
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hfuzz=20pt
\vfuzz=1.15pt
\def\C{{\Bbb C}}
\def\F{{\Bbb F}}
\def\N{{\Bbb N}}
\def\Q{{\Bbb Q}}
\def\R{{\Bbb R}}
\def\Z{{\Bbb Z}}
\def\Id{\text{Id}}
\def\Pr{\operatorname{Pr}}
\def\Arg{\operatorname{Arg}}
\def\Cov{\operatorname{Cov}}
\def\Res{\operatorname{Res}}
\def\Var{\operatorname{Var}}
\def\LUO{%
\leavevmode{\char'3\kern-.3em\lower0.666ex%
\hbox{\char'7}\kern-.125em\raise0.2ex\hbox{\char'12}}}
\def\Card{\operatorname{Card}}
\def\U{{\widehat{U}}}
\def\({\left(}
\def\){\right)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Environments for the user
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\renewcommand{\thetheorem}{\arabic{theorem}}
\newtheorem{lemma}{Lemma}
\renewcommand{\thelemma}{\arabic{lemma}}
\newtheorem{proposition}{Proposition}
\renewcommand{\theproposition}{\arabic{proposition}}
\newtheorem{conjecture}{Conjecture}
\renewcommand{\theconjecture}{\arabic{conjecture}}
\newtheorem{corollary}{Corollary}
\renewcommand{\thecorollary}{\arabic{corollary}}
\newtheorem{property}{Property}
\renewcommand{\theproperty}{\arabic{property}}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\renewcommand{\thedefinition}{\arabic{definition}}
\newtheorem{principle}{Principle}
\renewcommand{\theprinciple}{}
\newtheorem{condition}{Condition}
\renewcommand{\thecondition}{\arabic{condition}}
\theoremstyle{remark}
\newtheorem{example}{Example} \renewcommand{\theexample}{}
\newtheorem{remark}{Remark} \renewcommand{\theremark}{}
\newtheorem{note}{Note} \renewcommand{\thenote}{}
\renewenvironment{abstract}%
{\small\begin{center}{\bf Abstract}\end{center}
\quotation}%
{\endquotation\vspace{0.5ex}}
\def\proof{\pf}
\def\endproof{\endpf}
%\title{The recursion of Shiau and Yang}
\title[asymptotic study of a recursion]
{An asymptotic study of a recursion occurring in the analysis of an
algorithm on broadcast communication}
\author{Peter J. Grabner and Helmut Prodinger}
\address{\newline
Institut f\"ur Mathematik. Technical University of Graz.
Steyrergasse 30, A-8010 Graz, Austria.
\bigskip\newline
Institut f\"ur Algebra und Diskrete Mathematik.
Technical University of Vienna.
Wiedner Hauptstrasse 8--10, A-1040 Vienna, Austria.\bigskip}
\bigskip
\email{grabner@@weyl.math.tu-graz.ac.at, Helmut.Prodinger@@tuwien.ac.at}
\keywords{Broadcast communication, Recursion, Bernoulli numbers,
Rice's method, Mellin--Perron formula}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
In \cite{ShYa96} it was proved that a certain quantity $T_n$
occurring in the analysis of an
algorithm on broadcast communication
satisfies $4\ll \frac{T_n}{\log n}\ll 5$.
We give an explicit expression for $T_n$ involving Bernoulli numbers
and a precise asymptotic formula showing in particular that
$\frac{T_n}{\log n}\to \frac{\pi^2}{3\log 2}= 4.74627644\ldots$.
\end{abstract}
In \cite{ShYa96} a maximum finding
algorithm was presented that we rephrase
in our own words for the reader's convenience.
Assume that each of $n$ persons thinks about a number, and
the maximum of these should be determined. The party selects a
``loser,'' as in \cite{Prodinger93}, by
(recursive) coin flippings. This person's number will be the next current
maximum (initially the maximum was set to $-\infty$), and will
be officially announced. Then, all people who have a number smaller or
equal to the current maximum drop out of the game, and the procedure is
repeated with the reduced party. The interest is of course in the expected
time $T_n$ that this procedure takes in order to determine the maximum.
For the analysis of the algorithm the authors of
\cite{ShYa96} come up with the recursion
\begin{equation*}
\left(1-\frac{1}{2^{n-1}}\right)T_n=1+\frac{1}{2^n}\left[
1+\sum_{k=1}^{n-1}\binom{n}{k}T_k+\sum_{k=0}^{n-1}2^{n-1-k}T_k
\right]\;,
\end{equation*}
($n\ge2$; $T_0=T_1=1$).
Such a recursion is a typical ``probabilistic divide--and--conquer
recurrence'' and directly reflects the recursive structure of the algorithm.
As general references, we mention \cite{Knuth73} and \cite{SeFl96}.
By elementary methods it was shown
in \cite{ShYa96} that $T_n=\Theta(\log n)$. In this note it
will be shown that we can achieve much better results, since we will prove that
\begin{theorem} (i) An explicit formula for $T_n$ is given by
\begin{equation*}
T_n=1+\sum_{k=0}^{n-1}\frac{2B_k}{1-{2^{-k-1}}}\left[\binom{n}{k+1}-1
\right]\;,
\end{equation*}
where $B_n$ is the $n$--th Bernoulli number.
(ii)
For $n\to\infty$ we have
\begin{equation*}
T_n=\frac{\pi^2}{3\log 2}\log n+K+\delta(\log_2n)+O\Big(\frac1n\Big).
\end{equation*}
The constant $K$ is given by
\begin{equation*}
K=\frac{\gamma\pi^2}{3\log2}+1-\frac{\pi^2}{3\log2}-\frac{2\zeta'(2)}{\log2}
+\frac{\pi^2}6-2\sum_{n=1}^\infty\frac{\lceil\log_2n\rceil}{n^2}=
.34118435603469732225\ldots
\end{equation*}
and $\delta(x)$ is a periodic function with period 1, mean 0,
$|\delta(x)|\leq0.852\cdot10^{-5}$, and the Fourier expansion
\begin{equation*}
\delta(x)=\frac{2}{\log2}\sum_{k\ne
0}\frac{\Gamma(2-\chi_k)\,\zeta(2-\chi_k)}{\chi_k}
\,e^{2k\pi ix}\;.
\end{equation*}
Observe that $\frac{\pi^2}{3\log 2}= 4.74627644\ldots$, which ``explains'' the
elementary bounds $4\ll \frac{T_n}{\log n}\ll 5$ from \cite{ShYa96}.
\qed
\end{theorem}
By elementary rearrangements we write the recursion as
\begin{equation*}
\left(1-\frac{1}{2^{n-1}}\right)T_n+\frac{1}{2^n}T_n+\frac{1}{2^{n+1}}T_n
=1+\frac{1}{2^n}\left[
\sum_{k=0}^{n}\binom{n}{k}T_k+\sum_{k=0}^{n}2^{n-1-k}T_k
\right]\; ;
\end{equation*}
taking the difference between this equation and the one where $n$ is
substituted by
$n-1$ we find
\begin{equation*}
\left(1-\frac{1}{2^{n}}\right)\left(T_n-T_{n-1}\right)
=\frac{1}{2^n}\sum_{k=0}^{n-1}\binom{n-1}{k}\left(T_{k+1}-T_k\right)\;.
\end{equation*}
It is natural to introduce the auxiliary quantities
$U_k=T_{k+1}-T_k$ and replace $n$ by $n+1$ to find
\begin{equation*}
\left(1-\frac{1}{2^{n+1}}\right)U_{n}
=\frac{1}{2^{n+1}}\sum_{k=0}^{n}\binom{n}{k}U_k\;.
\end{equation*}
It holds for $n\ge2$ and $U_0=0$, $U_1=4$.
Now such recursions are fairly well understood, see e.g. \cite{SeFl96}: One
introduces the exponential generating function
\begin{equation*}
U(z)=\sum_{n\ge0}U_n\frac{z^n}{n!}
\end{equation*}
and translates the recursion into the functional equation
\begin{equation*}
U(z)={\tfrac{1}{2}}(1+e^{z/2})U({\tfrac z2})+2z\;.
\end{equation*}
This equation can be solved using an old trick of Knuth's,
\cite[pp. 502, 686 (Ex. 6.3.33)]{Knuth73}, that was used
to analyze a variant of digital search trees called Patricia trees:
We define
\begin{equation}\label{func}
\U(z)=\frac{U(z)}{e^z-1}
\end{equation}
and get the simpler equation
\begin{equation*}
\U(z)={\tfrac{1}{2}}\U({\tfrac z2})+\frac{2z}{e^z-1}\;.
\end{equation*}
Inserting
\begin{equation*}
\U(z)=\sum_{n\ge0}\U_n\frac{z^n}{n!}\;,
\end{equation*}
into (\ref{func}) yields
\begin{equation*}
\sum_{n\geq0}\frac{z^n}{n!}\U_n\(1-\frac1{2^{n+1}}\)=
2\sum_{n\geq0}\frac{z^n}{n!}B_n,
\end{equation*}
where $B_n$ denotes the $n$-th Bernoulli number.
Comparing coefficients we deduce
\begin{equation*}
\U_n\Big(1-\frac{1}{2^{n+1}}\Big)=2B_n\quad
\mbox{or}\quad
\U_n=\frac{2B_n}{1-\frac{1}{2^{n+1}}}\;.
\end{equation*}
Thus we have
\begin{equation*}
U_n=\sum_{k=0}^{n-1}\binom{n}{k} \frac{2B_k}{1-{2^{-k-1}}}\;.
\end{equation*}
Summing up this formula, we find the explicit formula for $T_n$, mentioned in
the
theorem.
It is interesting to compare this expression with ``the hardest asymptotic
nut'' Knuth ever had to crack,
\cite[p. 499 and Ex. 6.3.34]{Knuth73}. In \cite{Prodinger93}, related
quantities appear in the context of the election of a loser.
\medskip
Now we turn to asymptotics. Following the method described in \cite{FlSe95}
(see also \cite{Szpankowski88, Prodinger93})
we can write $U_n$ as a complex contour integral;
\begin{equation}
U_n=\frac{1}{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{\Gamma(n+1)\,\Gamma(1-s)}{\Gamma(n+1-s)}
\frac{2\zeta(1-s)}{1-{2^{-s-1}}}ds\;.
\end{equation}
Since
\begin{equation*}
T_n=1+U_0+U_1+\sum_{m=2}^{n-1}U_m\;,
\end{equation*}
we find
\begin{align}\label{fint}
T_n=5&-\frac 1{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{4\zeta(1-s)}{(1-s)(s+1)(1-2^{-s-1})} ds\\&+
\frac 1{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{\Gamma(n+1)\,\Gamma(1-s)}{\Gamma(n-s)}
\frac{2\zeta(1-s)}{(s+1)(1-2^{-s-1})}ds\;.
\end{align}
Observe that the first two terms were taken out in order to make the first
integral convergent.
We can compute (\ref{fint}) as follows,
\begin{align}\label{int}
\frac 1{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
&\frac{4\zeta(1-s)}{(1-s)(s+1)(1-2^{-s-1})} ds=\frac 1{2\pi i}
\int_{\frac32-i\infty}^{\frac32+i\infty}
\frac{4\zeta(s)}{s(2-s)(1-2^{s-2})}ds\\&=
\sum_{k\ge0}\sum_{n\ge1}4^{1-k}
\frac 1{2\pi i}
\int_{\frac32-i\infty}^{\frac32+i\infty}
\frac{1}{s(2-s)}\left(\frac{2^k}{n}\right)^sds\;.
\end{align}
Here, we first used the substitution
$s:=1-s$ and then the
the geometric series and the expansion of $\zeta(s)$, both
valid for $\Re z=\frac{3}{2}$. A simple application of residue calculus,
as it is often used in the context of the Mellin--Perron summation formula
(see \cite{Tenenbaum95, FGKPT94}) evaluates the integrals inside the summation:
\begin{equation*}
\frac 1{2\pi i}
\int_{\frac32-i\infty}^{\frac32+i\infty}
\frac1{s(2-s)}t^s ds=
\cases \frac12&\text{for }t\geq1\\
\frac{t^2}{2}&\text{for }t<1\endcases\;.
\end{equation*}
Now the series according to the first alternative is
\begin{equation*}
\sum_{k\ge0}4^{1-k}\sum_{n=1}^{2^k}\frac{1}{2}=2\sum_{k\ge0}4^{-k}2^k=
2\sum_{k\ge0}2^{-k}=4
\end{equation*}
and the other one is
\begin{equation}\label{sum}
2\sum_{k\ge0}\sum_{n>2^k}\frac{1}{n^2}=
2\sum_{k=0}^\infty(k+1)\sum_{n=2^k+1}^{2^{k+1}}\frac1{n^2}=
3.0022908154228746627\ldots\;.
\end{equation}
Notice that in the range of $n$ we have $k+1=\lceil\log_2n\rceil$, which gives
the series in the statement of the theorem. For numerical purposes the
expression
in (\ref{sum}) is preferred, since {\sc Maple} computes the partial sums
$\sum_{a\le n\le b}\frac{1}{n^2}$ efficiently using the Euler--MacLaurin
summation formula. Observe that the (slowly converging) integral
has been transformed into a (better converging) series. We mention here that
another possibility to compute the integral (\ref{int}) would be to move the
line of integration to the right. Here residues at the points
$2+\frac{2k\pi i}{\log 2}$ would have to be collected, which would form a
slowly convergent sum. This sum corresponds to (\ref{sum}) by replacing
$\lceil\log_2n\rceil$ with $\log_2n+1+\{\log_2n\}$ and inserting the Fourier
expansion for $\{x\}$ (the fractional part of $x$). Certainly, the values at
$n=2^k$ have to be adjusted accordingly. Since we could not find a closed form
expression for this sum and (\ref{sum}) could be computed easily numerically,
we preferred this form of the sum.
\medskip
The strategy
to evaluate the second integral
is to shift the line of integration to the left, and
to collect the residues; they constitute the terms in the asymptotic expansion
(see \cite{FlSe95}). A similar computation as the one used before to
derive the series expansion for the first integral shows that
\begin{equation*}
\frac1{2\pi i}\int_{-\frac32-i\infty}^{-\frac32+i\infty}
\frac{\Gamma(n+1)\,\Gamma(1-s)}{\Gamma(n-s)}\frac{2\zeta(1-s)}
{(s+1)(1-2^{-s-1})}ds=0.
\end{equation*}
At $s=-1$, we find the residue
\begin{equation*}
\frac{\pi^2H_n}{3\log 2}-\frac{\pi^2}{3\log2}-\frac{2\zeta'(2)}{\log2}
+\frac{\pi^2}6\;,
\end{equation*}
with a harmonic number $H_n=\sum_{1\le k\leq n}\frac1k=\log n+\gamma+
O(\frac{1}{n})$.
At $s=-1+\chi_k$ with $\chi_k=\frac{2k \pi i}{\log2}$
(for $k\in \Bbb{Z}$, $k\ne 0$)
we find the residue
\begin{equation*}
\frac{\Gamma(n+1)\,\Gamma(2-\chi_k)}{\Gamma(n+1-\chi_k)}
\frac{2\zeta(2-\chi_k)}{\chi_k \log2}\;;
\end{equation*}
collecting them gives the {\sl explicit formula\/}
\begin{equation*}
T_n=\frac{\pi^2}{3\log2}H_n+\Big(K-\frac{\gamma\pi^2}{3\log2}\Big)+
\sum_{k\in\Z\setminus\{0\}}\frac{\Gamma(n+1)\,\Gamma(2-\chi_k)}
{\Gamma(n+1-\chi_k)}\frac{2\zeta(2-\chi_k)}{\chi_k\log2}\;.
\end{equation*}
The periodic function mentioned in the theorem can be computed from the
asymptotic expansion of the quotients of $\Gamma$-functions
(compare \cite{AbSt73})
\begin{equation*}
\frac{\Gamma(n+1)}{\Gamma(n+1-\chi_k)}=n^{\chi_k}
\Big(1+O\big(\frac{k^2}{n}\big)\Big)\;.
\end{equation*}
Combining known estimates for the $\Gamma$- and $\zeta$-function
(cf.~\cite{AbSt73}) yields
\begin{equation*}
\frac{2\Gamma(2-\chi_k)\,\zeta(2-\chi_k)}{\chi_k\log2}\leq
13|k|^{\frac12}e^{-\frac{\pi^2}{\log2}|k|}\quad\mbox{for }|k|\geq1
\end{equation*}
which (by uniform convergence) justifies interchanging summation and
asymptotics. Furthermore, this yields the estimate for $\delta(x)$
stated in the theorem.
By taking more terms in the above formula and in the asymptotic expansion
of the harmonic numbers, a remainder of the form
$O(\frac{1}{n^m})$ for any
$m>0$ could be achieved. Consequently,
one could give as many terms as desired in the asymptotic formula of the
theorem.
\bibliographystyle{plain}
\begin{thebibliography}{1}
\bibitem{AbSt73}
M.~Abramowitz and I.~A. Stegun.
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover, 1973.
\newblock A reprint of the tenth National Bureau of Standards edition, 1964.
\bibitem{FGKPT94}
P.~Flajolet, P.~Grabner, P.~Kirschenhofer, {H. {P}rodinger}, and R.F. Tichy.
\newblock Mellin transforms and asymptotics: Digital sums.
\newblock {\em Theor. Comput. Sci.}, 123:291--314, 1994.
\bibitem{FlSe95}
P.~Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: Finite differences and {R}ice's
integrals.
\newblock {\em Theor. Comput. Sci.}, 144:101--124, 1995.
\bibitem{Knuth73}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
Searching.
\newblock Addison-Wesley, 1973.
\bibitem{Prodinger93}
H.~Prodinger.
\newblock How to select a loser.
\newblock {\em Discrete Math.}, 120:149--159, 1993.
\bibitem{SeFl96}
R.~Sedgewick and P.~Flajolet.
\newblock {\em An Introduction to the Analysis of Algorithms}.
\newblock Addison-Wesley, 1996.
\bibitem{ShYa96}
S.-H. Shiau and C.-B. Yang.
\newblock A fast maximum finding algorithm on broadcast communication.
\newblock {\em Inf. Process. Lett.}, 60:81--89, 1996.
\bibitem{Szpankowski88}
W.~Szpankowski.
\newblock The evaluation of an alternating sum with applications to the
analysis of algorithms.
\newblock {\em Inf. Process. Lett.}, 28:13--19, 1988.
\bibitem{Tenenbaum95}
G.~Tenenbaum.
\newblock {\em Introduction to analytic and probabilistic number theory}.
\newblock Cambridge University Press, 1995.
\end{thebibliography}
%\bibliography{pro_bib}
\end{document}