%Discrete Mathematics


\input amstex
\documentstyle{amsppt}

\parindent =10 pt
\parskip = 6 pt

\topmatter

\title
How to select a loser
\endtitle

\author
Helmut Prodinger
\endauthor

\affil
Department of Algebra and Discrete Mathematics\\
Technical University of Vienna\\
A-1040 Vienna, Austria
\endaffil

\address
{Technical University  of Vienna
\newline Wiedner Hauptstra{\ss}e 8-10 \newline
A-1040 Vienna \newline AUSTRIA}
\endaddress
\abstract{ $N$ people select a {\it loser} 
by flipping coins. Recursively, the
0-party continues until the loser is found. Among other things, it is
shown that this process stops on the average after about $\log_2N$ steps.
Nevertheless, this very plausible result requires rather advanced 
methods.}
\endabstract
\endtopmatter

\document

\heading
1. Introduction
\endheading

Assume that a party of $N$ people wants to select one of their members
(the {\it loser}) e.g. in order to pay a beer for everybody. The procedure
is as follows: Everybody is flipping a coin (with outputs
0 and 1, each with probability $\frac 12$); then, recursively, the 0-party
is selecting one of their members. However, there is one exception:
If all people have thrown a ``1'', then they have to repeat the procedure.

The following example illustrates the idea.

\vskip 6 cm
$$
\text{Fig.1}
$$

What is produced by the above mentioned mechanism might be called an 
{\it incomplete trie}. 
In this figure a left branch is labelled by a {\it 0}
and a right branch by a {\it 1}.
For tries and related data structures we refer to
\cite {4}. The idea of splitting the party by flipping a coin was also
used in the {\it tree protocol} of Capetanakis and Tsybakhov 
(see \cite {5} for a survey).

In the following we analyze the {\it size} of the tree, i.e the number of
nodes. (In the example the size is 8.) 
It will turn out
that the average size is about $2\log_2 N$; for a more precise statement see
the following sections.

Another parameter of interest is the number of times the party has to
flip the coins (= the {\it depth}). (In the example this number is 4.)


Also, we consider the total number of coin flippings. (In the example
this number is 28.)

It is worthwhile to mention that, even though the problem seems to be very
simple, the analysis is not totally trivial.


\heading
2. Preliminaries
\endheading

Here we list some notational conveniences, as well as some basic 
pro\-perties
of the Bernoulli numbers, since they are needed in the sequel
(compare e.g. \cite 3).

We write $[z^n]f(z)$ for the coefficient of $z^n$ in the series $f(z)$.
Quite naturally we have
$$
\left[ \frac{z^n}{n!} \right] f(z) = n! \left[ z^n \right] f(z).
$$
Abbreviations:
$$
L=\log 2 \qquad \text{and} \qquad \chi_k =\frac{2k\pi i}L, 
\quad k \in \Bbb Z.
$$
$\zeta(s)$ denotes Riemann's $\zeta$--function; $\Gamma(s)$ the
$\Gamma$--function; $\gamma$ is Euler's constant; $\gamma =0.57721$.

The Bernoulli numbers $B_n$ are defined by
$$
B_n=\left[\frac{z^n}{n!}\right] \frac z{e^z-1}.
$$
Similarly, the Bernoulli polynomial $B_n(t)$ is defined by
$$
\frac{ze^{tz}}{e^z-1} =\sum_{k\ge 0} B_k(t)\frac{z^k}{k!}.
$$
Properties:
$$
B_n(0)=B_n(1)=B_n \quad
\text{for} \ n \ge 2;\  B_0=1,\  B_1=-\frac 12,
$$
$$
B_n(x)=\sum_{k=0}^n \binom nk B_kx^{n-k}
$$
and thus
$$
B_n=\sum_{k=0}^n \binom nk B_k\quad\text{and}\quad
B_n\big(\frac 12\big)=-\Big(1-2^{1-n}\Big)B_n.
$$
Also, we may express the Bernoulli numbers by the $\zeta$--function:
$$
B_k=-k\zeta(1-k)\quad \text{for}\ k\ge 2.
$$

\heading
3. The average size
\endheading

The style of the following analysis follows \cite{4}; we mention
also \cite{6}.

\proclaim {Proposition 1} The probability generating function $F_N(z)$
fulfills the following recursion:
$$
\aligned
F_N(z)&=z^2\sum_{k=0}^N 2^{-N}\binom Nk F_k(z)
+z(1-z)2^{-N}F_N(z)\\
-&z^22^{-N}+z2^{-N}F_N(z) \
\text{for} \ N\ge 2; \ F_0(z)=1, \ F_1(z)=z.
\endaligned
$$
\endproclaim

\demo{Proof} $2^{-N}\binom Nk$ is the probability that $k$ out of 
$N$ people
have thrown a 0; $z^2$ measures two extra nodes obtained by this splitting.
The extra terms are related to the cases $k=0$ or $k=N$. 
In these two cases there is only one extra node generated, which is measured
by a $z$. 
\enddemo

Let $l_N = F_N'(1)$ denote the average size. The following recursion 
follows immediately from Proposition 1 by differentiation:
 
\proclaim {Proposition 2} We have $l_0=0$, $l_1=1$ and for $N \ge 2$
$$
l_N = 2 + \frac 1{1-2^{-N}}\sum_{k=0}^N 2^{-N}\binom Nk l_k.
$$
\endproclaim

Now we introduce the {\it exponential generating function} 
$\displaystyle{
L(z)=\sum_{k\ge 0} l_k\frac{z^k}{k!}.
}$
Then the recursion for the $l_n$'s turns into a functional equation for
$L(z)$.

\proclaim {Proposition 3}
$$
L(z)-L\big(\frac z2\big)=2e^z-2e^{z/2}-z + e^{z/2}L\big(\frac z2\big).
$$
\endproclaim

The equation becomes easier by introducing
$$
\hat L(z)= \frac{L(z)}{e^z-1} =\sum_{k\ge 0} \hat l_k \frac{z^k}{k!}.
$$
\proclaim {Proposition 4}
$$
\hat L (z) = \hat L \big(\frac z2
\big) + \frac{2e^z-2e^{z/2}-z}{e^z-1}.
$$
\endproclaim

\proclaim {Proposition 5} 
$\hat l_0=1$ and for $N\ge 1$ we have
$$
\hat l_N = \frac 1{1-2^{-N}}\frac 2{N+1}B_{N+1}
+\frac 2{N+1}B_{N+1}- \frac{B_N}{1-2^{-N}}.
$$
\endproclaim

\demo {Proof}
From Proposition 4 we find that for $N\ge 1$
$$
\aligned
\hat l_N (1-2^{-N}) &= \left[\frac{z^N}{N!}
\right]\frac{2e^z-2e^{z/2}-z}{e^z-1}\\
&=\frac 2{N+1} \left[\frac{z^{N+1}}{(N+1)!}\right]\frac{ze^z}{e^z-1}\\
&-\frac 2{N+1}\left[\frac{z^{N+1}}{(N+1)!}\right]
\frac{ze^{z/2}}{e^z-1}-B_N\\
&=
\frac 2{N+1}B_{N+1}(1)-\frac 2{N+1}B_{N+1}\big(\frac 12\big)-B_N.
\endaligned
$$
The final formula follows from the properties of the Bernoulli numbers.
\enddemo

Now, since $L(z)=\big(e^z-1\big)\hat L(z)$, we find
$$
\aligned
l_N&=\sum_{k=0}^{N-1}\binom Nk \hat l_k\\
&=1+\sum_{k=1}^{N-1} \binom Nk \frac 1{1-2^{-k}}\frac 2{k+1}B_{k+1}\\
&+\sum_{k=1}^{N-1} \binom Nk \frac 2{k+1}B_{k+1}-
\sum_{k=1}^{N-1} \binom Nk \frac{B_k}{1-2^{-k}}\\
&=1+S_1+S_2+S_3.
\endaligned
$$
The sum $S_2$ is the easiest:
$$
\aligned
S_2&= \frac 2{N+1}\sum_{k=1}^{N-1}\binom{N+1}{k+1}B_{k+1}\\
&=\frac 2{N+1}\left[
\sum_{k=0}^{N+1}\binom{N+1}kB_k -B_{N+1}-(N+1)B_1-B_0\right]\\
&=1-\frac 2{N+1}\sim 1.
\endaligned
$$  
Next we turn to $S_1$:
$$
\aligned
S_1&=
\sum_{k=1}^{N-1} \binom Nk \frac 2{k+1}B_{k+1}\left(1+
\frac 1{2^k-1}\right)\\
&=S_2+\frac 2{N+1}\sum_{k=2}^N\binom{N+1}k\frac {B_k}{2^{k-1}-1}.
\endaligned
$$
The remaining sum was studied in Knuth \cite{4, p.503}:

\proclaim {Theorem 6} {\rm [Knuth]}
$$
S:=\frac 1n \sum_{k=2}^{n-1}\binom nk \frac {B_k}{2^{k-1}-1}
\sim \frac 12 \log_2n -\frac 12\log_2\pi +\frac{\gamma}{2L} -\frac 34
+\delta_1(\log_2n),
$$
with the periodic function (of period 1 and very small amplitude)
$$
\delta_1(x)=\frac 1L\sum_{k\ne 0}\zeta(-\chi_k)\Gamma(-\chi_k)e^{2k\pi ix}.
\qed
$$
\endproclaim

With this result we can formulate an asymptotic equivalent for the sum $S_1$:
$$
S_1 \sim \log_2 N -\log_2\pi +\frac{\gamma}{L}-\frac 12 +2\delta(\log_2N).
$$
Now we turn to the computation of the last sum, $S_3$:
$$
S_3=- \sum_{k=1}^{N-1}\binom Nk B_k \left[1+ \frac 1{2^k-1}\right].
$$
According to this decomposition we find that the first sum equals $1$ and
analyze the second one:

\proclaim {Theorem 7}
$$
S:=\sum_{k=1}^{n-1}\binom nk \frac {B_k}{2^k-1}
\sim -\log_2n+\frac 12 
+\delta_2(\log_2n),
$$
with the periodic function (of period 1 and very small amplitude)
$$
\delta_2(x)=\frac 1L\sum_{k\ne 0}\zeta(1-\chi_k)
\Gamma(1-\chi_k)e^{2k\pi ix}.
$$
\endproclaim
\demo{Proof}
Instead of following Knuth's approach (cf.Theorem 6) (Mellin transforms)
we use ``Rice's method'' (see \cite{1} for a good introduction). An
equivalent methodology was given by W. Szpankowski in \cite{7}. From this,
we can express the sum $S$ as a contour integral
$$
S=\frac{1}{2\pi i}\int\limits_{\frac 12-i\infty}^{\frac 12+i\infty}
\frac{(-1)^nn!}{(z-1)(z-2)\dots (z-n)}\cdot \frac{\zeta(1-z)}{2^z-1}dz.
$$
Shifting the line of integration to the left and collecting the residues
gives the asymptotic expansion. The dominant poles are at $z=0$ and
$z=\chi_k$, $k\in \Bbb Z$, $k\ne 0$.

The local expansions for $z\to 0$ are
$$
\aligned
\frac{(-1)^nn!}{(z-1)(z-2)\dots (z-n)}&\sim 1+zH_n\\
\zeta(1-z)&\sim -\frac 1z\left(1-\gamma z\right)\\
\frac{1}{2^z-1}&\sim \frac{1}{Lz}\left(1-\frac{Lz}2\right)
\endaligned
$$
with $H_n=1+\frac 12+\dots+\frac 1n\sim\log n+\gamma$ being the $n$--th
harmonic number.
The residue at $z=0$ is therefore
$$
\aligned
\left[z^{-1}\right]&-\frac{1}{Lz^2}\left(1+zH_n\right)(1-\gamma z)
\left(1-\frac{Lz}{2}\right)\\
&=-\frac 1L \left(H_n-\gamma-\frac L2\right)\\
&\sim -\log_2n+\frac 12.
\endaligned
$$
The residue at $z=\chi_k$ is $\frac 1L\Gamma(1-\chi_k)\zeta(1-\chi_k)$.
This may be seen by expressing 
$$
\frac{(-1)^nn!}{(z-1)(z-2)\dots (z-n)}
\quad\text{as}\quad
\frac{\Gamma(n+1)\Gamma(1-z)}{\Gamma(n+1-z)}.
$$
So the function $\delta_2(x)$ is obtained, since
$n^{\chi_k}=e^{2k\pi i\cdot \log_2n}$.

\enddemo

Therefore we find that the sum $S_3$ can be approximated by
$$
S_3\sim \log_2n+\frac12 -\delta_2\left(\log_2N\right).
$$
Now we get our main result by collecting $1+S_1+S_2+S_3$:


\proclaim{Theorem 8}
The average size $l_N$ of the tree built by $N$ people who are selecting a 
loser
by a coin flipping process is
$$
l_N\sim 2\log_2N-\log_2\pi+\frac{\gamma}L+2+2\delta_1(\log_2N)-\delta_2
(\log_2N).
$$
The constant $-\log_2\pi+\frac{\gamma}L+2$ is $=1.181250048$.
\endproclaim


\heading
4. The average depth
\endheading

The analysis of the depth is a little bit easier than the size and almost
included in the computations from Section 3. 
Especially, as was observed in \cite{6}, the methodology to solve recursions
as in Section 3 is general enough to deal with all the following ones.
We just state the analogous
propositions:

\proclaim {Proposition 9}
The probability generating function $G_N(z)$ fulfills for $N\ge 2 \ $ 
$(G_0(z)=G_1(z)=1)$:
$$
G_N(z)=z\sum_{k=0}^{N}2^{-N}\binom NkG_k(z)-z2^{-N}+z2^{-N}G_N(z).
$$
\endproclaim
Set $d_N=G'_N(1)$.
\proclaim {Proposition 10}  We have $d_0=d_1=0$ and
for $N\ge 2$:
$$
d_N\left(1-2^{-N}\right)=1+\sum_{k=0}^{N}2^{-N}\binom Nkd_k.
$$
\endproclaim

Set 
$$
D(z)=\sum_{k\ge 0} d_k\frac{z^k}{k!} \quad \text{and} \quad
\hat D(z)=
\frac{D(z)}{e^z-1}=\sum_{k\ge 0} \hat d_k\frac{z^k}{k!}.
$$
\proclaim{Proposition 11}
$$
D(z)-D\left(\frac z2\right)=e^z-1-z + e^{z/2}D\left(\frac z2\right)
$$
\endproclaim
\proclaim {Proposition 12}
$$
\hat D (z) = \hat D \left(\frac z2
\right) + 1-\frac{z}{e^z-1}.
$$
\endproclaim

\proclaim {Proposition 13} 
$\hat d_0=1$ and for $N\ge 1$ we have
$$
\hat d_N = 
- \frac{B_N}{1-2^{-N}}.
$$
\endproclaim

Therefore we find that $d_N$ equals $S_3$ from Section 1 and we have:

\proclaim{Theorem 14}
The average depth $d_N$ of the tree built by $N$ people 
who are selecting a 
loser
by a coin flipping process is
$$
d_N\sim \log_2N+\frac 12 -\delta_2 (\log_2N).
$$
\endproclaim


\heading
5. The average number of coin flippings
\endheading

Now we count the total number of coin flippings during the process; if 
each of the $N$ people flips a coin, this contributes $N$ to the total
number. Surprisingly there is an easy exact formula for the average:

\proclaim{Theorem 15}
The average total number $c_N$ of coin flippings performed
by $N$ people who are selecting a loser is
$$
c_N=2N \quad \text{for} \ \ N\ge 2, \quad  c_0=c_1=0.
$$
\endproclaim

\demo{Proof}
We use some obvious notations in the style of the preceeding sections.
$$
\aligned
F_N(z)=z^N\sum_{k=0}^N2^{-N}\binom Nk F_k(z) &-z^N2^{-N}
+z^N2^{-N}F_N(z)\\
&\text{for}\ N\ge 2, \quad F_0(z)=F_1(z)=1.
\endaligned
$$
$$
c_N\left(1-2^{-N}\right)=N+\sum_{k=0}^N2^{-N}\binom Nk c_k
\quad \text{for}\ N\ge 2, \quad c_0=c_1=0.
$$
$$
C(z)-C\Big(\frac z2\Big)=z\left(e^z-1\right)+e^{z/2}C\Big(\frac z2\Big).
$$
$$
\hat C(z)=z+\hat C\Big(\frac z2\Big).
$$
$$
\hat c_N\left(1-2^{-N}\right)=0 \quad \text{for}\   N\ne 1, 
\quad \hat c_1=2.
$$
$$
c_N=\sum_{k=0}^{N-1}\binom Nk \hat c_k =2N.
$$
\enddemo


\heading
6. A draw is possible
\endheading

We might think about stopping the process if exactly 2 people are fighting
about being the loser (because it is unfair; they should share the costs
for the beers!). In this section we consider the averages from before in
this model. We use the notations from the preceeding sections, but with the
slightly different meaning.

We need yet another asymptotic formula involving the Bernoulli 
numbers:

\proclaim {Theorem 16} 
$$
S:=n \sum_{k=0}^{n-1}\binom nk \frac {B_k}{2^{k+1}-1}
\sim \frac{\pi^2}{6L}
+\delta_3(\log_2n),
$$
with the periodic function (of period 1 and very small amplitude)
$$
\delta_3(x)=\frac 1L\sum_{k\ne 0}\zeta(2-\chi_k)
\Gamma(2-\chi_k)e^{2k\pi ix}.
$$
\endproclaim

\demo{Proof}
As in the proof of Theorem 7, we express $S$ as a contour integral:
$$
S=n\cdot\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}^{-\frac 12+i\infty}
\frac{(-1)^nn!}{(z-1)(z-2)\dots (z-n)}\cdot \frac{\zeta(1-z)}{2^{z+1}-1}dz.
$$
The residues at $z=-1$ and $z=-1+\chi_k$, $k\ne 0$, give the asymptotic
formula (observe that $\zeta(2)=\dfrac{\pi^2}{6}$).





\enddemo

\proclaim {Theorem 17}
$$
d_N\sim \log_2N+\frac 12-\frac{\pi^2}{12L}-\delta_2(\log_2N)
-\frac 12\delta_3(\log_2N).
$$
The constant $\dfrac{\pi^2}{12L}= 1.1865691$ describes how much is
saved by stopping earlier.
\endproclaim

\demo {Proof}
It turns out that
$$
\hat d_N=\frac 1{1-2^{-N}}\left(-B_N-\frac 12NB_{N-1}\right).
$$
Therefore
$$
d_N=1-\sum_{k=1}^{N-1}\binom Nk\frac{B_k}{2^k-1}
-\frac N2\sum_{k=0}^{N-2}\binom {N-1}k\frac{B_k}{2^{k+1}-1}.
$$
So the result follows from the Theorems 6 and 7.
\enddemo

\proclaim{Theorem 18}
$$
\aligned
l_N&\sim 2\log_2N-\log_2\pi+\frac{\gamma}L+2-\frac{\pi^2}{16L}\\
&+2\delta_1(\log_2n)-\delta_2(\log_2n)-\frac 38\delta_3(\log_2N).
\endaligned
$$
The constant $\dfrac{\pi^2}{16L}$ is $=0.88992683$.
\endproclaim

\demo{Proof}
The old $\hat l_N$ must be changed by the additive term
$\displaystyle{
-\frac 38\frac{NB_{N-1}}{1-2^{-N}}.
}$
Therefore $l_N$ changes by
$$
-\frac 38\sum_{k=1}^{N-1}\binom Nk\frac{kB_{k-1}}{1-2^{-k}},
$$
which is covered by Theorem 16.
\enddemo

\proclaim{Theorem 19} 
$$
c_N\sim2N -\frac{\pi^2}{6L}-\delta_3(\log_2N).
$$
\endproclaim

\demo{Proof}
The extra term is again covered by the formula in Theorem 16.
\enddemo

\proclaim {Remark} {\rm
There is a slightly more general formula involving the 
Ber\-noulli numbers
(with an identical proof):}
\endproclaim

\proclaim {Theorem 20} 
Let $a>0$ be an arbitrary real number. Then
$$
\aligned
n^a \sum_{k=0}^{n-1}\binom nk \frac {B_k}{2^{k+a}-1}
&\sim \frac 1L\zeta(1+a)\Gamma(1+a)\\
&+\frac 1L\sum_{k\ne 0}\zeta(a-\chi_k)\Gamma(a-\chi_k)e^{2k\pi ix}.
\endaligned
$$
\endproclaim


\heading
7. Compression of the tree (``Patricia'')
\endheading

If we don't create a new node in the case that all party members have
thrown the same side of the coin, we construct a {\it compressed 
(incomplete) trie}. In Computer Science it is called a {\it Patricia trie}
\cite 4.

We just mention by how much the averages from the Sections 3--5 are
lowered in this way. (Only the main term is mentioned, and also none
of the (small) fluctuations.) The computations are totally similar to the
earlier ones.
$$
\aligned
\text{size}\ \ l_N&: \quad \log_2\pi-\frac{\gamma}L=0.81874995\\
\text{depth}\ \ d_N&: \quad \log_2\pi-\frac{\gamma}L=0.81874995\\
\text{flippings}\ \ c_N&: \quad \frac N2
\endaligned
$$


\heading
8. Further research
\endheading

The computation of the variances in all instances; this seems to be 
difficult.

Selection of $b$ losers: Recursively, the 0-party ($k$ members) is looking
for the $b$ losers. However, if $k<b$, $k$ losers are already found, so
the 1-party must select the remaining $b-k$ losers! There are a lot of
every day situations were this principle might apply. The reader is invited
to formulate some stimulating examples.

A reasonable variation is that not automatically the 0-party is looking
(recursively) for the loser, but always the party with {\it smaller
cardinality} (with some convention if they have the same number of 
elements).

We hope to report on these and other problems in the near future.


\Refs

\ref \no 1\by P.Flajolet and R.Sedgewick\paper Digital Search Trees
Revisited \jour SIAM J. Computing \vol 15 \yr 1986 \pages 748--767
\endref

\ref \no 2\by P. Flajolet and J.S. Vitter \paper Average--Case Analysis
of Algorithms and Data Structures  \inbook  Handbook of 
Theoretical Computer Science (Algorithms and Complexity)
 \publ North-Holland \yr 1990
\endref

\ref \no 3 \by D.E. Knuth \book The Art of Computer Science Vol.1\publ
Addison--Wesley \yr 1968 \publaddr Reading, MA \endref

\ref \no 4 \by D.E. Knuth \book The Art of Computer Science Vol.3\publ
Addison--Wesley \yr 1973 \publaddr Reading, MA \endref

\ref \no 5\by P. Mathys and P. Flajolet \paper Q--ary Collision Resolution
Algorithms in Random--Access Systems with Free or Blocked Channel Access
\jour IEEE Transactions on Information Theory \vol 31 
\yr 1985 \pages 217--243 \endref


\ref \no 6\by W. Szpankowski \paper Solution of a Linear Recurrence Equation
Arising in the 
Analysis of Some Algorithms \yr 1987 \pages 233--250 \vol 8
\jour SIAM Alg. Disc. Meth. \endref

\ref \no 7\by W. Szpankowski \paper 
The Evaluation of an Alternative Sum with Applications to the Analysis
of Some Data Structures
\yr 1988 \pages 13--19
\jour Information Processing Letters \vol 28 \endref

\endRefs

\enddocument

