\documentclass[12pt,reqno]{amsart}
\usepackage{amsmath,amssymb,a4ams}

\setlength{\headheight}{12.5pt}
\def\({\left(}
\def\){\right)}
\newcommand{\eps}{\varepsilon}
\newcommand{\Res}{\mathop{\mathrm{Res}}\limits}
\newlength{\remwidth}
\setlength{\remwidth}{\textwidth}
\addtolength{\remwidth}{-1cm}


\begin{document}
\bibliographystyle{plain}
\title[Sorting algorithms for broadcast communications]
{Sorting algorithms for broadcast communications:\\
Mathematical analysis}
\author[P. J. Grabner]{Peter J. Grabner$^\dag$}
\address[P. Grabner]{Institut f\"ur Mathematik A,
Technische Universit\"at Graz,
Steyrergasse 30,
8010 Graz,
Austria}
\email{grabner@weyl.math.tu-graz.ac.at}
\thanks{\dag{} This author is supported by the 
 START-project Y96-MAT of the Austrian Science Foundation}

\author[H. Prodinger]{Helmut Prodinger}
\address[H. Prodinger]{
The John Knopfmacher
Centre for Applicable Analysis and Number Theory\\
 Department of Mathematics\\
University of the Witwatersrand, P.~O. Wits\\ 
2050 Johannesburg, South Africa}
\email{helmut@gauss.cam.wits.ac.za}

\keywords{}
\subjclass{Primary: 68Q25; Secondary: 05A15, 05A16, 60C05}
\date{\today}
\begin{abstract}
We study three algorithms for sorting under the broadcast communication
model. Two algorithms are based on the maximum finding and the loser selection
strategy, the third one is the na\"\i{}ve strategy based on loser selection
only. While a precise description of the algorithms can be found in the paper
\cite{Shiau_Yang00b}, we concentrate here on the mathematical aspects of the
analysis. From these elementary considerations it follows that the average
time complexities of the non-na\"\i{}ve algorithms are $\Theta(n)$. We give
precise expressions for the constants involved by writing them as contour
integrals involving zeta functions. The numerical evaluation via residues leads
to slowly converging series, and the acceleration of them is a nontrivial task
that is done in a slightly more general fashion in order to fit all the 
applications. 
\end{abstract}
\bibliographystyle{plain}

\maketitle



\section{Introduction}\label{sec:intro}

The purpose of this paper is two-fold: firstly we discuss a
probabilistic model for conflict resolution in broadcast communication and
secondly we present a method to compute certain integrals which occur
in the asymptotic analysis of this model (and also elsewhere) numerically to a
high precision. 

Let us first describe the model:
Assume that $n$ persons communicate via a channel. Several algorithms related
to the transmitted data (``numbers'') are of interest. A particularly simple
one is to find 
the maximum of the $n$ items (communicated by the $n$ persons). This algorithm
was formulated and analyzed in \cite{Shiau_Yang96,Grabner_Prodinger98}. A more
complex task is sorting: in the end every party should have a complete sorted
list of the $n$ items. This implies of course that every item has to be
communicated at some stage.

We will analyze three algorithms to achieve this; the
interest is in the average number of discrete time slots needed for
communicating data (number of ``rounds''). 

When more than one person sends at a time, a
{\it conflict\/} arises. The conflict resolution
schemes that are considered here are all based on
coin flippings (with a fair coin): The persons involved in a conflict
flip a coin, and those who flipped tail step out
and wait until those who flipped head have resolved
their conflict.

This principle is often described as ``selection of a 
{\it loser}'', see \cite{Grabner93,Prodinger93},
or as {\it leader election}, see
\cite{Sedgewick_Flajolet96,Fill_Mahmoud_Szpankowski96,Janson_Szpankowski97}. 
(The loser is determined by consecutive rounds of coin flippings;
those who flip heads create smaller and smaller populations
until a single person remains. There is a special rule to be applied
however when nobody flips head; then this round has to be repeated.)
The loser then successfully transmits his data. By different recursive
strategies we obtain the variants of the algorithm studied in this paper.

\begin{description}
\item[Section~2] The first algorithm uses the maximum finding strategy as
studied in 
\cite{Shiau_Yang96,Grabner_Prodinger98}. Finding the maximum needs several
rounds of recursive coin flippings; after each successful broadcast of a number
only the persons with larger numbers than the announced one go on
recursively. Thus, in the process of finding the maximum, several data items
have already been transmitted successfully (and are known to all
participants). The remaining set of persons, who have not yet transmitted their
data successfully, follows the same strategy recursively, until no persons are
left. See \cite{Shiau_Yang00a} for a more detailed description of the
algorithm.
\item[Section~3] The second algorithm does not use the maximum finding
  strategy, but loser
selection instead. The loser transmits his number, and the participants are
split into two subfiles (larger resp. smaller numbers). These two subfiles are
processed recursively, until all persons have broadcasted. See
\cite{Shiau_Yang00b} for a detailed description. 
\item[Section~4] Finally, we discuss a very na\"\i{}ve strategy, where we only
  record the
communication provided by the loser, and find the next loser from the reduced
set of $n-1$ persons, etc. This is naturally slower.
\end{description}

Loser selection works by coin flippings; the first two
algorithms use additionally a splitting \`a la binary search, 
whereas the na\"\i{}ve strategy only works sequentially. 
It turns out that the second algorithm is the best, the intuitive
reason being  perhaps that it is good to split the file as soon as possible,
i.~e. when the first loser has been found. 

We remark that in our probabilistic model we use independent unbiased coins for
selecting the losers. Furthermore, all permutations of data are equally likely
(as it si customary when analyzing sorting algorithms).

The average number of rounds to select a loser is given by
the recursion
\begin{equation*}
S_n(1-2^{-n})=1+2^{-n}\sum_{k=0}^n\binom nkS_k,\quad n\ge2,
\qquad S_0,
S_1=0.
\end{equation*}
(Note that this algorithm itself is recursive).

From \cite{Prodinger93} we know the solution
\begin{equation*}
S_n=1-\sum_{k=1}^{n-1}\binom nk\frac{B_k}{2^k-1},
\qquad n\ge2
\end{equation*}
with Bernoulli numbers $B_k$.

There is also the very useful representation of $S_n$  as
a contour integral, viz.
\begin{equation*}
S_n=1-\frac{1}{2\pi i}
\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{\Gamma(1-s)\Gamma(n+1)\zeta(1-s)}
{\Gamma(n+1-s) (2^s-1)}\,ds.
\end{equation*}
See \cite{Flajolet_Sedgewick95} for some background on such integrals. 

The average number of rounds $M_n$ to find the maximum
\cite{Shiau_Yang96,Grabner_Prodinger98} is given by
\begin{align*}
M_n&=1+\sum_{k=0}^{n-1}\frac{2B_k}{1-2^{-k-1}}
\bigg[\binom{n}{k+1}-1\bigg],\qquad n\ge0;
\end{align*} 
 it was also proved that

\begin{equation}\label{eq:mn}
M_n-M_{n-1}=\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}\frac{\Gamma(n)\Gamma(1-s)}{\Gamma(n-s)}
\frac{2\zeta(1-s)}{1-2^{-s-1}}\,ds.
\end{equation}

Several parameters of the probabilistic model described above can be expressed
in terms of series involving the sequences $M_n$ and $S_n$. These series turn
out to converge very slowly so that they are not even suitable to compute three
digits of the values in question. In the specific case here the second
possibility to compute these constants is also not applicable: deform the line
of integration in the contour integral representation and collect residues
(cf.~section~\ref{sec:mellin}). Here the resulting series is again converging
too slowly. In section~\ref{sec:howto} we will describe how to use the integral
representation to obtain a rapidly converging algorithm for numerical
computation of these integrals. This algorithm is formulated rather general and
could be applied to similar problems immediately.


\medskip
\parbox{\remwidth}{
{\bf Remark.}  If the only task were to {\it transmit\/} all the elements,
then the most obvious strategy is the conflict resolution scheme as 
described in \cite{Mathys_Flajolet85}; all participants try to broadcast in the
beginning, and then the conflict is resolved by consecutive rounds of coin
flippings. The average number of rounds for this procedure is (apart from small
fluctuations) asymptotically equal to $\frac{2}{\log2}n$; the constant
$\frac{2}{\log2}=2.885390082$ 
is better than the constants for the algorithms in this paper. However, 
in this way the data arrive in random order, whereas the strategies in this
paper produce the sorted file (one can think about the data
as arranged in the Quicksort tree \cite{Sedgewick_Flajolet96}).}

\section{The maximum finding strategy}\label{sec:losers}

Denote by $T_n$ the average number of rounds with this method. 
Shiau and Yang \cite{Shiau_Yang00a} argue like this:
There are extra costs of $M_n$ for finding the maximum
on the first level of recursion. The first successful
broadcast, which can be any element with the same probability
$\frac{1}{n}$, splits the file into a subfile of $n-k-1$
smaller elements to which the recursive strategy is applied
at a later stage, with costs $T_{n-k-1}$. In the file of
$k$   larger elements, the search for the maximum is still
continuing, but we have taken care already for the extra
cost for maximum searching, thus a contribution $T_k-M_k$.
If $k=0$, it costs however $0$, and if $k=1$, it costs $1$, so that
we have the recursion for $n\ge2$
\begin{equation*}   
T_n=M_n+\frac{1}{n}\sum_{k=0}^{n-1}T_k
+\frac{1}{n}\sum_{k=2}^{n-1}(T_k-M_k)+\frac{1}{n},
\end{equation*}    
with $T_0=1$ and $T_1=1$.

We multiply that by $n$:   
\begin{equation*}   
nT_n=nM_n+\sum_{k=0}^{n-1}T_k
+\sum_{k=2}^{n-1}(T_k-M_k)+1,
\end{equation*}    
write this with $n$ replaced by $n-1$:
\begin{equation*}   
(n-1)T_{n-1}=(n-1)M_{n-1}+\sum_{k=0}^{n-2}T_k
+\sum_{k=2}^{n-2}(T_k-M_k)+1,
\end{equation*}    
 and take differences:
\begin{equation*}   
nT_n-(n-1)T_{n-1}=nM_n-(n-1)M_{n-1}+T_{n-1}
+T_{n-1}-M_{n-1},
\end{equation*}    
or (replacing $n$ by $k$) 
\begin{equation*}   
\frac{T_k}{k+1}-\frac{T_{k-1}}{k}=\frac{M_k-M_{k-1}}{k+1}.
\end{equation*}    
Summing this from $k=3,\dots, n$ we get
\begin{equation*}   
\frac{T_n}{n+1}-\frac{T_{2}}{3}=\sum_{k=3}^n\frac{M_k-M_{k-1}}{k+1}
\end{equation*}    
or
\begin{equation*}   
T_n=\frac{13}{6}(n+1)+(n+1)\sum_{k=3}^n\frac{M_k-M_{k-1}}{k+1}
\quad\text{for }n\geq2.
\end{equation*}    
Since asymptotics of $M_n$ are well--known \cite{Grabner_Prodinger98}
we know {\it a priori\/} that $T_n\sim A_1\cdot n$, where the constant
$A_1$ is given by
\begin{equation*}   
A_1=\frac{13}{6}+\sum_{k=3}^\infty\frac{M_k-M_{k-1}}{k+1}.
\end{equation*} 
(With more effort, one could derive a full asymptotic expansion;
see section~\ref{sec:howto} for such computations.)

Using \eqref{eq:mn} we obtain
\begin{equation}\label{eq:sum1}
\sum_{k=3}^\infty\frac{1}{k+1}(M_k-M_{k-1})
=\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}
\sum_{k=3}^\infty\frac{\Gamma(k)\Gamma(1-s)}{(k+1)\Gamma(k-s)}
\,\frac{2\zeta(1-s)}{1-2^{-s-1}}\,ds.
\end{equation}
Define
\begin{equation}\label{eq:fs}
f(s):=\Gamma(1-s)\sum_{n=3}^\infty\frac{\Gamma(n)}{(n+1)\Gamma(n-s)}=
-\frac{6s^2-3s-5}{6(s-1)}-s(s+1)\psi'(-s),
\end{equation}
where as usual $\psi(s)=\frac{\Gamma'(s)}{\Gamma(s)}$. Equation \eqref{eq:fs}
is a immediate consequence of the following chain of equations
(cf.~\cite{Andrews_Askey_Roy99}):
\begin{align}
\label{eq:fs1}
\begin{split}
\psi'(z)&=-\int_0^1\frac{t^{z-1}}{1-t}\log t\,dt
=-\int_0^1\frac{(1-t)^{z-1}}{t}\log(1-t)\,dt\\
&=\sum_{n=1}^\infty\frac1n\int_0^1(1-t)^{z-1}t^{n-1}\,dt
=\sum_{n=1}^\infty\frac1n\frac{\Gamma(z)\Gamma(n)}{\Gamma(n+z)}\\
&=\frac1z+\sum_{n=2}^\infty\left(\frac{\Gamma(z)\Gamma(n-1)}{\Gamma(n+z)}-
\frac{\Gamma(z)\Gamma(n-1)}{n\Gamma(n+z)}\right)
=\frac1z+\frac1{z^2}-
\sum_{n=1}^\infty\frac{\Gamma(z)\Gamma(n)}{(n+1)\Gamma(n+z)}.
\end{split}
\end{align}


As $\psi(s)$ is given by the uniformly convergent expansion
$$\psi'(s)=\sum_{n=0}^\infty\frac1{(n+s)^2}$$
it is easy to see that $\psi$ has double poles at the negative integers. For
further details on $\psi$ we refer to
\cite{Andrews_Askey_Roy99,Nielsen06,Titchmarsh39}. Furthermore, we note that
(cf.~\cite{Abramowitz_Stegun65}) for $|\arg(-s)|<\pi$
$$\psi'(-s)=-\frac1s+\frac1{2s^2}-\frac1{6s^3}+\frac1{30s^5}+
\mathcal{O}(|s|^{-7}).$$
Using the identity
$$\psi'(s)+\psi'(-s)=\frac{\pi^2}{\sin^2\pi s}+\frac1{s^2}$$
we can  find an estimate valid for all 
$s$ with $\forall n\in \mathbb{N}_0:
|s-n|>\eps$:
\begin{equation}
\label{eq:fasymp}
f(s)=\mathcal{O}\(\frac1{|s|^2}+\frac1{\eps^2}e^{-2\pi|\Im s|}\).
\end{equation}
Our goal is to compute the integral

\begin{equation*}
\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}^{-\frac{1}{2}+i\infty}
f(s)\frac{2\zeta(1-s)}{1-2^{-s-1}}\,ds.
\end{equation*}
Expanding the $\zeta$--function and the geometric series it is 


\begin{equation*}
\sum_{k\ge1}\frac{1}{k}\sum_{j\ge0}2^{1-j}
\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}^{-\frac{1}{2}+i\infty}
f(s)\Big(\frac{k}{2^j}\Big)^s\,ds.
\end{equation*}
For the evaluation of the integral we need now
\begin{equation}\label{eq:fmellin}
\Phi(x):=
\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}^{-\frac{1}{2}+i\infty}
f(s)x^s\,ds=
\begin{cases}
0&\text{for }x\geq1\\
\dfrac{(3-x)(1+x+x^2)}{3(1-x)^2}
+\dfrac{2x\log x}{(1-x)^3}&\text{for }0<x<1.
\end{cases}
\end{equation}
This equation is achieved as follows (this is actually a standard technique in
analytic number theory): to obtain the formula for $x\geq1$ consider the
integral over the segment $\{-\frac12+it\mid -R\leq t\leq R\}$ 
and the arc
$\{\sigma+it\mid \sigma^2+t^2=R^2, \sigma<-\frac12\}$. Since the integrand has
no poles in this region, the integral vanishes; now let $R$ tend to $\infty$
and observe that the estimate \eqref{eq:fasymp} implies that the integral over
the arc tends to $0$. For $x<1$ we shift the line of integration to the right
(technically, we again truncate the integral at $t=\pm R$ and show that the
contribution tends to $0$ for $R\to\infty$) and collect residues:
\begin{equation*}
\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}
f(s)x^s\,ds=-\sum_{k=1}^K\Res_{s=k}\big\{f(s)x^s\big\}+
\frac{1}{2\pi i}\int\limits_{K+\frac{1}{2}-i\infty}
^{K+\frac{1}{2}+i\infty}f(s)x^s\,ds.
\end{equation*}
By \eqref{eq:fasymp} the integral is bounded by $\mathcal{O}(x^K)$,
which allows the limit $K\to\infty$. Computing the residues and summing up
yields the desired result.

Using \eqref{eq:fmellin} we obtain
\begin{equation*}
\sum_{k\ge1}\frac{1}{k}\sum_{j\ge0}2^{1-j}
\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}\!\!\!
f(s)\Big(\frac{k}{2^j}\Big)^s\,ds=
2\sum_{j\ge0}\sum_{1\le k<2^j}\frac{2^{-j}}{k}\Phi\Big(
\frac{k}{2^j}\Big).
\end{equation*}
Observe that $\Phi(1)=0$, so that we can add the term
$k=2^j$  to the sum. 



In section~\ref{sec:howto} we will explain how to compute such sums numerically
to a high precision.
Therefore we get
\begin{equation*}   
A_1=\frac{13}{6}+2\Sigma_1=
3.67982\,61095\,85742\,29512\,70603\,33235\,96302\,23675\ldots
\end{equation*}
Note that the paper \cite{Shiau_Yang00a} provides the elementary
bounds $\frac{7}{2}=3.5\le A_1\le \frac{23}{6}=3.833\cdots$. 


\section{The splitting strategy}\label{sec:yet}

It is not hard to find a recursion for $T_n$, the average
number of rounds for this method.
(We use the notation $T_n$ again, but there
is no chance for confusion.) The values $T_0=1$ and  $T_1=1$
are self-explanatory, and for $n\ge2$ we have
\begin{equation*}   
T_n=1+S_n+\frac{1}{n}\sum_{k=0}^{n-1}(T_k+T_{n-1-k});
\end{equation*} 
the 1 counts the initial broadcast, causing the conflict, 
which needs $S_n$ to be resolved. Then, the probability is
uniformly $\frac{1}{n}$  that the file splits.
(See \cite{Shiau_Yang00b} for a more elaborate description.)

The traditional method to solve that is as in the previous
section:
\begin{equation*}   
nT_n=n+nS_n+2\sum_{k=0}^{n-1}T_k;
\end{equation*}
replace $n$  by $n-1$ 
\begin{equation*}   
(n-1)T_{n-1}=n-1+(n-1)S_{n-1}+2\sum_{k=0}^{n-2}T_k
\end{equation*}
and subtract to get
\begin{equation*}   
nT_n-(n+1)T_{n-1}=1+nS_n-(n-1)S_{n-1}.
\end{equation*}
Divide this by $n(n+1)$:
\begin{equation*}   
\frac{T_n}{n+1}-\frac{T_{n-1}}{n}=\frac{1}{n}-
\frac{1}{n+1}+\frac{S_n}{n+1}-\frac{n-1}{n(n+1)}
S_{n-1}
\end{equation*} 
and sum this from $n=3,\dots,N$, but write again $n$  
for $N$: 
\begin{equation*}   
\frac{T_n}{n+1}-\frac{5}{3}=\frac{1}{3}-
\frac{1}{n+1}+\sum_{k=3}^n\frac{S_k}{k+1}+
\sum_{k=3}^n\Big(\frac{1}{k}-\frac{2}{k+1}\Big)
S_{k-1}
\end{equation*}
or
\begin{align*}   
\frac{T_n}{n+1}&=2-
\frac{1}{n+1}-\frac{S_n}{n+1}+\frac{2}{3}
+2\sum_{k=3}^{n}\frac{S_{k}}{k+1}-
2\sum_{k=3}^{n}\frac{S_{k-1}}{k+1}
\end{align*}
 from which we conclude that
\begin{align*}   
{T_n}&=\frac{8}{3}n+\frac{5}{3}
-{S_n}+
2(n+1)\sum_{k=3}^{n}\frac{S_k-S_{k-1}}{k+1} \quad\text{for }n\geq2.
\end{align*}
(In \cite{Shiau_Yang00b} this is slightly wrong.)
We know again
{\it a priori\/} that $T_n\sim A_2\cdot n$. Our aim is compute this 
constant $A_2$:

\begin{equation}\label{eq:sum2}
A_2=\frac83
+2\sum_{k=3}^\infty\frac{S_k-S_{k-1}}{k+1}.
\end{equation}
From the integral formula for $S_k$ we conclude that 

\begin{align*}
S_k-S_{k-1}&=
-\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{\Gamma(1-s)\Gamma(k+1)\zeta(1-s)}
{\Gamma(k+1-s) (2^s-1)}\,ds
+\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{\Gamma(1-s)\Gamma(k)\zeta(1-s)}
{\Gamma(k-s) (2^s-1)}\,ds\\
&=-\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{s\Gamma(1-s)\Gamma(k)\zeta(1-s)}
{\Gamma(k+1-s) (2^s-1)}\,ds.
\end{align*}

Define
\begin{equation*}
f(s)=\Gamma(1-s)\sum_{k\ge3}\frac1{k+1}\frac{\Gamma(k)}{\Gamma(k+1-s)},
\end{equation*}
which makes sense for $\Re s<1$. The identity
$$f(s)=\frac{6s^2-15s+4}{6(s-1)(s-2)}-\frac1s+s\psi'(-s)$$
is again a consequence of \eqref{eq:fs1} and
provides the analytic continuation of $f(s)$. Then
\begin{align*}
A_2=\frac83
+2\cdot\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{sf(s)\zeta(1-s)}
{2^s-1}\,ds.
\end{align*}
Note that
\begin{equation*}
\frac{1}{2^s-1}=\sum_{k\ge1}2^{-ks}.
\end{equation*}
Therefore
\begin{equation*}
\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
\frac{sf(s)\zeta(1-s)}
{2^s-1}\,ds=
\sum_{k\ge1}\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty}
sf(s)\zeta(1-s)2^{-ks}\,ds.
\end{equation*}
The integral
\begin{equation*}
\frac{1}{2\pi i}\int\limits_{\frac{1}{2}-i\infty}
^{\frac{1}{2}+i\infty} sf(s)\zeta(1-s)2^{-ks}\,ds
\end{equation*}
can be computed by shifting the line of integration to $\Re s=-\frac12$ (again
this is justified by the growth rate of the integrand) and expanding the
$\zeta$--function:
\begin{equation*}
\sum_{n=1}^\infty\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}
sf(s)n^{s-1}2^{-ks}\,ds.
\end{equation*}
Thus it remains to compute the function
$$\Psi(x)=\frac{1}{2\pi i}\int\limits_{-\frac{1}{2}-i\infty}
^{-\frac{1}{2}+i\infty}sf(s)x^s\,ds.$$
This is done in a similar way as above and gives
\begin{equation*}
\Psi(x)=
\begin{cases}
\dfrac{x(17-14x+13x^2-4x^3)}{6(x-1)^2}-\dfrac{x+x^2}{(x-1)^3}\log x&
\text{for }0<x\leq1\\
0&\text{for }x>1.
\end{cases}
\end{equation*}
With this notation, the constant $A_2$ evaluates to
\begin{align*}
A_2=\frac{8}{3}+2
\sum_{j\ge0} \sum_{1\le k<2^j} \frac1k\Psi\Big(\frac k{2^j}\Big)=
3.54551\,78132\,67322\,88513\,75825\,40856\,52901\,34887\ldots
\end{align*} 
(see the last section for such evaluations).

Note also that the paper \cite{Shiau_Yang00b} gives the bounds
(after correcting the simple error)
$3.33\cdots\le A_2\le 4$. 

\section{The na\"\i{}ve strategy}\label{naive}

The average cost of selecting {\it one\/} loser is given by
$c_n=1+S_n$
with the quantities $S_n$ from the introduction.
Thus we have
\begin{equation*}
c_n=2-\sum_{k=1}^{n-1}\binom{n}{k}\frac{B_k}{2^k-1}.
\end{equation*}
In total, we need to evaluate
\begin{equation*}
C_n=c_1+\dots+c_n.
\end{equation*}
We know
\begin{equation*}
\sum_{k=1}^{n-1}\binom{n}{k}\frac{B_k}{2^k-1}
=\frac{1}{2\pi i}\int\limits_{\frac12-i \infty}
^{\frac12+i \infty}
\frac{\Gamma(n+1)\Gamma(1-s)}{\Gamma(n+1-s)}
\frac{\zeta(1-s)}{2^s-1}\,ds;
\end{equation*}
since $c_1=1$ and $c_2=3$ this leads to
\begin{equation*}
C_n=2n-\sum_{k=3}^n
\frac{1}{2\pi i}\int\limits_{\frac12-i \infty}
^{\frac12+i \infty}
\frac{\Gamma(k+1)\Gamma(1-s)}{\Gamma(k+1-s)}
\frac{\zeta(1-s)}{2^s-1}\,ds.
\end{equation*}
As before we sum up the terms in the integral
$$\sum_{k=3}^n\frac{\Gamma(k+1)\Gamma(1-s)}{\Gamma(k+1-s)}=
\frac{\Gamma(n+2)\Gamma(1-s)}{(s+1)\Gamma(n+1-s)}-\frac6{(s-1)(s-2)(s+1)}$$
and obtain
\begin{align}\begin{split}
\label{eq:Cn}
C_n=2n+&\frac1{2\pi i}\int\limits_{\frac12-i \infty}^{\frac12+i \infty}
\frac6{(s-1)(s-2)(s+1)}\frac{\zeta(1-s)}{2^s-1}\,ds\\-
&\frac1{2\pi i}\int\limits_{\frac12-i \infty}^{\frac12+i \infty}
\frac{\Gamma(n+2)\Gamma(1-s)}{(s+1)\Gamma(n+1-s)}
\frac{\zeta(1-s)}{2^s-1}\,ds.
\end{split}
\end{align}
For further reference we denote
$$I=\frac1{2\pi i}\int\limits_{\frac12-i \infty}^{\frac12+i \infty}
\frac6{(s-1)(s-2)(s+1)}\frac{\zeta(1-s)}{2^s-1}\,ds.$$
Now we use
\begin{equation}
\label{eq:gammaasymp}
\frac{\Gamma(n+2)}{\Gamma(n+1-s)}=n^{s+1}\(1-\frac{(s-3)(s+1)}{2n}+
\mathcal{O}\Big(\frac{|s|^4}{n^2}\Big)\)
\end{equation}
(cf.~\cite{Abramowitz_Stegun65}) to obtain
\begin{align}\label{eq:Cnasymp}\begin{split}
C_n=2n+I-&\frac1{2\pi i}\int\limits_{\frac12-i \infty}^{\frac12+i \infty}
\Gamma(1-s)\frac{\zeta(1-s)}{2^s-1}n^{s+1}\,ds
\\
+&\frac1{2\pi i}\int\limits_{\frac12-i \infty}^{\frac12+i \infty}
\Gamma(1-s)\frac{(s-3)(s+1)}2\frac{\zeta(1-s)}{2^s-1}n^s\,ds+
\mathcal{O}(n^{-\frac12}).
\end{split}
\end{align}

We shift the line of integration to $\Re s=-\frac12$ and obtain by calculating
the residues at the poles on the line $\Re s=0$
\begin{align*}
C_n&=2n+I-
\frac1{2\pi i}\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\Gamma(1-s)\frac{
\zeta(1-s)}{2^s-1}n^{s+1}\,ds\\
&+\frac1{2\pi i}\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\Gamma(1-s)\frac{(s-3)(s+1)}2\frac{\zeta(1-s)}{2^s-1}n^s\,ds
+n\log_2n-\frac12n+nF(\log_2n)\\
&+\frac32\log_2n+\frac1{\log2}-\frac34+
G(\log_2n)+\mathcal{O}(n^{-\frac12}),
\end{align*}
where $F$ and $G$ denote two periodic continuous functions of period $1$ and
mean $0$ given by their Fourier-expansions 
($\chi_k=\frac{2k\pi i}{\log2}$)
\begin{align}\begin{split}
\label{FGFourier}
F(x)&=-\frac1{\log2}\sum_{k\in\mathbb{Z}\setminus\{0\}}
\Gamma(1-\chi_k)\zeta(1-\chi_k)e^{2k\pi ix}\\
G(x)&=-\frac1{2\log2}\sum_{k\in\mathbb{Z}\setminus\{0\}}
(1+\chi_k)(3-\chi_k)\Gamma(1-\chi_k)\zeta(1-\chi_k)e^{2k\pi ix}.
\end{split}
\end{align}
It remains to compute the integral $I$.
This is done as follows:
\begin{align*}
I&=
\sum_{k=1}^\infty\frac1{2\pi i}\int\limits_{\frac12-i\infty}^{\frac12+i\infty}
\frac6{(s-1)(s-2)(s+1)}\zeta(1-s)2^{-ks}\,ds\\
&=\sum_{k=1}^\infty\bigg(\frac1{2\pi i}
\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac6{(s-1)(s-2)(s+1)}\zeta(1-s)2^{-ks}\,ds-3\bigg)\\
&=\sum_{k=1}^\infty\sum_{n=1}^\infty\bigg(\frac1{2\pi i}
\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac6{(s-1)(s-2)(s+1)}n^{s-1}2^{-ks}\,ds-3\bigg).
\end{align*}
As before we compute the integral
$$\frac1{2\pi i}
\int\limits_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac6{(s-1)(s-2)(s+1)}
x^s\,ds=
\begin{cases}
3x-2x^2&\text{for }0<x\leq1\\
\frac1x&\text{for }x>1.
\end{cases}
$$
We obtain
$$I=\sum_{k=1}^\infty\bigg(\sum_{n=1}^{2^k}\frac1n\(3\(\frac n{2^k}
\)-
2\(\frac n{2^k}\)^2\)+2^k\sum_{n=2^k+1}^\infty\frac1{n^2}-3\bigg).$$
After summing up the first sum and some obvious cancellation we arrive at
$$I=\sum_{k=1}^\infty\bigg(2^k\sum_{n=2^k}^\infty\frac1{n^2}-1
\bigg)-2.$$
This can be computed by the methods outlined in section~\ref{sec:howto}; the
numerical value is given by
$$I=-1.44637\,64113\,48039\,93349\,42661\,97916\,01589\,56591\,06916\ldots.$$

This gives
$$C_n=n\log_2n+\frac32n+nF(\log_2n)+\frac32\log_2n+B+G(\log_2n)+
\mathcal{O}(n^{-\frac12})$$
with
$$B=\frac1{\log2}-\frac34+I=
-0.75368\,13704\,59076\,52613\,43415\,16914\,12375\,82324\,60962\ldots\,.$$




\section{Mellin Integrals}\label{sec:mellin}
One possible way to give a reasonably convergent series expansion for the value
of an integral of the form
\begin{equation}
\label{eq:int}
\frac1{2\pi i}\int\limits_{\frac12-i\infty}^{\frac12+i\infty}
f(s)\frac{\zeta(1-s)}{2^s-1}\,ds
\end{equation}
would be to move the line of integration to the left. This yields
\begin{equation}\label{eq:intsum}
\frac1{2\pi i}\int\limits
_{\frac12-i\infty}^{\frac12+i\infty}
f(s)\frac{\zeta(1-s)}{2^s-1}\,ds=
\sum_{k\in\mathbb{Z}}\Res_{s=\chi_k}\Big\{f(s)\frac{\zeta(1-s)}{2^s-1}
\Big\}+
\frac1{2\pi i}\int\limits
_{-\frac12-i\infty}^{-\frac12+i\infty}
f(s)\frac{\zeta(1-s)}{2^s-1}\,ds,
\end{equation}
where again $\chi_k=\frac{2k\pi i}{\log2}$.
Under the growth condition $|f(s)|=\mathcal{O}(|s|^{-2})$ the last integral is
zero by the same arguments as used above. Thus we have a series expansion for
the integral \eqref{eq:int}
\begin{equation}\label{eq:res}
\frac1{\log2}\sum_{k\in\mathbb{Z}\setminus\{0\}}f(\chi_k)\zeta(1-\chi_k)+
\Res_{s=0}\Big\{f(s)\frac{\zeta(1-s)}{2^s-1}\Big\}.
\end{equation}

Unfortunately, the rate of convergence of this sum is not much better than the
rate of convergence of the sums \eqref{eq:sum1} and \eqref{eq:sum2}. Thus this
method does not yield a numerically feasible method to compute integrals of the
form \eqref{eq:int} to high precision, although it is possible to get a few
digits by using \eqref{eq:res}, as pointed by one of the referees.
The next section will describe how to find high precision
approximations to the numerical value of such integrals.

\section{How to compute the integrals numerically}\label{sec:howto}
In this section we discuss how
to compute a sums like
\begin{equation}\label{eq:S1}
\Sigma_1=\sum_{j\ge0}\sum_{1\le k<2^j}\frac{2^{-j}}{k}
\Phi\Big(\frac{k}{2^j}\Big)\quad\text{and}\quad
\Sigma_2=\sum_{j\ge0}\sum_{1\le k<2^j}\frac1{k}
\Phi\Big(\frac{k}{2^j}\Big)
\end{equation}
numerically. We assume that $\Phi\in C^{2m}(0,1]$, $\Phi(0)=D$, and
\begin{equation}\label{eq:asym}
\frac{\Phi(t)-D}t=\sum_{\ell=0}^{2m}C_\ell t^\ell\log t+Q_{2m}(t)+
O(t^{2m+1}\log t),
\end{equation}
where $Q_{2m}\in C^{2m+1}[0,1]$ and $C_\ell$ are
constants (these two properties are satisfied for the functions to which
these studies will be applied later).

In the sequel we will use the Bernoulli-polynomials $P_k(t)$ defined by
$$\sum_{\ell=0}^\infty P_\ell(t)\frac{z^\ell}{\ell!}=\frac{ze^{zt}}{e^z-1}$$
and the Bernoulli numbers $B_\ell=P_\ell(0)$. Throughout this section we use
the notation $\{x\}$ to indicate the fractional part of $x$.

Then we have
\begin{align*}
\sum_{1\leq k\leq2^j}&\frac1k f\Big(\frac k{2^j}\Big)=
\sum_{k=1}^{2^j}\frac1k\left(f\Big(\frac k{2^j}\Big)-D\right)+
D\sum_{k=1}^{2^j}\frac1k\\
&=\sum_{k=1}^{2^j}\frac1k\left(f\Big(\frac k{2^j}\Big)-D\right)\\
&\qquad+D\bigg(j\log2+\gamma+\frac1{2^{j+1}}-
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}\frac1{2^{2\ell j}}+
2^{-(2m+1)j}\int\limits_1^\infty P_{2m+1}(\{2^jx\})x^{-2m-2}\,dx
\bigg)\\
&=2^{-j}\sum_{k=1}^{2^j}\bigg[\frac{2^j}k\left(
f\Big(\frac k{2^j}\Big)-D\right)-
\sum_{\ell=0}^{2m}C_\ell\Big(\frac k{2^j}\Big)^\ell
\log\frac k{2^j}\bigg]\\
&\qquad+\sum_{\ell=0}^{2m}C_\ell2^{-j}\sum_{k=1}^{2^j}
\Big(\frac k{2^j}\Big)^\ell\log\frac k{2^j}
+D\bigg(j\log2+\gamma+\frac1{2^{j+1}}-
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}\frac1{2^{2\ell j}}+
R_j\bigg)
\end{align*}
where $|R_j|\leq\frac1{2m+1}\|P_{2m+1}\|_\infty2^{-(2m+1)j}$.

We set $g(t)=g_{2m}(t)=\frac{f(t)-D}t-\sum_{\ell=0}^{2m}C_\ell t^\ell\log t$;
under our assumptions on $f$, 
the function $g$ is $2m$ times differentiable on $[0,1]$ and
the $(2m+1)$--st derivative is in $L^1[0,1]$. Then we have
\begin{align}\label{eq:gsum}
2^{-j}&\sum_{k=1}^{2^j}g\Big(\frac k{2^j}\Big)=
\int\limits_0^1g(t)\,dt+\frac12\big(g(1)-g(0)\big)2^{-j}
+\sum_{\ell=1}^m\frac{B_{2\ell}}{(2\ell)!}
\(g^{(2\ell-1)}(1)-g^{(2\ell-1)}(0)\)
2^{-2\ell j}\notag\\
&\qquad+
\frac1{(2m+1)!}2^{-(2m+1)j}\int\limits_0^1\!
P_{2m+1}(\{2^jx\})g^{(2m+1)}(x)\,dx\\
&=\int\limits_0^1g(t)\,dt+\frac12\big(g(1)-g(0)\big)2^{-j}+
\sum_{\ell=1}^m\frac{B_{2\ell}}{(2\ell)!}\(g^{(2\ell-1)}(1)-g^{(2\ell-1)}(0)\)
2^{-2\ell j}+R_j'\notag
\end{align}
with $|R'_j|\leq\frac1{(2m+1)!}\|P_{2m+1}\|_\infty \|g^{(2m+1)}\|_1$.

Finally, we compute the sums
\begin{equation}\label{eq:logsum}
2^{-j}\sum_{k=1}^{2^j}\Big(\frac k{2^j}\Big)^r\log\frac k{2^j}
\end{equation}
for $r\in\mathbb{N}_0$ using the Euler-MacLaurin summation formula. For this
purpose we first compute the sum
\begin{align}\label{eq:ssum}\begin{split}
2^{-(s+1)j}\sum_{k=1}^{2^j}k^s&=\frac1{s+1}+\frac1{2^{1+j}}+
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}\binom s{2\ell-1}2^{-2\ell j}+
2^{-js}\zeta(-s)\\
&-2^{-(2m+1)j}\binom s{2m+1}\int\limits_1^\infty
P_{2m+1}(\{2^jx\})x^{s-2m-1}\,dx;\end{split}
\end{align}
here we have used the identity (cf.~\cite{Ivic85})
$$\zeta(-s)=-\frac1{s+1}+\frac12-
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}\binom s{2\ell-1}+
\binom s{2m+1}\int\limits_1^\infty P_{2m+1}(\{x\})x^{s-2m-1}\,dx,$$
which is valid for $\Re s<2m$.

Differentiating \eqref{eq:ssum} and setting $s=r\in\mathbb{N}_0$ yields
\begin{align}\label{eq:logsum1}
2^{-j}\sum_{k=1}^{2^j}\Big(\frac k{2^j}\Big)^r\log\frac k{2^j}
&=-\frac1{(r+1)^2}+
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}
\frac{d}{ds}\binom s{2\ell-1}\biggr|_{s=r}2^{-2\ell j}\notag\\
&+
j2^{-jr}\zeta(-r)\log2-
2^{-jr}\zeta'(-r)\\&-
2^{-(2m+1)j}\frac{d}{ds}\binom s{2m+1}\biggr|_{s=r}
\int\limits_1^\infty P_{2m+1}(\{2^jx\})x^{r-2m-1}\,dx;\notag
\end{align}
here we have used that $\binom r{2m+1}=0$ 
for $r<2m$. We note also that
$\zeta(-r)=-\frac{B_{r+1}}{r+1}$ for $r\geq1$ and $\zeta(0)=-\frac12$.

Finally, we observe that
$$\frac{d}{ds}\binom s{2\ell-1}\biggr|_{s=r}=
\begin{cases}\displaystyle{
(-1)^r\dfrac{r!(2\ell-r-2)!}{(2\ell-1)!}}&\text{for }r\leq2\ell-2\\
\displaystyle{
\binom r{2\ell-1}\sum\limits_{t=0}^{2\ell-2}
\frac1{r-t}}&\text{for }r>2\ell-2.
\end{cases}
$$
Inserting this into \eqref{eq:logsum1} and estimating the integral trivially
yields
\begin{align}\label{eq:logsum2}\begin{split}
2^{-j}\sum_{k=1}^{2^j}\Big(\frac k{2^j}\Big)^r\log\frac k{2^j}&=
-\frac1{(r+1)^2}+
\sum_{\ell=1}^{\lfloor\frac {r+1}2\rfloor}\frac{B_{2\ell}}{2\ell}
\binom r{2\ell-1}\sum_{t=0}^{2\ell-2}\frac1{r-t}2^{-2\ell j}\\
&+j2^{-jr}\zeta(-r)\log2-2^{-jr}\zeta'(-r)\\&-
(-1)^r\sum_{\ell=\lfloor\frac{r+3}2\rfloor}^m\frac{r!(2\ell-r-2)!}{(2\ell-1)!}
\frac{B_{2\ell}}{2\ell}2^{-2\ell j}+R_{j,r}
\end{split}\end{align}
with $|R_{j,r}|\leq\frac{r!(2m-r-1)!}{(2m+1)!}2^{-(2m+1)j}\|P_{2m+1}\|_\infty$.

Extending the last sum \eqref{eq:logsum2} to $m+2$ for $r=2m$ and putting
everything together we obtain (the $C_0j2^{-j}\log2$--term 
in the fourth
line is to compensate the difference between $\zeta(0)$ and $B_1$)
\begin{align}
&\sum_{k=1}^{2^j}\frac1k f\Big(\frac k{2^j}\Big)=
D\bigg(j\log2+\gamma+\frac1{2^{j+1}}-
\sum_{\ell=1}^m\frac{B_{2\ell}}{2\ell}2^{-2\ell j}+
R_j\bigg)+\notag\\
&\int\limits_0^1\frac{f(t)-D}t\,dt+\frac12\big(g(1)-g(0)\big)2^{-j}+
\sum_{\ell=1}^m\frac{B_{2\ell}}{(2\ell)!}\(g^{(2\ell-1)}(1)-g^{(2\ell-1)}(0)\)
2^{-2\ell j}+\label{eq:asum}\\
&C_0j2^{-j}\log2+\sum_{r=0}^{2m}C_r\Biggl(
\sum_{\ell=1}^{\lfloor\frac r2\rfloor}\frac{B_{2\ell}}{2\ell}
\binom r{2\ell-1}\sum_{t=0}^{2\ell-2}\frac1{r-t}2^{-2\ell j}+
j2^{-j(r+1)}\frac{B_{r+1}}{r+1}\log2-\notag\\
&2^{-j(r+1)}\zeta'(-r)-
(-1)^r\sum_{\ell=\lfloor\frac{r+2}2\rfloor}^m\frac{r!(2\ell-r-2)!}{(2\ell-1)!}
\frac{B_{2\ell}}{2\ell}2^{-2\ell j}\Biggr)+\widetilde R_j\notag
\end{align}
with
\begin{align*}
|\widetilde R_j|&\leq 2^{-(2m+1)j}\|P_{2m+1}\|_\infty
\(\frac D{2m+1}+\frac1{(2m+1)!}\|g^{(2m+1)}\|_1+
\sum_{r=0}^{2m-1}C_r\frac{r!(2m-r-1)!}{(2m+1)!}\)\\
&+C_{2m}\(|\zeta'(-2m)|2^{-(2m+1)j}+|B_{2m+2}|2^{-2j(m+1)}+
\frac{\|P_{2m+3}\|}{2m+1}2^{-j(2m+3)}\);
\end{align*}
here we have used that
$$\int\limits_0^1\frac{f(t)-D}t\,dt=\int\limits_0^1g(t)\,dt-
\sum_{r=0}^{2m}\frac{C_r}{(r+1)^2}.$$

For the function
$$f(t)=\Phi(t)=
\frac{(3-t)(1+t+t^2)}{3(1-t)^2}+\frac{2t\log t}{(1-t)^3}$$
we have $D=1$ and $C_r=(r+1)(r+2)$, and
$\int\limits_0^1\frac{f(t)-1}t\,dt=-\frac{11}6$.

For a numerical approximation of \eqref{eq:S1} we split summation at $J$ and
replace the infinite part of the sum by the asymptotic estimate
\eqref{eq:asum}. For $J=10$ and $m=10$ this gives an error estimate of
$2.152\cdot10^{-45}$. Thus we have
$$S_1=0.75657\,97214\,59537\,81423\,
01968\,71433\,28464\,81778\,24250\,446\ldots$$

In a similar way we can treat the sum
$$S_2=\sum_{j\ge0}\sum_{1\le k<2^j} \frac1k\Psi\Big(\frac k{2^j}\Big)$$
In this case $D=0$ and $\int\limits_0^1\frac{\Psi(x)}x\,dx=0$. 
 For $J=8$ and $m=10$ we
obtain an error estimate of $2.0765\cdot10^{-48}$. Thus we have
$$S_2=0.43942\,55733\,00328\,10923\,
54579\,37094\,93117\,34110\,28053\ldots$$

\section{Concluding remarks}\label{sec:concl}
The method for the numerical computation of Mellin integrals as described in
section~\ref{sec:howto} can be easily generalized to integrals of the form
$$\int\limits_{c-i\infty}^{c+i\infty}f(s)\frac{\zeta(1-s)}{A^s-1}\,ds
\quad\text{for }A>1,$$
where $f(s)$ is a meromorphic function in the whole complex plane satisfying
the following properties:
\begin{itemize}
\item $f(s)=\mathcal{O}(|s|^{-1-\eps})$ for some positive $\eps$ and
  $|\arg(-s)|<\pi$
\item $f(s)$ has no poles left of a line $\Re s=\sigma_0$
\item the sum over the residues $\Res f(s)x^s$ converges for $0<x<1$.
\end{itemize}
If $A$ is not an integer one has to use a slightly changed version of the
Euler-MacLaurin summation formula:
\begin{align*}
\sum_{1\leq k<A^n}g\(\frac k{A^n}\)&=A^n\int\limits_0^1g(x)\,dx-
\frac12g(0)+\left(\{A^n\}-\frac12\right)g(1)\\
&+\sum_{\ell=1}^m\frac{B_{2\ell}}{(2\ell)!}
\(g^{(2\ell-1)}(1)-g^{(2\ell-1)}(0)\)A^{-(2\ell-1)n}\\
&+\frac1{(2m+1)!}\int\limits_0^1P_{2m+1}(\{A^nx\})g^{(2m+1)}(x)\,dx.
\end{align*}
Again singularities of $g$ have to be subtracted as shown in
section~\ref{sec:howto}.
\bigskip

{\bf Acknowledgment.} We thank two anonymous referees and Hsien--Kuei~Hwang
for their valuable remarks.
\begin{thebibliography}{10}

\bibitem{Abramowitz_Stegun65}
M.~Abramowitz and I.~A. Stegun.
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover, New York, 1965.

\bibitem{Andrews_Askey_Roy99}
G.~Andrews, R.~Askey, and R.~Roy.
\newblock {\em Special Functions}.
\newblock Number~71 in Encyclopedia of Mathematics and its Applications.
  Cambridge University Press, 1999.

\bibitem{Fill_Mahmoud_Szpankowski96}
J.~A. Fill, H.~M. Mahmoud, and W.~Szpankowski.
\newblock On the distribution for the duration of a randomized leader election
  algorithm.
\newblock {\em Ann. Appl. Probab.}, 6:1260--1283, 1996.

\bibitem{Flajolet_Sedgewick95}
P.~Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: finite differences and {R}ice's
  integrals.
\newblock {\em Theor. Comput. Sci.}, 144(1--2):101--124, June 1995.

\bibitem{Grabner_Prodinger98}
P.~Grabner and H.~Prodinger.
\newblock An asymptotic study of a recursion occurring in the analysis of an
  algorithm on broadcast communication.
\newblock {\em Inf. Process. Lett.}, 65:89--93, 1998.

\bibitem{Grabner93}
P.~J. Grabner.
\newblock Searching for losers.
\newblock {\em Random Structures and Algorithms}, 4:99--110, 1993.

\bibitem{Ivic85}
A.~Ivi\'c.
\newblock {\em The Riemann Zeta-Function}.
\newblock J. Wiley, New York, 1985.

\bibitem{Janson_Szpankowski97}
S.~Janson and W.~Szpankowski.
\newblock Analysis of an asymmetric leader election algorithm.
\newblock {\em Electron. J. Comb.}, 4:\#R17, 17 pages, 1997.

\bibitem{Mathys_Flajolet85}
P.~Mathys and P.~Flajolet.
\newblock Q--ary collision resolution algorithms in random access systems with
  free or blocked channel access.
\newblock {\em IEEE Transactions on Information Theory}, IT-31(2):217--243,
  March 1985.

\bibitem{Nielsen06}
N.~Nielsen.
\newblock {\em Handbuch der Theorie der Gammafunktion}.
\newblock Teubner, Leipzig, 1906.

\bibitem{Prodinger93}
H.~Prodinger.
\newblock How to select a loser.
\newblock {\em Discrete Math.}, 120:149--159, 1993.

\bibitem{Sedgewick_Flajolet96}
R.~Sedgewick and P.~Flajolet.
\newblock {\em Introduction to the Analysis of Algorithms}.
\newblock Addison-Wesley, Reading, Massachusetts, 1996.

\bibitem{Shiau_Yang96}
S.-H. Shiau and C.-B. Yang.
\newblock A fast maximum finding algorithm on broadcast communications.
\newblock {\em Inf. Process. Lett.}, 60:81--89, 1996.

\bibitem{Shiau_Yang00a}
S.-H. Shiau and C.-B. Yang.
\newblock A fast sorting algorithm and its generalization on broadcast
  communications.
\newblock preprint, 18 pages, 2000.

\bibitem{Shiau_Yang00b}
S.-H. Shiau and C.-B. Yang.
\newblock Sorting algorithms on broadcast communications: Algorithm and
  fundamental analysis.
\newblock in preparation, 2000.

\bibitem{Titchmarsh39}
E.~C. Titchmarsh.
\newblock {\em The Theory of Functions}.
\newblock Oxford University Press, 1939.

\end{thebibliography}
\end{document}
