ANALYSIS OF AN ASYMMETRIC LEADER ELECTION ALGORITHM

Svante Janson  Wojciech Szpankowski^{∗}
Department of Mathematics  Department of Computer Science
Uppsala University  Purdue University
75106 Uppsala  W. Lafayette, IN 47907
Sweden  U.S.A.

 svante.janson@math.uu.se               spa@cs.purdue.edu

Submitted April 29, 1997; Accepted July 14, 1997.

Abstract

We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at every stage of the algorithm those objects that survived so far flip a biased coin, and those who received, say a tail, survive for the next round. The process continues until only one objects remains. Our interest is in evaluating the limiting distribution and the first two moments of the number of rounds needed to select a leader. We establish precise asymptotics for the first two moments, and show that the asymptotic expression for the duration of the algorithm exhibits some periodic fluctuations and consequently no limiting distribution exists. These results are proved by analytical techniques of the precise analysis of algorithms such as: analytical poissonization and depoissonization, Mellin transform, and complex analysis.

1 Introduction

Consider a group of n people (users, computers, objects, etc.) sharing a scarce resource (e.g., channel, CPU, etc.). The following elimination process can be used to find a “winner” or a “leader” that has undisputed and uncontested access to the resource (cf. [2, 5, 19]): All objects involved toss a biased coin, and all players to throw heads are losers while those who throw tails remain candidate winners and flip the coins again until a single winner (leader) is identified. If all players throw heads at any stage, the toss is inconclusive and all players participate again in the contest. How many tosses are needed to identify a winner? The problem was posed for a fair (unbiased) coin tossing process by Prodinger [19] (cf. also [10]), who provided the first non-trivial analysis. Recently, for the same fair coin model, Fill et. al. [5] find the limiting distribution for the number of rounds. In this paper, we analyze the same problem but when the coins involved are biased, that is, the probability p of throwing a head is not equal to one half (p ≠ \frac{1}{2}). In passing, we should mention that such a randomized elimination algorithm has some applications, notably in electing a “leading” computer after a synchronization is lost in a distributed computer network (e.g., token lost in a token passing ring network). We also remark that a formula for the exact distribution has been given by Fill et. al. [5] for the fair model and by Fill [6] for the biased case.

∗The work of this author was supported by NSF Grants NCR-9206315 and NCR-9415491, and NATO Collaborative Grant CRG.950060. The second author also thanks INRIA, Sophia Antipolis, project MISTRAL for hospitality and support during the summer of 1996 when this paper was completed.

The above elimination process can be represented as a incomplete trie (cf. [5, 18, 19]) in which only one side of the trie is developed while the other side is pruned (all those players who throw heads do not participate any more in the process). Therefore, the number of throws needed to find the winner (leader) is equivalent to the height in such a incomplete trie. Accordingly, we shall call the duration of the above elimination process as height, and we study asymptotics of its moments and the limiting distribution, if it exists.

Tries have been extensively analyzed in the past including the height. The reader is referred to Knuth [16] and Mahmoud [18] for updated account on recent developments in this area. In fact, tries and other digital trees were used as a testbed for the “precise analytical analysis of algorithms”. Several new analytical techniques were developed in the process of analyzing different parameters of digital trees (cf. [4, 5, 10, 13, 14, 16, 20, 21, 22]). Recently, the focus of the research was moved towards developing analytical techniques that can handle limiting distributions and large deviations results (cf. [5, 11, 12, 14, 15]).

In this paper, we continue recent lines of research and establish asymptotic distribution together with the first two moments of the height. The novelty of this work lies in deriving an asymptotic solution to a certain functional equation that often arises in the analysis of algorithms and data structures (cf. [4, 21]). Namely, we consider functional equations of the following type:

f(z) = f(pz) + f(qz)e^{−pz} + a(z)  (1)

where p + q = 1 and a(z) is a given function. The point to observe is that there is a coefficient depending on z in front of f(qz) which makes the problem interesting (otherwise a standard approach can be applied; cf. [7]). While a first-order asymptotic for such an equation, when z → ∞ in a cone around the positive axis, is rather easy to obtain, second-order asymptotics are more challenging. This demands an evaluation of some constants for which a closed-form solution does not exist. We provide a quickly converging numerical procedure to assess these constants. We must mention that functional equations of type (1) could be alternatively treated by the method proposed in [4] (cf. [21]), however, it seems to us that our method is more straightforward. In addition, in [4] the problem of evaluating the constants was not discussed.

When dealing with the limiting distribution, we use a two steps approach recently advocated in some papers (notably: [5, 11, 12, 14]): That is, we first poissonize the problem and then depoissonize it. By poissonization we mean to replace the fixed size population model (i.e., fixed n) by a model in which the number of persons involved is Poisson distributed with mean n. Such a model leads to a functional equation of type (1): More precisely, for all integers k ≥ 0

f_{k+1}(z) = f_{k}(pz) + e^{−pz}f_{k}(qz) .

This equation is solved inside a cone, and then depoissonized in order to obtain an asymptotic distribution of the original fixed size model. Actually, during the course of establishing the limiting distribution we realize that its asymptotic expression exhibits some fluctuations leading us to a conclusion that the height does not possess a limiting distribution. This was already observed for the height of tries (cf. [3]) and symmetric (unbiased coin tossing) incomplete tries (cf. [5]).

The paper is organized as follows. The next section presents our main results: In Theorem 1 we discuss asymptotics of the mean and the variance of the height. The next Theorem 2 provides an asymptotic expression for the distribution of the height. We close this section with a brief discussion of main consequences of our results. Section 3 contains the proofs of both Theorem 1 and Theorem 2. Since, as we already mentioned above, we work on the Poisson model instead of the original model, we need a tool of depoissonization. For the completeness of our presentation, we briefly discuss a depoissonization lemma of Jacquet and Szpankowski [15] in Section 3.1. Then, Theorem 1 is proved in Section 3.2, and Theorem 2 in Section 3.3.

2 Main Results

In this section, we present our main results. To recall, n people use the randomized elimination algorithm described above to identify a leader. Let p be the probability of of survival, and q = 1 − p. By H_{n} we denote the number of tosses needed to identify the winner.

As mentioned before, the elimination process can be represented as an incomplete trie. Having this in mind, one can easily derive the basic recurrence equation for the generating function of H_{n}. Indeed, let for n ≥ 1, G_{n}(u) = Eu^{H_{n}} = ∑_{k≥0} P(H_{n} = k)z^{k} be the probability generating function of H_{n}, where u is a complex number. We further let G_{0}(u) = 0 for convenience. (This corresponds to defining H_{0} = ∞; as pointed out by Jim Fill [6], this convention is reasonable since we never succeed to choose a leader without any candidates.)

Then, G_{1}(u) = 1 and for n ≥ 2

G_{n}(u) = u ∑_{k=0}^{n} \binom{n}{k}p^{k}q^{n−k}G_{k}(u) + uq^{n}G_{n}(u) .  (2)

The first term of the above is a consequence of the Bernoulli-like split (after the first round) of n players into those who still stay in the game. Clearly, the remaining players have H_{n} − 1 tosses to finish the game. The second term of the above, takes care of the inconclusive throw (when all players throw heads).

In this paper, we derive the distribution of H_{n} as well as the first two moments, that is, EH_{n} and Var H_{n}. We use the following abbreviated notation: x_{n} = EH_{n} and w_{n} = EH_{n}(H_{n} − 1). Observing that x_{n} = G′_{n}(1) and w_{n} = G′′_{n}(1), we derive from (2):

x_{n} = 1 + q^{n}x_{n} + ∑_{k=0}^{n} \binom{n}{k}p^{k}q^{n−k}x_{k} ,  n ≥ 2 ,  (3)
w_{n} = 2(x_{n} − 1) + q^{n}w_{n} + ∑_{k=0}^{n} \binom{n}{k}p^{k}q^{n−k}w_{k} ,  n ≥ 2 ,  (4)

with x_{0} = x_{1} = w_{0} = w_{1} = 0.

In the next section, we solve asymptotically the above recurrence equations using poissonization, Mellin transform and depoissonization. This results in our first main finding.

Theorem 1 Let P := 1/p and χ_{k} := 2πik/ ln P. Then:

(i) The mean EH_{n} of the height admits the following asymptotic formula

EH_{n} = log_{P} n + \frac{1}{2} − \frac{1 − γ − T_{1}^{∗}(0)}{ln P} + δ_{1}(log_{P} n) + O(1/n)  (5)

where γ = 0.577 … is the Euler constant, and

T_{1}^{∗}(0) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n} ,  (6)

where x_{n} must be computed from (3) (observe that the series converges geometrically fast). The function δ_{1}(x) is periodic function of small magnitude (e.g., for p = 0.5 one proves |δ_{1}(x)| ≤ 2 × 10^{−5}) given by

δ_{1}(x) = − ∑_{k≠0} α_{k}e^{−2πikx}  (7)

where

α_{k} = \frac{(1 + χ_{k})Γ(χ_{k}) − T_{1}^{∗}(χ_{k})}{ln P} ,

Γ(s) is the Euler gamma function (cf. [1]) and T_{1}^{∗}(s) is given by (37).

Table 1: Numerical evaluation of the constants T_{1}^{∗}(0), T_{1}^{∗′}(0), T_{2}^{∗}(0), and the variance Var H_{n} for various p ∈ [0.2..0.8]

\begin{matrix}p & T_{1}^{∗}(0) & T_{1}^{∗′}(0) & T_{2}^{∗}(0) & Var H_{n} \\ 0.2 & 2.36 & 2.38 & 9.32 & 5.83 \\ 0.3 & 1.22 & 1.09 & 3.41 & 3.58 \\ 0.4 & 0.70 & 0.56 & 1.64 & 2.97 \\ 0.5 & 0.42 & 0.30 & 0.95 & 3.12 \\ 0.6 & 0.25 & 0.17 & 0.62 & 4.07 \\ 0.7 & 0.15 & 0.09 & 0.45 & 6.68 \\ 0.8 & 0.08 & 0.04 & 0.35 & 14.84 \end{matrix}

(ii) The variance Var H_{n} = EH_{n}(H_{n} − 1) + EH_{n} − (EH_{n})^{2} satisfies

Var H_{n} = \frac{π^{2}/6 − 1 + 2(1 − γ)T_{1}^{∗}(0) − 2T_{1}^{∗′}(0) − (T_{1}^{∗}(0))^{2}}{ln^{2} P} + \frac{2T_{1}^{∗}(0) + T_{2}^{∗}(0)}{ln P} + \frac{1}{12}
− [δ_{1}^{2}]_{0} + δ_{2}(log_{P} n) + O (\frac{ln n}{n})  (8)

where

T_{1}^{∗′}(0) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n!} Γ′(n) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n} Ψ(n) ,  (9)

where Ψ(z) = Γ′(z)/Γ(z) is the psi-function. Observe that for natural n we have Ψ(n) = −γ + H_{n−1} where H_{n} is the n-th Harmonic number. The constant T_{2}^{∗}(0) can be computed as

T_{2}^{∗}(0) = ∑_{n=2}^{∞} \frac{w_{n}q^{n}}{n}

where w_{n} is given by the recurrence (4). Finally, δ_{2}(x) is a periodic continuous function of zero mean and small amplitude. The constant [δ_{1}^{2}]_{0} = ∑_{k≠0} |α_{k}|^{2} is the zeroth term of δ_{1}^{2}(x) and its value is extremely small (e.g., for p = 0.5 one proves that [δ_{1}^{2}]_{0} ≤ sup |δ_{1}(x)|^{2} ≤ 4 × 10^{−10}).

In Table 1 we present numerical values of the constants T_{1}^{∗}(0), T_{1}^{∗′}(0), T_{2}^{∗}(0), and the asymptotic equivalence of the variance Var H_{n} given by (8) (for large n) as a function of p. In particular, we verify that our formula (8) on the variance agrees with that of Fill et al. [5] for p = 0.5, where the exact value 1 − γ = 0.422 … is given.

In order to formulate our next result concerning the distribution of H_{n} we need a new definition. Let a measure μ be defined on the positive real axis as follows: Partition the positive real axis into an infinite sequence of consecutive intervals I_{0}, I_{1}, … such that I_{k} has length (q/p)^{s(k)}, where s(k) is the number of 1’s in the binary expansion of k. Thus, I_{0} = [0, 1], I_{1} = [1, 1 + q/p], etc. Note that the total length of the first 2^{m} intervals I_{0}, ..., I_{2^{m}−1} is p^{−m}, and that these 2^{m} intervals are obtained by repeated subdivisions of [0, p^{−m}], each time dividing each interval in the proportions p : q. Given these intervals, define μ by putting a point mass |I_{k}| at the right endpoint of I_{k}, for each k = 0, 1, ... Note that for p = q = 1/2, μ consists of a unit mass at each positive integer.

Now, we are in a position to present our second main finding:

Theorem 2 The following holds, uniformly for all integers k,

P(H_{n} ≤ k) = F (p^{k}n) + O(n^{−1}),  (10)

where

F (x) = x ∫_{0}^{∞} e^{−xt}dμ(t) = ∫_{0}^{∞} e^{−t}dμ_{x}(t),  (11)

with μ_{x} denoting the dilated measure defined as above for the intervals xI_{0}, xI_{1}, …. In particular, when k = ⌊log_{P} n⌋ + κ where κ is an integer, then for large n the following asymptotic formula is true uniformly over κ

P(H_{n} ≤ ⌊log_{P} n⌋ + κ) = p^{κ−\{log_{P} n\}} ∫_{0}^{∞} e^{−tp^{κ−\{log_{P} n\}}}dμ(t) + O (\frac{1}{n}) ,  (12)

where {log_{P} n} = log_{P} n − ⌊log_{P} n⌋.

Remarks (i) Limiting Distribution Does Not Exist. The fractional part {log_{P} n} appearing in Theorem 2 is dense in the interval [0, 1) and does not converge. Thus, the limiting distribution of H_{n} − ⌊log_{P} n⌋ does not exist. In fact, we observe that:

lim inf_{n→∞} P(H_{n} ≤ ⌊log_{P} n⌋ + κ) ≤ p^{κ−1} ∫_{0}^{∞} e^{−tp^{κ−1}}dμ(t) ,
lim sup_{n→∞} P(H_{n} ≤ ⌊log_{P} n⌋ + κ) ≥ p^{κ} ∫_{0}^{∞} e^{−tp^{κ}}dμ(t) .

(ii) Symmetric Case p = q = 0.5. We observe that for p = q = 0.5 we obtain

F (x) = x ∑_{j=1}^{∞} e^{−jx} = \frac{x}{e^{x} − 1} ,

and our results coincide with those of [5].

(iii) It is easily seen that lim_{x→0} F (x) = 1 and lim_{x→∞} F (x) = 0. We conjecture that F (x) is always decreasing, as it is for p = 0.5 by the explicit formula in (ii). If F (x) is decreasing, then F (p^{x}) is a distribution function, and if Z is a random variable with this distribution, then (10) can be written

P(H_{n} ≤ k) = P(Z + log_{P} n ≤ k) + O(n^{−1}).

Hence, in this case, the distribution of H_{n} is well approximated by the distribution of ⌈Z + log_{P} n⌉; for example it follows that the total variation distance between the two distributions tends to 0 as n → ∞, which is a substitute for the failing limit distribution. (iv) It is possible to obtain further terms in the asymptotic formulae in Theorems 1 and 2 using the same methods.

3 Analysis and Proofs

In this section, we prove Theorems 1 and 2 using an analytical approach. In the next subsection, we transform the problem to the Poisson model (i.e., poissonize it), which is easier to solve. Then, we apply the Mellin transform (cf. Section 3.2) and a simple functional analysis (cf. Section 3.3) to obtain an asymptotic solution for the poissonized moments and the poissonized distribution for the height. Finally, we depoissonize these findings to recover our results for the original model.

3.1 Poissonization and Depoissonization

It is well known that often poissonization leads to a simpler solution due to unique properties of the Poisson distribution (cf. [9]). Poissonization is a technique which replaces the fixed population model (sometimes called the Bernoulli model) by a model in which the population varies according to the Poisson law (hence, Poisson model). In the case of the leader election algorithm, we replace n by a random variable N distributed according to Poisson with mean equal n. We shall apply analytical poissonization (cf. [10, 11, 13, 14, 20]) that makes use of the Poisson transform (i.e., exponential generating function as shown below). One must observe, however, that after solving the Poisson model (in most cases we can only solve it asymptotically!), we must depoissonize to recover the Bernoulli model results. In this subsection, we first derive functional equations for the Poisson model, and then present a general depoissonization lemma of Jacquet and Szpankowski [15] (cf. also [5, 11, 12, 13, 14, 20]) that we apply throughout the paper.

We now build the Poisson model. Let us define

G̃(z, u) = ∑_{n=0}^{∞} G_{n}(u)\frac{z^{n}}{n!} e^{−z} ,
X̃(z) = ∑_{n=0}^{∞} x_{n} \frac{z^{n}}{n!} e^{−z} ,
W̃(z) = ∑_{n=0}^{∞} w_{n} \frac{z^{n}}{n!} e^{−z} ,

where G_{n}(u), x_{n} and w_{n} are expressed as (2)–(4), respectively. They are poissonized versions of the corresponding quantities in the Bernoulli model.

Remark If z ≥ 0, then G̃(z, ·) is the probability generating function of H_{N(z)}, where the population size N(z) is random with the Poisson distribution Po(z). Note, however, that because of our convention G_{0} = 0 (or H_{0} = ∞), G̃(z, ·) is a defective probability generating function. This could be rectified by instead defining H_{0} = 0, but our choice is more convenient for us. Similarly, X̃(z) = \frac{∂}{∂u} G̃(z, u)|_{u=1} is for z ≥ 0 the expectation EH_{N(z)} of the height when the population is random Po(z), provided we here use the convention H_{0} = 0.

To see the achieved simplifications, we observe that the recurrences (2)–(4) now become:

G̃(z, u) = uG̃(pz, u) + uG̃(qz, u)e^{−pz} + (1 − u)ze^{−z} ,  (13)
X̃(z) = X̃(pz) + X̃(qz)e^{−pz} + 1 − (1 + z)e^{−z} ,  (14)
W̃(z) = W̃(pz) + W̃(qz)e^{−pz} + 2X̃(z) + 2 ((e^{−z} − 1) + ze^{−z})  (15)

for a complex z. The above functional equations have a simpler form than their corresponding Bernoulli model equations, but they are far from being trivial. The main difficulty lies in the fact that there is a factor e^{−pz} in front of G̃(qz, u), X̃(qz) and W̃(qz). Observe that in the symmetric case (i.e., p = q = 0.5) these functional equations reduce to the one analyzed in Szpankowski [22] (cf. also [5, 7, 16]). We solve these functional equations asymptotically (see the next two subsections) for z large and real. The next step is a depoissonization of these results, and we present now a general depoissonization result of Jacquet and Szpankowski [15] that generalize previous depoissonization lemmas of [11, 12, 13, 20]. Recall that a measurable function ψ: (0, ∞) → (0, ∞) is slowly varying if ψ(tx)/ψ(x) → 1 as x → ∞ for every fixed t > 0.

Lemma 1 [Depoissonization Lemma] Assume that G̃(z) = ∑_{n=0}^{∞} g_{n} \frac{z^{n}}{n!} e^{−z} is an entire function of a complex variable z. Suppose that there exist real constants a < 1, β, θ ∈ (0, π/2), c_{1}, c_{2}, and z_{0}, and a slowly varying function ψ such that the following conditions hold, where S_{θ} is the cone S_{θ} = {z : | arg(z)| ≤ θ}:

(I) For all z ∈ S_{θ} with |z| ≥ z_{0},

|G̃(z)| ≤ c_{1}|z|^{β}ψ(|z|);  (16)

(O) For all z ∉ S_{θ} with |z| ≥ z_{0},

|G̃(z)e^{z}| ≤ c_{2}e^{a|z|}.  (17)

Then for n ≥ 1,

g_{n} = G̃(n) + O (n^{β−1}ψ(n)) .  (18)

More precisely,

g_{n} = G̃(n) − \frac{1}{2}nG̃′′(n) + O (n^{β−2}ψ(n)) .  (19)

The “Big-Oh” terms in (18) and (19) are uniform for any family of entire functions G̃ that satisfy the conditions with the same a, β, θ, c_{1}, c_{2}, z_{0} and ψ.

3.2 Analysis of Moments

We now prove Theorem 1 using the Mellin transform and depoissonization techniques. We thus begin by studying the functions G̃(z, u), X̃(z) and Ṽ (z) defined above, which satisfy the functional equations (13)–(15). We write f^{∗}(s) or M(f, s) for the Mellin transform of a function f(x) of real parameter x, that is,

f^{∗}(s) = M(f, s) = ∫_{0}^{∞} f(x)x^{s−1}dx

provided the above integral converges. A beautiful survey on Mellin transform can be found in [8], and we refer the reader to this paper for details concerning Mellin transform.

The Poisson mean X̃(z) and second factorial moment W̃(z) satisfy function equations (14) and (15), respectively. We observe that from the recurrence equations (3) and (4) we immediately prove that x_{n} = O(ln(n + 1)) and w_{n} = O(ln^{2}(n + 1)). It follows that X̃ and W̃ are entire functions. Moreover, it follows easily that X̃(x) = O(ln(x + 1)) for x > 0. In order to apply the depoissonization lemma we have to extend this estimate to complex arguments in a cone S_{θ}.

Thus fix θ = π/4, say; we claim that

|X̃(z)| = O(ln(|z| + 1)),  z ∈ S_{θ}.  (20)

This is proved by induction along increasing domains (cf. [14]) as follows: Let ρ = max(p, q)^{−1} > 1. Suppose that R and A are such that

|X̃(z)| ≤ A ln(|z|),  z ∈ S_{θ}, 2 ≤ |z| ≤ R.  (21)

If now z ∈ S_{θ} with R ≤ |z| ≤ ρR, then the recursion relation (14) yields, provided R min(p, q) ≥ 2,

|X̃(z)| ≤ |X̃(pz)| + |X̃(qz)|e^{−p|z| cos θ} + 1 + (1 + |z|)e^{−|z| cos θ}
≤ A ln(|z|) + A ln(p) + A ln(R)e^{−pR cos θ} + 2 + (cos θ)^{−1}.  (22)

Now choose R_{0} ≥ 2/ min(p, q) such that ln(p) + ln(R)e^{−pR cos θ} ≤ −δ < 0 for R ≥ R_{0}. If A ≥ 3/δ cos θ and R ≥ R_{0}, then (22) shows that (21) holds also for z ∈ S_{θ} with R ≤ |z| ≤ ρR. Since clearly (21) holds for R = R_{0} and a suitable large A, (21) holds by induction for R = ρ^{n}R_{0} for every n ≥ 0 (with the same A) and (20) follows for |z| ≥ 2; for small |z| we use X̃(z) = O(|z|^{2}), |z| ≤ 2, because x_{0} = x_{1} = 0.

Similarly one proves, using (15) and (20),

|W̃(z)| = O(ln^{2}(|z| + 1)),  z ∈ S_{θ}.  (23)

In particular, (20) and (23) hold for real x > 0. It follows that the Mellin transforms X^{∗}(s) and W^{∗}(s) exist (and are analytic) in the strip −1 < ℜs < 0. (In fact, since x_{1} = w_{1} = 0, they exist for −2 < ℜs < 0, but we do not need this.)

Let us now concentrate on the first moment. Define

T_{1}(z) = X̃(qz)e^{−pz} .  (24)

Then, T_{1}(z) is an entire function and the Mellin transform T_{1}^{∗}(s) exists at least for −2 < ℜs < ∞. Indeed, since every x_{n} ≥ 0, we have

|X̃(z)e^{z}| ≤ X̃(|z|)e^{|z|}  (25)

and thus |X̃(z)| ≤ X̃(|z|)e^{|z|−ℜz}. Hence, if x > 0 and |z − x| < px/4,

|T_{1}(z)| ≤ X̃(q|z|)e^{q|z|−ℜz} ≤ X̃(q|z|)e^{qx−x+2|z−x|} ≤ X̃(q|z|)e^{−px/2} = O(e^{−px/2} ln(1 + x)).

Thus, by Cauchy’s estimate, for every m ≥ 0,

T_{1}^{(m)}(x) = O(x^{−m}e^{−px/2} ln(1 + x)), x > 0.

Since further T_{1}^{(m)}(x) is bounded for 0 ≤ x ≤ 1, the Mellin transform T_{1}^{(m)∗}(s) exists at least for 0 < ℜs < ∞, and is bounded on each line ℜs = σ > 0.

Integration by parts yields s(s + 1) ⋯ (s + m − 1)T_{1}^{∗}(s) = (−1)^{m}T_{1}^{(m)∗}(s + m) and thus the estimate

|T_{1}^{∗}(σ + iτ)| ≤ \frac{C(σ, m)}{(1 + |τ|)^{m}}  (26)

for each m ≥ 2 and −2 < σ < ∞; C(σ, m) is bounded for σ in a compact interval of (−2, ∞) and m fixed. In particular, T_{1}^{∗}(σ + iτ) is integrable in τ for each σ > −2.

We re-write (14) as follows:

X̃(z) = X̃(pz) + T_{1}(z) − (e^{−z} − 1) − ze^{−z} .

Taking the Mellin transform of the above we have, for −1 < ℜs < 0,

X^{∗}(s) = p^{−s}X^{∗}(s) + T_{1}^{∗}(s) − Γ(s) − Γ(s + 1),  (27)

where Γ(·) is the Euler gamma function. Now, we can solve (27) to get

X^{∗}(s) = \frac{Γ(s) + Γ(s + 1) − T_{1}^{∗}(s)}{(P)^{s} − 1},  −1 < ℜs < 0.  (28)

The right hand side extends to a meromorphic function in the half plane −1 < ℜs < ∞, with poles at χ_{k} = 2πik/ ln(P), k = …, −1, 0, 1, 2, . . .. All poles are simple except the one at 0 (k = 0), which is double.

It follows from (28) and (26) that for every σ ∈ (−1, 0) ∪ (0, ∞), |X^{∗}(σ + iτ)| = O((1 + τ^{2})^{−1}) ∈ L^{1}(dτ). The Mellin (Fourier) inversion formula thus yields for x > 0 the following.

X̃(x) = \frac{1}{2πi} ∫_{−1/2−i∞}^{−1/2+i∞} x^{−s}X^{∗}(s)ds.  (29)

Shifting the line of integration to ℜs = R > 0 (using the Cauchy residue theorem) we obtain for any large R,

X̃(x) = O(x^{−R}) − ∑_{−∞}^{∞} Res_{χ_{k}}(x^{−s}X^{∗}(s)).  (30)

Let α_{k} = Res_{χ_{k}}X^{∗}(s). If k ≠ 0, then

α_{k} = ((1 + χ_{k})Γ(χ_{k}) − T_{1}^{∗}(χ_{k}))/ ln(P);

in particular this implies α_{k} = O(|k|^{−n}) for each n > 0. Moreover, for k ≠ 0,

Res_{χ_{k}}(x^{−s}X^{∗}(s)) = x^{−χ_{k}}Res_{χ_{k}}X^{∗}(s) = α_{k}e^{−2πik log_{1/p} x}.

For k = 0, we obtain

Res_{0}(x^{−s}X^{∗}(s)) = − ln(x)/ ln(P) + Res_{0}X^{∗}(s) = − log_{1/p} x − \frac{1}{2} + \frac{1 − γ − T_{1}^{∗}(0)}{ln(P)}.

Consequently, for every R > 0,

X̃(x) = log_{1/p} x + \frac{1}{2} − \frac{1 − γ − T_{1}^{∗}(0)}{ln(P)} + δ_{1}(log_{1/p} x) + O(x^{−R}),  (31)

where δ_{1}(t) = − ∑_{k≠0} α_{k}e^{−2πikt} is a periodic function with mean 0.

We now apply the depoissonization lemma. We have already verified condition (I) in (20), with β = 0 and ψ(x) = ln(x + 1). Condition (O) can be verified similarly, but it is also possible to avoid induction and use the recursion just once as follows. First, by (25) and (20), |X̃(z)e^{z}| ≤ X̃(|z|)e^{|z|} ≤ Ce^{|z|} ln(|z| + 1) for every z. Next,

(14) can be written

e^{z}X̃(z) = e^{qz}e^{pz}X̃(pz) + e^{qz}X̃(qz) + e^{z} − 1 − z,

which thus yields

|e^{z}X̃(z)| ≤ C ln(1 + |z|) (e^{p|z|+qℜz} + e^{q|z|}) + e^{ℜz} + 1 + |z|,

and (O) follows.

Depoissonization Lemma now gives immediately, by (18), the first moment

EH_{n} = x_{n} = log_{P} n + \frac{1}{2} − \frac{1 − γ − T_{1}^{∗}(0)}{ln P} + δ_{1}(log_{P} n) + O(ln n/n).  (32)

The error term can be improved to O(1/n), which yields (5), by instead using (19) and verifying that X̃′′(x) = O(x^{−2}), x > 0. The latter estimate is easily obtained by differentiating (29) twice (moving the derivatives inside the integral) and estimating the integral by residue calculus as above. The details can be found in [14, 15].

Now, the second moment. Let T_{2}(z) = W̃(qz)e^{−pz}; then the Mellin transform T_{2}^{∗}(s) exists for −2 < ℜs < ∞ and (15) yields, for −1 < ℜs < 0,

W^{∗}(s) = p^{−s}W^{∗}(s) + T_{2}^{∗}(s) + 2X^{∗}(s) + 2Γ(s) + 2Γ(s + 1),  (33)

and thus

W^{∗}(s) = \frac{2X^{∗}(s)}{1 − p^{−s}} + \frac{2Γ(s) + 2Γ(s + 1) + T_{2}^{∗}(s)}{1 − p^{−s}}
= \frac{−2Γ(s) − 2Γ(s + 1) + 2T_{1}^{∗}(s)}{((P)^{s} − 1)^{2}} − \frac{2Γ(s) + 2Γ(s + 1) + T_{2}^{∗}(s)}{(P)^{s} − 1}. (34)

As above, we can obtain an asymptotic expansion of W̃(z) by finding the inverse of the Mellin transform. Thus, the Poisson variance Ṽ (z) = W̃(z) + X̃(z) − X̃^{2}(z) becomes, after some lengthy but elementary calculations,

Ṽ (x) = \frac{π^{2}}{6 ln^{2} p} + \frac{1}{12} + \frac{2T_{1}^{∗}(0) + T_{2}^{∗}(0)}{ln(P)}

+ \frac{−1 − 2T_{1}^{∗′}(0) + 2(1 − γ)T_{1}^{∗}(0) − (T_{1}^{∗}(0))^{2}}{ln^{2} p} + δ_{3}(log_{1/p} x) + O(x^{−R})(35)

where δ_{3}(t) = δ_{2}(t) − [δ_{1}^{2}]_{0} is a small fluctuating function. Applying now the Depoissonization Lemma to W̃ (verifying (O) as for X̃), we easily obtain (8). In fact, it follows as above, using (19), that w_{n} = W̃(n) + O(ln n/n) ((18) would give O(ln^{2} n/n)), and this together with the already proven x_{n} = X̃(n) + O(1/n) yields Var H_{n} = w_{n} + x_{n} − x_{n}^{2} = Ṽ (n) + O(ln n/n) (cf. [14, 15]).

To complete the proof of Theorem 1, we need a method of evaluating the constants T_{1}^{∗}(0), T_{2}^{∗}(0), and T_{1}^{∗′}(0). Let again x_{n} = EH_{n} which we can compute for any n from the recurrence above. We need an evaluation of the Mellin transform of X̃(z) = ∑_{n≥2} x_{n} \frac{z^{n}}{n!} e^{−z} since x_{0} = x_{1} = 0. Thus noting that M(e^{−z}, s) = Γ(s) for ℜ(s) > 0, and furthermore M(z^{n}e^{−z}, s) = Γ(s + n) for ℜ(s) > −n, we immediately derive

X^{∗}(s) = ∑_{n=2}^{∞} \frac{x_{n}}{n!} M(z^{n}e^{−z}, s) = ∑_{n=2}^{∞} \frac{x_{n}}{n!} Γ(s + n)  (36)

provided ℜ(s) ∈ (−2, 0). Observe that the series converges absolutely in this range by the estimate of x_{n} above.

Moreover,

T_{1}(z) = X̃(qz)e^{−pz} = ∑_{n≥2} x_{n} \frac{(qz)^{n}}{n!} e^{−z} = ∑_{n≥2} \frac{x_{n}q^{n}}{n!} z^{n}e^{−z}

and thus, similarly,

T_{1}^{∗}(s) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n!} Γ(s + n)  (37)

provided −2 < ℜ(s) < ∞. In particular,

T_{1}^{∗}(0) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n!} Γ(n) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n} ,  (38)

which has an exponential rate of convergence.

Now, we can move on and estimate T_{1}^{∗′}(0). Taking the derivative of (37) at s = 0 and arguing as before we arrive at the following formula

T_{1}^{∗′}(0) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n!} Γ′(n) = ∑_{n=2}^{∞} \frac{x_{n}q^{n}}{n} Ψ(n),  (39)

where Ψ(s) = Γ′(s)/Γ(s) is the Psi function; recall that for n ≥ 2 we have Ψ(n) = −γ + H_{n−1} (where H_{n} here is the n-th Harmonic number).

Of course, T_{2}^{∗}(0) can be computed in a similar fashion

T_{2}^{∗}(0) = ∑_{n=2}^{∞} \frac{w_{n}q^{n}}{n} .  (40)

This completes the proof of Theorem 1.

3.3 Analysis of the Distribution

We now prove Theorem 2. We start with the functional equation (13). After defining H̃(z, u) = G̃(z, u)/(1 − u) we obtain

H̃(z, u) = uH̃(pz, u) + uH̃(qz, u)e^{−pz} + ze^{−z} .  (41)

Let now G̃_{k}(z) = ∑_{n=1}^{∞} P(H_{n} ≤ k)\frac{z^{n}}{n!} e^{−z}. Then, H̃(z, u) = ∑_{k=0}^{∞} u^{k}G̃_{k}(z) and an identification of the coefficients of u in (41) yield

G̃_{0}(z) = ze^{−z}
G̃_{k+1}(z) = G̃_{k}(pz) + e^{−pz}G̃_{k}(qz) ,  k ≥ 0.  (42)

We claim that the above functional equation for G̃_{k}(z) is solved by

G̃_{k}(z) = p^{k}z ∫_{0}^{p^{−k}} e^{−p^{k}zt}dμ(t)  (43)

(where μ is defined just above Theorem 2). In fact, the case k = 0 is simple, because μ restricted to [0, 1] only consists of a point mass at 1, and thus the integral equals e^{−z}. For k ≥ 1, we use the fact that the measure μ on (p^{−k}, p^{−k−1}] is obtained from μ on (0, p^{−k}] by a translation and dilation, so that for every function f,

∫_{p^{−k}+}^{p^{−k−1}} f(t)dμ(t) = \frac{q}{p} ∫_{0}^{p^{−k}} f(p^{−k} + \frac{q}{p}t)dμ(t)

and thus

∫_{0}^{p^{−k−1}} f(t)dμ(t) = ∫_{0}^{p^{−k}} f(t)dμ(t) + \frac{q}{p} ∫_{0}^{p^{−k}} f(p^{−k} + \frac{q}{p}t)dμ(t).

It is now easy to see that (43) satisfies (42).

Moreover, (43) trivially holds also for k < 0, with both sides zero; hence (43) holds for all integers k.

We next observe that, with F (x) defined in (11),

|G̃_{k}(n) − F (p^{k}n)| = p^{k}n ∫_{p^{−k}+}^{∞} e^{−p^{k}nt}dμ(t) ≤ p^{k}n ∫_{p^{−k}}^{∞} e^{−p^{k}nt}dt = e^{−n}  (44)

when k ≥ 0, and similarly |G̃_{k}(n) − F (p^{k}n)| = F (p^{k}n) ≤ p^{k}ne^{−p^{k}n} + e^{−n} ≤ (n + 1)e^{−n} when k < 0. Thus, to complete the proof of Theorem 2 it suffices to apply Depoissonization Lemma, provided we verify conditions (I) and (O) uniformly for all k (and some fixed θ), with β = 0 and ψ = 1. This can be done as above using induction along increasing domains, but we give a simpler argument. Indeed, in order to verify (I) we can use the exact formula (43) and observe that for any decreasing function f ≥ 0 on (0, ∞), ∫_{0}^{∞} f dμ(t) ≤ ∫_{0}^{∞} f dt; hence if ℜz > 0,

|G̃_{k}(z)| ≤ p^{k}|z| ∫_{0}^{∞} e^{−p^{k}ℜzt} dμ(t) ≤ p^{k}|z| ∫_{0}^{∞} e^{−p^{k}ℜzt} dt = \frac{|z|}{ℜz} .

Consequently (I) holds, uniformly in k, for any θ < π/2.

For (O) we first observe that

|e^{z}G̃_{k}(z)| ≤ ∑_{n=0}^{∞} \frac{|z|^{n}}{n!} = e^{|z|}.

Hence (42) yields, for k ≥ 0,

|e^{z}G̃_{k+1}(z)| ≤ |e^{qz}||e^{pz}G̃_{k}(pz)| + |e^{qz}G̃_{k}(qz)| ≤ e^{qℜz+p|z|} + e^{q|z|} ≤ e^{a|z|}

for some a < 1 and z sufficiently large. Since further |e^{z}G̃_{0}(z)| = |z|, also (O) holds uniformly in k. This completes the proof of Theorem 2.

ACKNOWLEDGEMENT

We would like to thank Profs. J. Fill and H. Mahmoud for several discussions concerning this paper.

References

[1] Abramowitz, M. and Stegun, I., eds. Handbook of Mathematical Functions. Wiley-Interscience, New York, 1972.

[2] Brassard, G. and Bratley, P. Algorithmics: Theory and Practice. Prentice Hall, Englewood Cliffs, New Jersey 1988.

[3] Devroye, L. A Study of Trie-Like Structures Under the Density Model. Annals of Applied Probability, 2, 402–434, 1992.

[4] Fayolle, G., Flajolet, P., and Hofri, M. On a Functional Equation Arising in the Analysis of a Protocol for a Multiaccess Broadcast Channel, Adv. Appl. Probab., 18, 441–472, 1984.

[5] Fill, J. A., Mahmoud, H. M., and Szpankowski, W. On the Distribution for the Duration of a Randomized Leader Election Algorithm. Ann. Appl. Probab., 6, 1260–1283, 1996.

[6] Fill, J. Personal Communication.

[7] Flajolet, P., Régnier, M. and Sotteau, D. Algebraic Methods for Trie Statistics, Annals of Discrete Mathematics, 25, 145-188, 1985.

[8] Flajolet, P., Gourdon, X., and Dumas, P. Mellin Transforms and Asymptotics: Harmonic Sums. Theoretical Computer Science, 144, 3–58, 1995.

[9] Gonnet, G. and Munro, J. The Analysis of Linear Probing Sort by the Use of a New Mathematical Transform, Journal of Algorithms, 5, 451-470, 1984.

[10] Grabner, P. Searching for Losers. Random Structures and Algorithms, 4, 99–110, 1993.

[11] Jacquet, P. and Régnier, M. Trie Partitioning Process: Limiting Distributions. Lecture Notes in Computer Science, 214, 196–210, Springer, New York, 1986.

[12] Jacquet, P. and Régnier, M. Normal Limiting Distribution of the Size of Tries, Proc. Performance’87, 209-223, North Holland, Amsterdam 1987

[13] Jacquet, P. and Szpankowski, W. Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm. SIAM J. Computing, 18, 777–791, 1989.

[14] Jacquet, P. and Szpankowski, W. Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees. Theoretical Computer Science, 144, 161– 197, 1995.

[15] Jacquet, P. and Szpankowski, W. Analytical Depoissonization and Its Applications, Theoretical Computer Science, to appear.

[16] Knuth, D. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison–Wesley, Reading, Massachusetts, 1973.

[17] Kuipers, L. and Niederreiter, H. Uniform Distribution of Sequences. Wiley, New York, 1974.

[18] Mahmoud, H. Evolution of Random Search Trees. Wiley, New York, 1992.

[19] Prodinger, H. How to Select a Loser. Discrete Math., 120, 149–159, 1993.

[20] Rais, B., Jacquet, P. and Szpankowski, W. Limiting Distribution for the Depth in PATRICIA Tries. SIAM J. on Discrete Math., 3, 355–362, 1993.

[21] Schmid, U. The Average CRI-length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects, Proc. ICALP 92, Vienna, 223-234, 1992.

[22] Szpankowski, W. Solution to a Linear Recurrence Equation Arising in the Analysis of Some Algorithms. SIAM J. Alg. Disc. Meth., 8, 233–250, 1987.