AN ASYMPTOTIC STUDY OF A RECURSION OCCURRING IN THE ANALYSIS OF AN ALGORITHM ON BROADCAST COMMUNICATION

PETER J. GRABNER AND HELMUT PRODINGER

Abstract In [7] it was proved that a certain quantity T_{n} occurring in the analysis of an algorithm on broadcast communication satisfies 4 ≪ \frac{T_{n}}{log n} ≪ 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} → \frac{π^{2}}{3 log 2} = 4.74627644 . . ..

In [7] 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 [5], by (recursive) coin flippings. This person’s number will be the next current maximum (initially the maximum was set to −∞), 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 [7] come up with the recursion

(1 − \frac{1}{2^{n−1}} ) T_{n} = 1 + \frac{1}{2^{n}} [1 + ∑_{k=1}^{n−1} \binom{n}{k}T_{k} + ∑_{k=0}^{n−1} 2^{n−1−k}T_{k}] ,

(n ≥ 2; 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 [4] and [6].

By elementary methods it was shown in [7] that T_{n} = Θ(log n). In this note it will be shown that we can achieve much better results, since we will prove that

Theorem 1. (i) An explicit formula for T_{n} is given by

T_{n} = 1 + ∑_{k=0}^{n−1} \frac{2B_{k}}{1 − 2^{−k−1}} [\binom{n}{k + 1} − 1] ,

where B_{n} is the n–th Bernoulli number.

(ii) For n → ∞ we have

T_{n} = \frac{π^{2}}{3 log 2} log n + K + δ(log_{2} n) + O(\frac{1}{n}).

Date: November 6, 1997.

Key words and phrases. Broadcast communication, Recursion, Bernoulli numbers, Rice’s method, Mellin– Perron formula.

The constant K is given by

K = \frac{γπ^{2}}{3 log 2} + 1 − \frac{π^{2}}{3 log 2} − \frac{2ζ′(2)}{log 2} + \frac{π^{2}}{6} − 2 ∑_{n=1}^{∞} \frac{⌈log_{2} n⌉}{n^{2}} = .34118435603469732225 …

and δ(x) is a periodic function with period 1, mean 0, |δ(x)| ≤ 0.852 · 10^{−5}, and the Fourier expansion

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

Observe that \frac{π^{2}}{3 log 2} = 4.74627644 …, which “explains” the elementary bounds 4 ≪ \frac{T_{n}}{log n} ≪ 5 from [7].

By elementary rearrangements we write the recursion as

(1 − \frac{1}{2^{n−1}} ) T_{n} + \frac{1}{2^{n}} T_{n} + \frac{1}{2^{n+1}} T_{n} = 1 + \frac{1}{2^{n}} [∑_{k=0}^{n} \binom{n}{k}T_{k} + ∑_{k=0}^{n} 2^{n−1−k}T_{k}] ;

taking the difference between this equation and the one where n is substituted by n − 1 we find

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

It is natural to introduce the auxiliary quantities U_{k} = T_{k+1} − T_{k} and replace n by n + 1 to find

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

It holds for n ≥ 2 and U_{0} = 0, U_{1} = 4. Now such recursions are fairly well understood, see e.g. [6]: One introduces the exponential generating function

U(z) = ∑_{n≥0} U_{n} \frac{z^{n}}{n!}

and translates the recursion into the functional equation

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

This equation can be solved using an old trick of Knuth’s, [4, pp. 502, 686 (Ex. 6.3.33)], that was used to analyze a variant of digital search trees called Patricia trees: We define

Û(z) = \frac{U(z)}{e^{z} − 1}  (1)

and get the simpler equation

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

Inserting

Û(z) = ∑_{n≥0} Û_{n} \frac{z^{n}}{n!} ,

into (1) yields

∑_{n≥0} \frac{z^{n}}{n!} Û_{n} (1 − \frac{1}{2^{n+1}} ) = 2 ∑_{n≥0} \frac{z^{n}}{n!} B_{n},

where B_{n} denotes the n-th Bernoulli number. Comparing coefficients we deduce

Û_{n}(1 − \frac{1}{2^{n+1}} ) = 2B_{n} or Û_{n} = \frac{2B_{n}}{1 − \frac{1}{2^{n+1}}} .

Thus we have

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

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, [4, p. 499 and Ex. 6.3.34]. In [5], related quantities appear in the context of the election of a loser.

Now we turn to asymptotics. Following the method described in [3] (see also [8, 5]) we can write U_{n} as a complex contour integral;

U_{n} = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{Γ(n + 1) Γ(1 − s)}{Γ(n + 1 − s)} \frac{2ζ(1 − s)}{1 − 2^{−s−1}} ds .  (2)

Since

T_{n} = 1 + U_{0} + U_{1} + ∑_{m=2}^{n−1} U_{m} ,

we find

T_{n} = 5 − \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{4ζ(1 − s)}{(1 − s)(s + 1)(1 − 2^{−s−1})}ds  (3)
+ \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{Γ(n + 1) Γ(1 − s)}{Γ(n − s)} \frac{2ζ(1 − s)}{(s + 1)(1 − 2^{−s−1})}ds .  (4)

Observe that the first two terms were taken out in order to make the first integral convergent. We can compute (3) as follows,

\frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{4ζ(1 − s)}{(1 − s)(s + 1)(1 − 2^{−s−1})}ds = \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞} \frac{4ζ(s)}{s(2 − s)(1 − 2^{s−2})}ds  (5)
= ∑_{k≥0} ∑_{n≥1} 4^{1−k} \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞} \frac{1}{s(2 − s)} (\frac{2^{k}}{n} )^{s} ds .  (6)

Here, we first used the substitution s := 1 − s and then the the geometric series and the expansion of ζ(s), both valid for ℜ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 [9, 2]) evaluates the integrals inside the summation:

\frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞} \frac{1}{s(2 − s)}t^{s}ds = \begin{cases}\frac{1}{2} & for t ≥ 1 \\ \frac{t^{2}}{2} & for t < 1 \end{cases} .

Now the series according to the first alternative is

∑_{k≥0} 4^{1−k} ∑_{n=1}^{2^{k}} \frac{1}{2} = 2 ∑_{k≥0} 4^{−k}2^{k} = 2 ∑_{k≥0} 2^{−k} = 4

and the other one is

2 ∑_{k≥0} ∑_{n>2^{k}} \frac{1}{n^{2}} = 2 ∑_{k=0}^{∞}(k + 1) ∑_{n=2^{k}+1}^{2^{k+1}} \frac{1}{n^{2}} = 3.0022908154228746627 ….  (7)

Notice that in the range of n we have k+1 = ⌈log_{2} n⌉, which gives the series in the statement of the theorem. For numerical purposes the expression in (7) is preferred, since Maple computes the partial sums ∑_{a≤n≤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 (5) would be to move the line of integration to the right. Here residues at the points 2 + \frac{2kπi}{log 2} would have to be collected, which would form a slowly convergent sum. This sum corresponds to (7) by replacing ⌈log_{2} n⌉ with log_{2} n + 1 + {log_{2} n} 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 (7) could be computed easily numerically, we preferred this form of the sum.

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 [3]). A similar computation as the one used before to derive the series expansion for the first integral shows that

\frac{1}{2πi} ∫_{− \frac{3}{2} −i∞}^{− \frac{3}{2} +i∞} \frac{Γ(n + 1) Γ(1 − s)}{Γ(n − s)} \frac{2ζ(1 − s)}{(s + 1)(1 − 2^{−s−1})}ds = 0.

At s = −1, we find the residue

\frac{π^{2}H_{n}}{3 log 2} − \frac{π^{2}}{3 log 2} − \frac{2ζ′(2)}{log 2} + \frac{π^{2}}{6} ,

with a harmonic number H_{n} = ∑_{1≤k≤n} \frac{1}{k} = log n + γ + O(\frac{1}{n}). At s = −1 + χ_{k} with χ_{k} = \frac{2kπi}{log 2} (for k ∈ ℤ, k ≠ 0) we find the residue

\frac{Γ(n + 1) Γ(2 − χ_{k})}{Γ(n + 1 − χ_{k})} \frac{2ζ(2 − χ_{k})}{χ_{k} log 2} ;

collecting them gives the explicit formula

T_{n} = \frac{π^{2}}{3 log 2}H_{n} + (K − \frac{γπ^{2}}{3 log 2}) + ∑_{k∈ℤ\\{0\}} \frac{Γ(n + 1) Γ(2 − χ_{k})}{Γ(n + 1 − χ_{k})} \frac{2ζ(2 − χ_{k})}{χ_{k} log 2} .

The periodic function mentioned in the theorem can be computed from the asymptotic expansion of the quotients of Γ-functions (compare [1])

\frac{Γ(n + 1)}{Γ(n + 1 − χ_{k})} = n^{χ_{k}}(1 + O(\frac{k^{2}}{n} )) .

Combining known estimates for the Γ- and ζ-function (cf. [1]) yields

\frac{2Γ(2 − χ_{k}) ζ(2 − χ_{k})}{χ_{k} log 2} ≤ 13|k|^{\frac{1}{2}} e^{− \frac{π^{2}}{log 2} |k|} for |k| ≥ 1

which (by uniform convergence) justifies interchanging summation and asymptotics. Furthermore, this yields the estimate for δ(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.

References

[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1973. A reprint of the tenth National Bureau of Standards edition, 1964.

[2] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R.F. Tichy. Mellin transforms and asymptotics: Digital sums. Theor. Comput. Sci., 123:291–314, 1994.

[3] P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: Finite differences and Rice’s integrals. Theor. Comput. Sci., 144:101–124, 1995.

[4] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973.

[5] H. Prodinger. How to select a loser. Discrete Math., 120:149–159, 1993.

[6] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

[7] S.-H. Shiau and C.-B. Yang. A fast maximum finding algorithm on broadcast communication. Inf. Process. Lett., 60:81–89, 1996.

[8] W. Szpankowski. The evaluation of an alternating sum with applications to the analysis of algorithms. Inf. Process. Lett., 28:13–19, 1988.

[9] G. Tenenbaum. Introduction to analytic and probabilistic number theory. Cambridge University Press, 1995.

Institut für Mathematik. Technical University of Graz. Steyrergasse 30, A-8010 Graz, Austria.

Institut für Algebra und Diskrete Mathematik. Technical University of Vienna. Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

  E-mail address: grabner@weyl.math.tu-graz.ac.at, Helmut.Prodinger@tuwien.ac.at