HOW TO SELECT A LOSER

Helmut Prodinger

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

Abstract. N people select a 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_{2} N steps. Nevertheless, this very plausible result requires rather advanced methods.

1. Introduction

Assume that a party of N people wants to select one of their members (the 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{1}{2}); 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.

Fig.1

What is produced by the above mentioned mechanism might be called an incomplete trie. In this figure a left branch is labelled by a 0 and a right branch by a 1.

Typeset by AMS-TEX

For tries and related data structures we refer to [4]. The idea of splitting the party by flipping a coin was also used in the tree protocol of Capetanakis and Tsybakhov (see [5] for a survey).

In the following we analyze the 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 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.

2. Preliminaries

Here we list some notational conveniences, as well as some basic properties of the Bernoulli numbers, since they are needed in the sequel (compare e.g. [3]).

We write [z^{n}]f(z) for the coefficient of z^{n} in the series f(z). Quite naturally we have

[\frac{z^{n}}{n!} ] f(z) = n! [z^{n}] f(z).

Abbreviations:

L = log 2  and  χ_{k} = \frac{2kπi}{L}, k ∈ ℤ.

ζ(s) denotes Riemann’s ζ–function; Γ(s) the Γ–function; γ is Euler’s constant; γ = 0.57721.

The Bernoulli numbers B_{n} are defined by

B_{n} = [\frac{z^{n}}{n!} ] \frac{z}{e^{z} − 1}.

Similarly, the Bernoulli polynomial B_{n}(t) is defined by

\frac{ze^{tz}}{e^{z} − 1} = ∑_{k≥0} B_{k}(t)\frac{z^{k}}{k!} .

Properties:

B_{n}(0) = B_{n}(1) = B_{n} for n ≥ 2; B_{0} = 1, B_{1} = −\frac{1}{2},

B_{n}(x) = ∑_{k=0}^{n} \binom{n}{k}B_{k}x^{n−k}

and thus

B_{n} = ∑_{k=0}^{n} \binom{n}{k}B_{k} and B_{n}(\frac{1}{2}) = −(1 − 2^{1−n})B_{n}.

Also, we may express the Bernoulli numbers by the ζ–function:

B_{k} = −kζ(1 − k) for k ≥ 2.

3. The average size

The style of the following analysis follows [4]; we mention also [6].

Proposition 1. The probability generating function F_{N}(z) fulfills the following recursion:

\begin{matrix}F_{N}(z) & = z^{2} ∑_{k=0}^{N} 2^{−N} \binom{N}{k}F_{k}(z) + z(1 − z)2^{−N}F_{N}(z) \\ − & z^{2}2^{−N} + z2^{−N}F_{N}(z) for N ≥ 2; F_{0}(z) = 1, F_{1}(z) = z. \end{matrix}

Proof. 2^{−N} \binom{N}{k} 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.

Let l_{N} = F′_{N}(1) denote the average size. The following recursion follows immediately from Proposition 1 by differentiation:

Proposition 2. We have l_{0} = 0, l_{1} = 1 and for N ≥ 2

l_{N} = 2 + \frac{1}{1 − 2^{−N}} ∑_{k=0}^{N} 2^{−N} \binom{N}{k}l_{k}.

Now we introduce the exponential generating function L(z) = ∑_{k≥0} l_{k} \frac{z^{k}}{k!} . Then the

recursion for the l_{n}’s turns into a functional equation for L(z).

Proposition 3.

L(z) − L(\frac{z}{2}) = 2e^{z} − 2e^{z/2} − z + e^{z/2}L(\frac{z}{2}).

The equation becomes easier by introducing

L̂(z) = \frac{L(z)}{e^{z} − 1} = ∑_{k≥0} l̂_{k} \frac{z^{k}}{k!} .

4 HELMUT PRODINGER

Proposition 4.

L̂(z) = L̂(\frac{z}{2}) + \frac{2e^{z} − 2e^{z/2} − z}{e^{z} − 1} .

Proposition 5. l̂_{0} = 1 and for N ≥ 1 we have

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}} .

Proof. From Proposition 4 we find that for N ≥ 1

l̂_{N}(1 − 2^{−N}) = [\frac{z^{N}}{N!} ] \frac{2e^{z} − 2e^{z/2} − z}{e^{z} − 1}

= \frac{2}{N + 1} [\frac{z^{N+1}}{(N + 1)!}] \frac{ze^{z}}{e^{z} − 1}

− \frac{2}{N + 1} [\frac{z^{N+1}}{(N + 1)!}] \frac{ze^{z/2}}{e^{z} − 1} − B_{N}

= \frac{2}{N + 1}B_{N+1}(1) − \frac{2}{N + 1}B_{N+1}(\frac{1}{2}) − B_{N}.

The final formula follows from the properties of the Bernoulli numbers. Now, since L(z) = (e^{z} − 1)L̂(z), we find

l_{N} = ∑_{k=0}^{N−1} \binom{N}{k}l̂_{k}

= 1 + ∑_{k=1}^{N−1} \binom{N}{k}\frac{1}{1 − 2^{−k}} \frac{2}{k + 1}B_{k+1}

+ ∑_{k=1}^{N−1} \binom{N}{k}\frac{2}{k + 1}B_{k+1} − ∑_{k=1}^{N−1} \binom{N}{k}\frac{B_{k}}{1 − 2^{−k}}

= 1 + S_{1} + S_{2} + S_{3}.

The sum S_{2} is the easiest:

S_{2} = \frac{2}{N + 1} ∑_{k=1}^{N−1} \binom{N + 1}{k + 1}B_{k+1}

= \frac{2}{N + 1} [ ∑_{k=0}^{N+1} \binom{N + 1}{k}B_{k} − B_{N+1} − (N + 1)B_{1} − B_{0}]

= 1 − \frac{2}{N + 1} ∼ 1.

Next we turn to S_{1}:

\begin{aligned}S_{1} & = ∑_{k=1}^{N−1} \binom{N}{k}\frac{2}{k + 1}B_{k+1} (1 + \frac{1}{2^{k} − 1}) \\ & = S_{2} + \frac{2}{N + 1} ∑_{k=2}^{N} \binom{N + 1}{k}\frac{B_{k}}{2^{k−1} − 1}. \end{aligned}

The remaining sum was studied in Knuth [4, p.503]:

Theorem 6. [Knuth]

S := \frac{1}{n} ∑_{k=2}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k−1} − 1} ∼ \frac{1}{2} log_{2} n − \frac{1}{2} log_{2} π + \frac{γ}{2L} − \frac{3}{4} + δ_{1}(log_{2} n),

with the periodic function (of period 1 and very small amplitude)

δ_{1}(x) = \frac{1}{L} ∑_{k≠0} ζ(−χ_{k})Γ(−χ_{k})e^{2kπix}. □

With this result we can formulate an asymptotic equivalent for the sum S_{1}:

S_{1} ∼ log_{2} N − log_{2} π + \frac{γ}{L} − \frac{1}{2} + 2δ(log_{2} N).

Now we turn to the computation of the last sum, S_{3}:

S_{3} = − ∑_{k=1}^{N−1} \binom{N}{k}B_{k} [1 + \frac{1}{2^{k} − 1}] .

According to this decomposition we find that the first sum equals 1 and analyze the second one:

Theorem 7.

S := ∑_{k=1}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k} − 1} ∼ − log_{2} n + \frac{1}{2} + δ_{2}(log_{2} n),

with the periodic function (of period 1 and very small amplitude)

δ_{2}(x) = \frac{1}{L} ∑_{k≠0} ζ(1 − χ_{k})Γ(1 − χ_{k})e^{2kπix}.

Proof. Instead of following Knuth’s approach (cf.Theorem 6) (Mellin transforms) we use “Rice’s method” (see [1] for a good introduction). An equivalent methodology was given by W. Szpankowski in [7]. From this, we can express the sum S as a contour integral

S = \frac{1}{2πi} ∫_{\frac{1}{2} −i∞}^{\frac{1}{2} +i∞}\frac{(−1)^{n}n!}{(z − 1)(z − 2) … (z − n)} · \frac{ζ(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 = χ_{k}, k ∈ ℤ, k ≠ 0.

The local expansions for z → 0 are

\begin{aligned}\frac{(−1)^{n}n!}{(z − 1)(z − 2) … (z − n)} & ∼ 1 + zH_{n} \\ ζ(1 − z) & ∼ −\frac{1}{z} (1 − γz) \\ \frac{1}{2^{z} − 1} & ∼ \frac{1}{Lz} (1 − \frac{Lz}{2} ) \end{aligned}

with H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n} ∼ log n + γ being the n–th harmonic number. The residue at z = 0 is therefore

[z^{−1}] − \frac{1}{Lz^{2}} (1 + zH_{n}) (1 − γz) (1 − \frac{Lz}{2} )

= −\frac{1}{L} (H_{n} − γ − \frac{L}{2})

∼ − log_{2} n + \frac{1}{2}.

The residue at z = χ_{k} is \frac{1}{L}Γ(1 − χ_{k})ζ(1 − χ_{k}). This may be seen by expressing

\frac{(−1)^{n}n!}{(z − 1)(z − 2) … (z − n)} as \frac{Γ(n + 1)Γ(1 − z)}{Γ(n + 1 − z)}.

So the function δ_{2}(x) is obtained, since n^{χ_{k}} = e^{2kπi·log_{2} n}.

Therefore we find that the sum S_{3} can be approximated by

S_{3} ∼ log_{2} n + \frac{1}{2} − δ_{2} (log_{2} N) .

Now we get our main result by collecting 1 + S_{1} + S_{2} + S_{3}:

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} ∼ 2 log_{2} N − log_{2} π + \frac{γ}{L} + 2 + 2δ_{1}(log_{2} N) − δ_{2}(log_{2} N).

The constant − log_{2} π + \frac{γ}{L} + 2 is = 1.181250048.

4. The average depth

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 [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:

Proposition 9. The probability generating function G_{N}(z) fulfills for N ≥ 2 (G_{0}(z) = G_{1}(z) = 1):

G_{N}(z) = z ∑_{k=0}^{N} 2^{−N} \binom{N}{k}G_{k}(z) − z2^{−N} + z2^{−N}G_{N}(z).

Set d_{N} = G′_{N}(1).

Proposition 10. We have d_{0} = d_{1} = 0 and for N ≥ 2:

d_{N} (1 − 2^{−N}) = 1 + ∑_{k=0}^{N} 2^{−N} \binom{N}{k}d_{k}.

Set

D(z) = ∑_{k≥0} d_{k} \frac{z^{k}}{k!} and D̂(z) = \frac{D(z)}{e^{z} − 1} = ∑_{k≥0} d̂_{k} \frac{z^{k}}{k!} .

Proposition 11.

D(z) − D (\frac{z}{2}) = e^{z} − 1 − z + e^{z/2}D (\frac{z}{2})

Proposition 12.

D̂(z) = D̂ (\frac{z}{2}) + 1 − \frac{z}{e^{z} − 1}.

Proposition 13. d̂_{0} = 1 and for N ≥ 1 we have

d̂_{N} = −\frac{B_{N}}{1 − 2^{−N}} .

Therefore we find that d_{N} equals S_{3} from Section 1 and we have:

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} ∼ log_{2} N + \frac{1}{2} − δ_{2}(log_{2} N).

5. The average number of coin flippings

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:

Theorem 15. The average total number c_{N} of coin flippings performed by N people who are selecting a loser is

c_{N} = 2N for N ≥ 2, c_{0} = c_{1} = 0.

Proof. We use some obvious notations in the style of the preceeding sections.

\begin{matrix}F_{N}(z) = z^{N} ∑_{k=0}^{N} 2^{−N} \binom{N}{k}F_{k}(z) & − z^{N}2^{−N} + z^{N}2^{−N}F_{N}(z) \\ for N ≥ 2, F_{0}(z) = F_{1}(z) = 1. \end{matrix}

c_{N} (1 − 2^{−N}) = N + ∑_{k=0}^{N} 2^{−N} \binom{N}{k}c_{k} for N ≥ 2, c_{0} = c_{1} = 0.

C(z) − C(\frac{z}{2}) = z (e^{z} − 1) + e^{z/2}C(\frac{z}{2}).

Ĉ(z) = z + Ĉ(\frac{z}{2}).

ĉ_{N} (1 − 2^{−N}) = 0 for N ≠ 1, ĉ_{1} = 2.

c_{N} = ∑_{k=0}^{N−1} \binom{N}{k}ĉ_{k} = 2N.

6. A draw is possible

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:

Theorem 16.

S := n ∑_{k=0}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k+1} − 1} ∼ \frac{π^{2}}{6L} + δ_{3}(log_{2} n),

with the periodic function (of period 1 and very small amplitude)

δ_{3}(x) = \frac{1}{L} ∑_{k≠0} ζ(2 − χ_{k})Γ(2 − χ_{k})e^{2kπix}.

Proof. As in the proof of Theorem 7, we express S as a contour integral:

S = n · \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}\frac{(−1)^{n}n!}{(z − 1)(z − 2) … (z − n)} · \frac{ζ(1 − z)}{2^{z+1} − 1}dz.

The residues at z = −1 and z = −1 + χ_{k}, k ≠ 0, give the asymptotic formula

(observe that ζ(2) = \frac{π^{2}}{6} ).

HOW TO SELECT A LOSER 9

Theorem 17.

d_{N} ∼ log_{2} N + \frac{1}{2} − \frac{π^{2}}{12L} − δ_{2}(log_{2} N) − \frac{1}{2}δ_{3}(log_{2} N).

The constant \frac{π^{2}}{12L} = 1.1865691 describes how much is saved by stopping earlier. Proof. It turns out that

d̂_{N} = \frac{1}{1 − 2^{−N}} (−B_{N} − \frac{1}{2}NB_{N−1}) .

Therefore

d_{N} = 1 − ∑_{k=1}^{N−1} \binom{N}{k}\frac{B_{k}}{2^{k} − 1} − \frac{N}{2} ∑_{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. Theorem 18.

l_{N} ∼ 2 log_{2} N − log_{2} π + \frac{γ}{L} + 2 − \frac{π^{2}}{16L}

+ 2δ_{1}(log_{2} n) − δ_{2}(log_{2} n) − \frac{3}{8}δ_{3}(log_{2} N).

The constant \frac{π^{2}}{16L} is = 0.88992683.

Proof. The old l̂_{N} must be changed by the additive term −\frac{3}{8} \frac{NB_{N−1}}{1 − 2^{−N}} . Therefore l_{N} changes by

−\frac{3}{8} ∑_{k=1}^{N−1} \binom{N}{k}\frac{kB_{k−1}}{1 − 2^{−k}} ,

which is covered by Theorem 16. Theorem 19.

c_{N} ∼ 2N − \frac{π^{2}}{6L} − δ_{3}(log_{2} N).

Proof. The extra term is again covered by the formula in Theorem 16. Remark. There is a slightly more general formula involving the Bernoulli numbers (with an identical proof): Theorem 20. Let a > 0 be an arbitrary real number. Then

\begin{aligned}n^{a} ∑_{k=0}^{n−1} \binom{n}{k}\frac{B_{k}}{2^{k+a} − 1} & ∼ \frac{1}{L}ζ(1 + a)Γ(1 + a) \\ & + \frac{1}{L} ∑_{k≠0} ζ(a − χ_{k})Γ(a − χ_{k})e^{2kπix}. \end{aligned}

7. Compression of the tree (“Patricia”)

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 compressed (incomplete) trie. In Computer Science it is called a Patricia trie [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.

size l_{N} : log_{2} π − \frac{γ}{L} = 0.81874995
depth d_{N} : log_{2} π − \frac{γ}{L} = 0.81874995
flippings c_{N} : \frac{N}{2}

8. Further research

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 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.

References

1. P.Flajolet and R.Sedgewick, Digital Search Trees Revisited, SIAM J. Computing 15 (1986), 748–767.

2. P. Flajolet and J.S. Vitter, Average–Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science (Algorithms and Complexity), North-Holland, 1990.

3. D.E. Knuth, The Art of Computer Science Vol.1, Addison–Wesley, Reading, MA, 1968.

4. D.E. Knuth, The Art of Computer Science Vol.3, Addison–Wesley, Reading, MA, 1973.

5. P. Mathys and P. Flajolet, Q–ary Collision Resolution Algorithms in Random–Access Systems with Free or Blocked Channel Access, IEEE Transactions on Information Theory 31 (1985), 217–243.

6. W. Szpankowski, Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms, SIAM Alg. Disc. Meth. 8 (1987), 233–250.

7. W. Szpankowski, The Evaluation of an Alternative Sum with Applications to the Analysis of Some Data Structures, Information Processing Letters 28 (1988), 13–19.

Technical University of Vienna Wiedner Hauptstraße 8-10

HOW TO SELECT A LOSER 11

A-1040 Vienna AUSTRIA