Combinatorics, Probability and Computing (1999) 8, 473–482. Printed in the United Kingdom
`c 1999 Cambridge University Press
`
`Studying Balanced Allocations with
`Di↵erential Equations†
`
`M I C H A E L M I T Z E N M A C H E R§
`
`Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301, USA
`
`(e-mail: michaelm@pa.dec.com)
`
`Received 4 November 1997; revised 25 June 1998
`
`Using di↵erential equations, we examine the greedy algorithm studied by Azar, Broder,
`Karlin and Upfal for distributed load balancing [1]. This approach yields accurate estimates
`of the actual load distribution, provides insight into the exponential improvement greedy
`o↵ers over simple random selection, and allows one to prove tight concentration theorems
`about the loads in a straightforward manner.
`
`1. Introduction
`
`Suppose that n balls are placed into n bins, with each ball being placed into a bin chosen
`independently and uniformly at random. Let the load of a bin be the number of balls
`in that bin after all balls have been thrown. It is well known that, with high probability,
`the maximum load upon completion will be approximately log n
`log log n [8]. (We use with high
`probability to mean with probability at least 1 O(1/n), where n is the number of balls.
`Also, log will always mean the natural logarithm, unless otherwise noted.)
`Azar, Broder, Karlin and Upfal considered how much more evenly distributed the load
`would be if each ball had two (or more) choices [1]. Suppose that the balls are placed
`sequentially, and each ball is placed into the less full of two bins chosen independently and
`uniformly at random with replacement (breaking ties arbitrarily). In this case, they showed
`that the maximum load drops to log log n
`log 2 + O(1) with high probability. If each ball instead
`
`† A preliminary version of this work appeared in the Proceedings of the 37th Annual IEEE Symposium on the
`Foundations of Computer Science, October 1996.
`§ Much of this work was done at U.C. Berkeley, supported by a fellowship from the Oce of Naval Research
`and by NSF grant CCR-9505448.
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`Apple 1222
`
`1
`
`

`
`474
`
`M. Mitzenmacher
`
`has d choices, then the maximum load will be log log n
`log d + O(1) with high probability. Having
`two choices hence yields a qualitatively di↵erent type of behaviour from the single choice
`case, leading to an exponential improvement in the maximum load; having more than
`two choices further improves the maximum load by only a constant factor. This result has
`important implications for distributed load balancing, hashing, and PRAM simulation [1].
`
`Following Azar, Broder, Karlin and Upfal, we refer to the algorithm in which each
`ball has d random choices as greedy(d). In this paper, we develop an alternative method
`of studying the performance of greedy(d) using di↵erential equations. The di↵erential
`equations describe the limiting performance of greedy(d) as the number of balls and
`bins tends to infinity. As we will demonstrate, the description of the limiting performance
`proves highly accurate, even when n is relatively small. In particular, we note that from
`our results one can determine the fraction of bins of any fixed load at the end of the
`process for the limiting case as n goes to infinity. These limiting quantities provide accurate
`estimates for the fraction of bins of each fixed load for suciently large systems. This
`analysis therefore adds significantly more detail to the previous analysis of [1]. Moreover,
`besides giving more insight into the actual performance of greedy, our methods provide
`a great deal of intuition behind the behavioural di↵erence between one and two choices.
`
`Our motivation in studying this problem is twofold. First, we wish to demonstrate and
`highlight this methodology, and encourage its use for studying random processes. While
`this methodology is by no means new, its uses have been surprisingly limited. The technical
`results justifying the relationship between families of Markov processes and di↵erential
`equations date back at least to Kurtz [13, 14]. Karp and Sipser provided an early use of
`this technology to analyse an algorithm for finding maximum matchings in sparse random
`graphs [11]. Other past applications in the analysis of algorithms include [9, 12], and more
`recently many more have been found (see, for example, [2, 3, 15, 17, 21], to name a few).
`
`Our second motivation is to demonstrate the power of using two choices. This idea dates
`back at least as far as the work of Eager, Lazowska and Zahorjan [7], who examined a
`dynamic load balancing model based on viewing processors as single server queues. In the
`static setting, this idea was also studied by Hajek [9], who used the same approach we un-
`dertake to determine the fraction of empty bins. The aforementioned exponential improve-
`ment in behaviour was noted and proved first in a paper by Karp, Luby and Meyer auf der
`Heide [10]. The work by Azar, Broder, Karlin and Upfal examined a simpler model that
`clarified the argument and provided many new results. Related work by the author [16, 17],
`as well as by others [20], examines the power of two choices in dynamic settings. Continued
`work in the area includes recent work by Stemann [19] and Czumaj and Stemann [6].
`
`In the rest of the paper, we explain the derivation of the di↵erential equations that
`describe the greedy strategy of [1] and compare the results from the di↵erential equations
`with simulations. We also demonstrate how the equations give more insight into the
`behaviour of greedy and how the equations relate to the work in [1].
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`2
`
`

`
`Studying Balanced Allocations with Di↵erential Equations
`
`475
`
`2. The di↵erential equations
`
`In this section, we demonstrate how to establish a family of di↵erential equations that
`can be used to model the behaviour of the greedy strategy of [1]. We begin the process
`with m balls and n bins. We shall require for our analysis that m = cn for some constant
`c. Balls arrive sequentially, and, upon arrival, each ball chooses d bins independently and
`uniformly at random (with replacement); the ball is then placed in the least loaded of
`these bins (with ties broken arbitrarily).
`We first ask how many bins remain empty after the protocol greedy(d) terminates.
`This question has a natural interpretation in the task-processor model: how many of
`our processors are not utilized? The question can also be seen as a matching problem
`on random bipartite graphs: given a bipartite graph with n vertices on each side such
`that each vertex on the left has d edges to vertices chosen independently and uniformly
`at random on the right, what is the expected size of the greedy matching obtained by
`sequentially matching vertices on the left to a random unmatched neighbour? Our attack,
`again, is to consider this system as n ! 1. This question has been previously solved
`by Hajek using entirely similar techniques [9]. We shall briefly repeat his argument with
`some additional insights. Once we show how to answer the question of the number of
`empty bins, we shall extend it to the more general load balancing problem.
`
`2.1. The empty bins problem
`We set up the problem of the number of empty bins by developing a Markov chain with
`a simple state that describes the balls and bins process. We first establish a concept of
`time. Let Y (T ) be the number of non-empty bins after T balls have been thrown. Then
`{Y (i)}, i = 0 . . . m, is clearly a Markov chain. Moreover,
`n ◆d
`E[Y (T + 1) Y (T )] = 1 ✓ Y (T )
`
`(2.1)
`
`,
`
`since the probability that a ball finds all non-empty bins among its d choices is (Y (T )/n)d.
`The notation becomes somewhat more convenient if we scale by a factor of n. We let t
`be the time at which exactly nt balls have been thrown, and we let y(t) be the fraction of
`non-empty bins. Then equation (2.1) becomes
`E[y(t + 1/n) y(t)]
`1/n
`
`= 1 (y(t))d .
`
`(2.2)
`
`We claim the random process described by equation (2.2) is well approximated by the
`trajectory of the di↵erential equation
`
`dy
`dt
`where this equation has been obtained from equation (2.2) by replacing the right-hand
`side with the appropriate limiting value as n tends to infinity, dy/dt. That the random
`
`= 1 yd,
`
`(2.3)
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`3
`
`

`
`476
`
`M. Mitzenmacher
`
`process given by the Markov chain closely follows the trajectory given by the di↵erential
`equation follows easily from known techniques, such as, for example, Kurtz’s theorem, or
`the similar work on random graphs by Wormald [21]. (As previously mentioned, the balls
`and bins process has a natural interpretation in terms of random bipartite graphs.)
`To clarify this connection, here we state a form of Kurtz’s theorem, as given in [18,
`Theorem 5.3]. We provide the necessary notation, and then relate the notation back to the
`underlying balls and bins process. Suppose we are given a finite set of vectors {~e1, . . . ,~ek}
`in Rd. We consider an initial process ~x(t) with generator
`kXi=1
`ni(~x)✓f✓~x +
`kXi=1
`
`Lnf(~x) =
`
`The limiting operator L1 satisfies
`
`~ei
`
`n◆ f(~x)◆ .
`
`i(~x)(f(~x + ~ei) f(~x))
`and a scaled process ~zn(t) with generator
`
`Lf(~x) =
`
`kXi=1
`kXi=1
`
`ni(~x)hrf(~x),~eii,
`and corresponds to the deterministic solution ~z1 of the equation
`
`L1f(~x) =
`
`i(~z1(t))~ei.
`
`(2.4)
`
`d d
`
`~z1(t) =
`t
`
`We relate the above notation to the problem of keeping track of the fraction of non-
`empty bins. For convenience, think of the times balls enter the system as being determined
`by a Poisson arrival process at a rate of one per unit time. (This does not a↵ect the result;
`it merely simplifies the discussion. See, for example, [13].) In the scaled process with n
`balls and n bins, n balls arrive per unit time. The process is one-dimensional, and hence
`~e1 = (1). The rate function 1 satisfies 1(~x) = 1 xd
`1: this is just the probability that an
`incoming ball lands in an empty bin. The limiting process is then given by the di↵erential
`equation (2.4), which in this case is equivalent to equation (2.3); note that for convenience
`we have dropped the vector notation and simply used the variable y.
`Kurtz’s theorem states that the scaled processes approach the limiting process, with
`error bounds similar to Cherno↵-like bounds.
`
`Theorem 2.1 (Kurtz’s theorem [18], Theorem 5.3). Let i(~x) :R d ! R+ be uniformly
`bounded and Lipschitz continuous, and let ~z1 be the unique solution of (2.4) with ~z1(0) =
`~x(0). For each finite T there exist a positive constant C1 and a function C2 with
`C2(✏)
`C2(✏)
`✏2 2 (0,1) and lim
`✏
`✏"1
`
`= 1
`
`lim
`✏#0
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`4
`
`

`
`Studying Balanced Allocations with Di↵erential Equations
`
`477
`
`such that, for all n > 1 and ✏>0,
`
`06t6T |~zn(t) ~z1(t)| > ✏◆ 6 C1enC2(✏).
`Pr✓ sup
`
`Moreover, C1 and C2 can be chosen independently of ~x.
`
`The connection between the balls and bins process and the di↵erential equation (2.3)
`yields the following theorem.
`
`Theorem 2.2. Suppose cn balls are thrown into n bins according to the greedy(d) protocol
`for some constant c. Let Ycn be the number of non-empty bins when the process terminates.
`Then limn!1 E[ Ycn
`n ] =y c, where yc < 1 satisfies
`
`c =
`
`1Xi=0
`
`yid+1
`c
`(id + 1)
`
`.
`
`Proof. The preconditions for Kurtz’s theorem (the above or [14, Chapter 8]) are easily
`checked for the one-dimensional system described by (2.3), so by Kurtz’s theorem we have
`that this di↵erential equation is the correct limiting process.† Instead of solving (2.3) for
`1yd =P1i=0 yid. We integrate up to
`dy = 1
`y in terms of t, we solve for t in terms of y: dt
`some time t, yielding
`
`t =
`
`1Xi=0
`
`y(t)id+1
`(id + 1)
`
`.
`
`(2.5)
`
`From equation (2.5), given d we can solve for y(t) for any value of t using, for example,
`binary search. One can also attempt to find an equation for y in terms of d and t; standard
`integral tables give such equations when d = 2, 3 and 4, for example. When t = c, all of
`the balls have been thrown, and the process terminates. Plugging t = c into equation (2.5)
`yields the theorem, with yc = y(c).
`
`We may actually use Kurtz’s theorem to obtain a concentration result.
`
`Theorem 2.3.
`
`In the notation of Theorem 2.2, | Ycn
`n yc| is, with high probability,
`n ! ,
`O r log n
`
`where the constant depends on c.
`
`† Again, it appears that there might be a problem here since we consider events occurring at discrete time-steps,
`instead of according to random times from a Poisson process. One can always adopt the convention that each
`discrete time-step corresponds to an amount of time given by an exponentially distributed random variable.
`In the limiting case, this distinction disappears.
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`5
`
`

`
`478
`
`M. Mitzenmacher
`
`One can also obtain entirely similar bounds for Ycn using more straightforward mar-
`tingale arguments. In the following, we assume familiarity with basic martingale theory:
`see, for example, [4, Chapter 7] for more information. We use the following form of the
`martingale tail inequality due to Azuma [5]:
`
`Lemma 2.1 (Azuma [5]). Let X0, X1, . . . Xm be a martingale sequence such that, for each
`k,
`
`|Xk Xk1| 6 1.
`Pr(|Xm X0| >↵ pm) < 2e↵2/2.
`In the notation of Theorem 2.2, Pr(|Ycn E[Ycn]| >↵ pcn) < 2e↵2/2 for any
`
`Then, for any ↵>0,
`
`Theorem 2.4.
`↵>0.
`
`Proof. For 0 6 j 6 cn, let Fj be the -field of events corresponding to the possible
`states after j balls have been placed, and Zj = E[Ycn|Fj] be the associated conditional
`expectation of Ycn. Then the random variables {Zj}cn
`j=0 form a Doob martingale, and it is
`clear that |Zj Zj1| 6 1. The theorem now follows from Lemma 2.1.
`Theorem 2.4 implies that Ycn is within O(pn log n) of its expected value with high
`probability; however, the martingale approach does not immediately lead us to the value
`to which Ycn/n converges. This is a standard limitation of the martingale approach: in
`contrast, the di↵erential equations approach allows us to find the mean as well as prove
`concentration around the mean.
`
`2.2. Bins with fixed load
`We can extend the previous analysis to find the fraction of bins with load at least (or
`exactly) k for any constant k as n ! 1. We first establish the appropriate Markov chain.
`Let si(t) be the fraction of bins with load at least i at time t, where again at time t exactly
`nt balls have been thrown. Then the corresponding di↵erential equations regarding the
`growth of the si (for i > 1) are easily determined:
`
`dsi
`dt
`s0
`
`
`
`i1 sd= (sd
`i )
`= 1.
`
`for i > 1 ;
`
`(2.6)
`
`8<:
`
`The di↵erential equations have the following simple interpretation: for there to be an
`increase in the number of bins with at least i balls, the d choices of a ball about to be
`placed must all be bins with load at least i 1, but not all bins with load at least i.
`In the context of the notation established for Kurtz’s theorem, we let ~x be a k-
`dimensional vector, with ~ei being a standard unit vector in the ith dimension. Then
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`6
`
`

`
`Studying Balanced Allocations with Di↵erential Equations
`
`479
`
`Table 1 Predicted behaviour for greedy(d) and average results from 100 simulations with 1 million balls.
`
`d = 2
`prediction
`
`1 million
`simulation
`
`d = 3
`prediction
`
`1 million
`simulation
`
`s1
`s2
`s3
`s4
`s5
`
`0.7616
`0.2295
`0.0089
`0.000006
`< 1011
`
`0.7616
`0.2295
`0.0089
`0.000007
`0
`
`0.8231
`0.1765
`0.00051
`< 1011
`< 1011
`
`0.8230
`0.1765
`0.00051
`0
`0
`
`i1 xd
`
`1(~x) = 1 xd1 and i(~x) =x d
`i for i >1. The corresponding limiting solution given
`by (2.4) is then equivalent to the system (2.6), where again we have removed the vector
`notation for convenience.
`In contrast to Section 2.1, where we could derive a formula for the fraction of empty bins,
`we are not aware of how to determine explicit formulae for si(t) in general. These systems
`of di↵erential equations can be solved numerically using standard methods, however;
`for up to any fixed k and t, we can accurately determine sk(t). By applying Kurtz’s
`theorem to the k-dimensional process (as in Theorem 2.3) or martingale arguments (as in
`Theorem 2.4), one can show that these results will be accurate with high probability.
`We also demonstrate that our technique accurately predicts the behaviour of the
`greedy(d) algorithm by comparing with simulation results. The first and third columns
`of Table 1 shows the values of si(1) for d = 2 and d = 3 as calculated from the di↵erential
`equations. We use these values as predictions for the process where we throw n balls into
`n bins. From the predictions with d = 2, one would not expect to see bins with load five
`until billions of balls have been thrown. Similarly, choosing d = 3 one expects a maximum
`load of three until billions of balls have been thrown. These results match our simulations
`of several hundred runs with up to thirty-two million balls, the largest simulation we have
`attempted. We also present the averages from one hundred simulations of one million
`balls for d = 2 and d = 3, which demonstrate the accuracy of the technique in predicting
`the behaviour of the system. Further simulations reveal that, in general, the solution given
`by the limiting system of di↵erential equations becomes more accurate as n grows, and
`the deviation from this solution is small, as one would expect. This accuracy is a marked
`advantage of this approach: previous techniques have not provided ways of concretely
`predicting actual performance.
`
`2.3. Relationship to O(log log n) bounds
`We can also use the di↵erential equations to provide an alternative derivation of a key idea
`from the proof of the upper bounds on the maximum load of greedy(d). The approach of
`looking at the underlying di↵erential equations provides insight into how the sk decrease,
`which is essential to determining the O(log log n) bounds.
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37) (cid:36)5(cid:35)D935,(cid:11)(cid:6)(cid:11)(cid:6)(cid:5)3(cid:33)(cid:32)(cid:37)5(cid:32)(cid:37)(cid:5)94(cid:5)C(cid:35)(cid:32),31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26),94,1(cid:35)(cid:37)93(cid:30)5,0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)(cid:5)(cid:35)5(cid:36)(cid:33)C(cid:35)35(cid:5)(cid:32)1(cid:31)5(cid:5)0(cid:6)(cid:14)(cid:12)(cid:9)(cid:11)(cid:10)(cid:13)(cid:9)(cid:14)(cid:14)(cid:6)(cid:6)(cid:9)(cid:14)(cid:10)(cid:12)1(cid:4)(cid:34)46
`
`7
`
`

`
`480
`
`M. Mitzenmacher
`
`We begin by focusing on the case where the number of balls n equals the number of
`bins n, and consider the limiting description given by the di↵erential equations as n ! 1.
`
`Lemma 2.2. For the family of di↵erential equations given by (2.6), si(1) 6 [si1(1)]d.
`
`Proof. We wish to know the values of si(1). Because the si are all non-decreasing over
`time and nonnegative, from (2.6),
`
`dsi
`dt
`for all t 6 1 and hence by integrating
`
`
`
`
`
`i1 sd= sd i 6 [si1(1)d]
`
`si(1) 6 [si1(1)]d.
`
`(2.7)
`
`One can calculate s1(1) directly from Theorem 2.2, and it follows from a simple induction
`on (2.7) that
`
`si(1) 6 [s1(1)]di1
`
`.
`
`In other words, the si(1), which represent the limiting fraction of bins with load at least
`i after all balls have been thrown, decrease doubly exponentially, as the i is in the second
`level of the exponent. Using Kurtz’s theorem one obtains a high probability result for the
`case of a finite number of balls n.
`
`Theorem 2.5. Let wn
`i be the fraction of bins with load at least i when n balls are thrown
`i 6 (1 + ✏)[s1(1)]di1 with
`and fixed i, wn
`into n bins using greedy(d). Then, for any ✏>0
`probability at least 1 ec(log i)n✏2 for some suitable constant c.
`
`Proof. The proof is a direct application of Kurtz’s theorem, using the appropriate error
`bounds.
`
`This doubly exponential decrease in the si(1) (or, equivalently, of the wn
`i ) is a key step of
`the proof of Azar, Broder, Karlin and Upfal in [1], where it is proved via an inductive use
`of Cherno↵ bounds. Theorem 2.5 shows that this induction can be replaced by applying
`Kurtz’s theorem to the di↵erential equations, at least up to any fixed constant value of i.
`This approach has some advantages. Most importantly, Lemma 2.2 and the corresponding
`inductive bound for si(1) seem quite natural and make transparent how the si decrease.
`Additionally, using this approach can improve the additive O(1) term in Theorem 4 of
`[1].
`Intuitively, this doubly exponential decrease suggests that, if we look at bins with load
`
`.(cid:33)(cid:40)(cid:32)(cid:30)(cid:33)1454(cid:1)6(cid:35)(cid:33)(cid:31)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:4)(cid:1)-(cid:33)(cid:34)(cid:41)(cid:35)9(cid:26)8(cid:37)(cid:1)-(cid:30)51(cid:35)1(cid:32)35(cid:1)-5(cid:32)(cid:37)5(cid:35)(cid:1)-C(cid:36)(cid:37)(cid:33)(cid:31)5(cid:35)(cid:1)05(cid:35)D935(cid:2)(cid:1)(cid:33)(cid:32)(cid:1)(cid:7)(cid:10)(cid:1)/(cid:33)D(cid:1)(cid:8)(cid:6)(cid:7)(cid:12)(cid:1)1(cid:37)(cid:1)(cid:8)(cid:6),(cid:11)(cid:8),(cid:6)(cid:7)(cid:2)(cid:1)(cid:36)C2:53(cid:37)(cid:1)(cid:37)(cid:33)(cid:1)(cid:37)85(cid:1)-1(cid:31)2(cid:35)94(cid:26)5(cid:1)-(cid:33)(cid:35)5(cid:1)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:1)(cid:33)6(cid:1)C(cid:36)5(cid:2)(cid:1)1D19(cid:30)12(cid:30)5(cid:1)1(cid:37)
`8(cid:37)(cid:37)(cid:34),(cid:5)(cid:40)(cid:40)(cid:40)(cid:4)31(cid:31)2(cid:35)94(cid:26)5(cid:4)(cid:33)(cid:35)(cid:26)(cid:5)3(cid:33)(cid:35)5(cid:5)(cid:37)5(cid:35)(cid:31)(cid:36)(cid:4)(cid:1)8(cid:37)(cid:37)(cid:34),(cid:5)(cid:5)3(cid:33)(cid:32)(ci