{'fraction_non_alphanumeric': 0.05310374043709038, 'fraction_numerical': 0.011126616661267413, 'mean_word_length': 3.9277951740652055, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 83, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Large deviation asymptotics for occupancy problems

In the standard formulation of the occupancy problem one considers the distribution of r balls in n cells, with each ball assigned independently to a given cell with probability 1/n. Although closed form expressions can be given for the distribution of various interesting quantities (such as the fraction of cells that contain a given number of balls), these expressions are often of limited practical use. Approximations provide an attractive alternative, and in the present paper we consider a large deviation approximation as r and n tend to infinity. In order to analyze the problem we first consider a dynamical model, where the balls are placed in the cells sequentially and ``time'' corresponds to the number of balls that have already been thrown. A complete large deviation analysis of this ``process level'' problem is carried out, and the rate function for the original problem is then obtained via the contraction principle. The variational problem that characterizes this rate function is analyzed, and a fairly complete and explicit solution is obtained. The minimizing trajectories and minimal cost are identified up to two constants, and the constants are characterized as the unique solution to an elementary fixed point problem. These results are then used to solve a number of interesting problems, including an overflow problem and the partial coupon collector's problem.

1. Introduction. Urn occupancy problems center on the distribution of r balls in n cells, typically with each ball independently assigned to a given cell with probability 1/n. The literature on the general topic is enormous. See, for example, [9,19,20] and the references therein. There are many different questions one can pose. For example, it may be that one is interested in the distribution of (Γ 0 , Γ 1 , . . . ), where Γ i is the number of cells containing exactly i balls after all r balls have been thrown. In the classical occupancy problem [9,14,20], one is interested only in the distribution of unoccupied urns Γ 0 . In other cases, one might be interested in the (random) number of balls required to fill all cells to a given level, or the number required so that a given fraction are filled to that level-the so called coupon collector's or dixie cup problem. In biology the inverse problem of estimating the number of balls thrown from the number of occupied cells also arises and is used to estimate species abundance [17]. Related applications in biology appear in [2,3], and an application in computer science appears in [21].
Another related problem of interest is the overflow problem, in which the urns are supposed to have a finite capacity C, and the number of balls that overflow is the random variable of interest. Ramakrishna and Mukhopadhyay [24] describes an application in computer science concerned with memory access, and [12] considers an application to optical switches. In [12] one is concerned with dimensioning the number of wavelength converters so as to reduce the probability of packet loss across the switch to an acceptable level. In [12] any-color-to-any-color converters are considered. However, by extending the results proved here to the case where the balls have distinct colors, dimensioning in the case where we have many-to-one color converters can be carried out and the blocking probability of the output estimated.
A wide range of results have been proved for the occupancy problem by using "exact" approaches. For example, combinatorial methods are used in [9,14,20], and methods that utilize generating functions are discussed in [20]. The implementation of these results, however, can be difficult. For example, in applying the combinatorial results one must compute the difference between large quantities that appear in the inclusion-exclusion formula for the probability that a given fraction of cells are occupied. An analogous difficulty occurs with techniques based on moment generating functions, since one must invert the generating function itself.
Asymptotic methods provide an attractive alternative to both of these approaches. One reason is that they often offer good approximations with only a modest computational effort. A second, perhaps more important reason, is that superior qualitative insights can often be obtained. Indeed, a range of asymptotic results have already been obtained for these problems (see, e.g., [18]). The first large deviations principle (LDP) for urn problems that we are aware of was established in [28] for the special case of the classical occupancy problem. This result was applied in [21] to a boolean satisfiability problem in computer science. Reference [6], which appeared while the present paper was under review, proves a LDP for the infinite-dimensional occupancy measures associated with occupancy processes. The present paper LARGE DEVIATION FOR OCCUPANCY PROBLEMS 3 focuses on finite-dimensional occupancy measures in which urn occupancies above a given level are not distinguished. In this finite case, we are able to provide a concise large deviations proof along with explicit, insightful and computable expressions for the rate functions and for the large deviations extremals. The rate function for the occupancy model after all the balls have been thrown is shown to have a simple and fairly explicit rate function, which can be defined in terms of relative entropy with respect to the Poisson distribution. Many different problems can be solved in this framework simply by changing the set over which the rate function is minimized. We also give sample path results for the evolution of the urn occupancies toward a particular event. In principle, the explicit form of the minimizing trajectories for sample path results should enable accurate empirical estimates of unlikely events using importance sampling; see [7,22].
Let ⌊a⌋ denote the integer part of a scalar a. With n cells available and a total of r = ⌊βn⌋ balls to be thrown (with β > 0), we consider the large deviation asymptotics as n → ∞. The precise statement is as follows. Fix a positive integer I. Then with Γ n i (β) equal to the fraction of cells containing i balls, we characterize the large deviation asymptotics of the random vectors {(Γ n 0 (β), Γ n 1 (β), . . . , Γ n I (β)), n = 1, 2, . . . } as n → ∞. A direct analysis of this problem is difficult, and, in fact, it turns out to be simpler to first "lift" the problem to the level of a sample path large deviation problem, and then use the contraction principle to reduce to the original finite-dimensional problem. A "time" variable x is introduced into the problem, where ⌊nx⌋ balls have been thrown at time x, and Γ n i (x) is equal to the fraction of cells containing i balls at this time. We then follow a standard program: the large deviation properties of this Markov process are analyzed, the rate function J on path space is obtained, and the rate function for the occupancy at time β is then characterized as the solution to a variational problem involving J .
Although the program is standard, there are several very interesting features, both qualitative and technical, which distinguish this large deviation problem. We first describe some of the attractive qualitative features. Typically, one has a rate function on path space of the form J(φ) = L(φ(x),φ(x)) dx, where the nonnegative function L(γ, ξ) is jointly lower semi-continuous and convex in ξ for each fixed γ. The large deviation properties of the process at time β are then found by solving a variational problem of the form where ω is given and where there will also be constraints on the initial condition φ(0). In general, this problem does not have an explicit, closed form solution. One exception to this rule is the extraordinarily simple situation where L(γ, ξ) does not depend on the state variable γ. In this case, Jensen's inequality implies that the minimizing trajectory is a straight line, and so the variational problem is actually finite dimensional. Another exception is the case of large deviation asymptotics of a small noise linear stochastic differential equation. In this case the variational problem takes the form of the classical linear quadratic regulator, and the explicit solution is well known from the theory of deterministic optimal control. However, in this case there is no need to "lift" the problem to the sample path level, since the distribution of the diffusion at any time is Gaussian with explicitly calculable mean and covariance. Other exceptions occur in large deviation problems from queuing theory, but in these problems the variational integrand is "sectionally" independent of γ, and one can show that the minimizing trajectories are the concatenation of a finite number of straight line segments (see, e.g., [1] and the references therein).
For the occupancy problem the variational integrand has a complicated state dependence [see (2.2)], reflecting the complicated dependence of the transition probabilities (in the process level version) on the state. Nonetheless, the rate function possesses a great deal of structure that can be heavily exploited. For example, the function J turns out to be strictly convex on path space, and so all local minimizers in the variational problem are actually global minimizers. Perhaps even more surprising is the fact that explicit solutions to the Euler-Lagrange equations can be constructed, and as a consequence, the variational problem can be more-or-less solved explicitly (see the Appendix). Both of these properties follow from the fact that the variational integrand L can be defined in terms of the famous relative entropy function (or divergence).
A technical novelty of the problem is the singular behavior of the transition probabilities of the underlying Markov process. Since only cells containing j balls can become cells with j + 1, it is clear that the transition probability corresponding to such an event scales linearly with Γ n j (x), and in particular, that it vanishes at the boundary of the state space, when Γ n j (x) = 0. This poses no difficulty for the large deviations upper bound, but is an obstacle for the lower bound. (Some results that address lower bounds when rates go to zero include Chapter 8 of [26], which treats processes with "flat" boundaries, and recent general results in [27].) For the occupancy model, existing results provide a lower bound for open sets of trajectories that do not touch the boundary, because away from the boundaries the set {ξ : L(Γ, ξ) < ∞} is independent of Γ. To deal with more general open sets we use a perturbation argument. We first show, using the strict convexity of J and properties of the zero cost paths, that it is enough to prove large deviation lower bounds for open neighborhoods of trajectories that stay away from the boundary for all positive times. (Note that this still allows the trajectory to start on the boundary.) Loosely speaking, to prove the lower bound for sets of this type it is enough to show that given a > 0, there is b > 0 such that the probability that the process is at least distance b from the boundary by time b is bounded below by exp −na. It turns out that these bounds can be easily established by exploiting an explicit representation for such probabilities that was proved in [11].
An outline of the paper is as follows. Section 2 states the main results of the paper. In the first part of Section 2 we construct the underlying stochastic process model, and state the corresponding sample path level LDP, as well as the LDP for the terminal distribution. The proof of the sample path LDP is given in the following section, although in Section 2 an additional heuristic argument for the form of the local rate function based on Sanov's theorem is provided. In the second part of Section 2, the terminal distribution rate function is characterized and explicit expressions for the sample path minimizers are presented. These constitute more-or-less complete solutions to the corresponding calculus of variations problem. The detailed proofs of these latter results are deferred to the Appendix. Section 3 gives a proof of the sample path LDP. The solutions to the variational problem are exemplified in Section 4, where we show how specific questions regarding the occupancy problem can be answered. In particular, we work out the asymptotics for a number of examples, including an overflow problem and a partial coupon collection problem. Generalizations to our results are also described.

Main results.
2.1. Statement of the LDP. In this section we formulate the problem of interest and state the LDP. The proof will be given in Section 3. As noted in the Introduction, our focus is the asymptotic behavior of the occupancy problem. If n denotes the total number of cells, then to have a nontrivial limit, the number of balls placed in the cells should scale linearly with n. We will place ⌊βn⌋ balls in the cells, where β ∈ (0, ∞) is a fixed parameter and ⌊a⌋ denotes the integer part of a.
As will be seen in the sequel, the large deviation asymptotics of the occupancy should be treated by first lifting the problem to the level of sample path large deviations, and then using the contraction principle to reduce to the original problem. To do this, we introduce a "time" variable x that ranges from 0 to β. At time x, one should imagine that ⌊nx⌋ balls have been thrown. Thus, the occupancy process will be piecewise constant over intervals of the form [i/n, i/n + 1/n). With this scaling of time, large deviation asymptotics can be obtained if we scale space by a factor of 1/n. Thus, we define the random occupancy process Γ n (x) . = (Γ n 0 (x), . . . , Γ n I (x), Γ n I+ (x)) by letting Γ n i (x), i = 0, . . . , I denote 1/n times the number of cells with exactly i balls at time x, and letting Γ n I+ (x) be 1/n times the number of cells with more than I 6 P. DUPUIS, C. NUZMAN AND P. WHITING balls at time x. Note that Γ n takes values in the set of probability vectors on I + 2 points: S I . = {γ ∈ R I+2 : γ j ≥ 0, 0 ≤ j ≤ I + 1 and I+1 j=0 γ j = 1}. The process {Γ n (i/n), i = 0, 1, . . .} is obviously Markovian. It will be convenient to work with the following "dynamical system" representation: where the independent and identically distributed random vector fields {b i (·), Here e j represents the vector in R I+2 whose jth element is unity and for which all other elements are zero. The occupancy after ⌊βn⌋ balls have been thrown can then be represented by nΓ n (β).
As we have discussed, the large deviations behavior of Γ n (β) will be deduced from that of the process Γ n (·). In order to state the large deviation asymptotics precisely, we should clarify the space in which Γ n (·) takes values and the topology used on that space. As usual for processes with jumps of this sort, we use the Skorokhod space D([0, β] : R I+2 ) together with the Skorokhod topology [5], Chapter 4. However, the large deviations properties of {Γ n } are the same as for the processes {Γ n }, whereΓ n is defined to be the piecewise linear process which agrees with Γ n at times of the form i/n. For readers unfamiliar with the Skorokhod space and associated topology, the identical large deviations results hold forΓ n , save that the space of continuous functions and the sup norm topology are used instead.
To complete the statement of the LDP for {Γ n } we need some additional notation. A vector of (deterministic) occupancy rates θ(x) = (θ 0 (x), . . . , θ I (x),θ I+ (x)) is a measurable mapping from [0, β] to S I . Intuitively these rates represent the rate at which balls flow into urns of a given occupancy level. Associated with each such vector of rates is the corresponding deterministic occupancy function γ(x) = (γ 0 (x), . . . , γ I (x), γ I+ (x)), which is defined by the initial condition γ(0) and the differential equationsγ . These equations reflect the idea that the fraction of urns containing i balls increases as balls enter (i − 1)-occupied urns, and decreases as balls enter i-occupied urns. Defining the matrix Conversely, given a differentiable occupancy function γ, the corresponding rates are uniquely determined byγ(x) = M θ(x) and the normalization I i=0 θ i (x) + θ I+ (x) = 1. We will also be interested in the cumulative occupancy function ψ with components ψ i (x) = i j=0 γ i (x). Inspecting the cumulative sums of the rows of M shows thatψ i = −θ i for i = 0, . . . , I. As more balls are thrown, the fraction of urns containing i or fewer balls can only decrease, and the rate of decrease is the rate at which balls enter i-occupied urns. We will say that γ is a valid occupancy function if γ is absolutely continuous, if γ(x) is a probability vector for all x ∈ [0, β], and if its associated θ(x) is a probability vector for almost all x ∈ [0, β]. Note that the functions ψ, γ and θ are interchangeable, in the sense that each can be derived from any of the others [given γ(0) in the case of θ]. Thus, we say that θ and ψ are valid if the associated γ is valid. The following lemma gives a direct characterization of validity in terms of ψ.
Sketch of the proof. In the forward direction, the first condition plus the bound ψ I (x) ≤ 1 ensure that γ(x) is a probability distribution. The second and third conditions together imply that ψ is Lipschitz continuous with constant 1 and, hence, absolutely continuous. This implies the absolute continuity of γ. Sinceψ = −θ, the third condition ensures that θ is almost always a probability distribution. The reverse direction proceeds similarly.
Given γ, θ ∈ S I , let D(θ γ) denote relative entropy of θ with respect to γ. Thus, with the understanding that θ i log(θ i /γ i ) . = 0 whenever θ i = 0, and that is a valid occupancy function with corresponding occupancy rates θ(x), then we set In all other cases set J(γ) = ∞. and, moreover, for any compact set of initial conditions K and C < ∞, the set The proof of this result is provided in Section 3. However, a formal justification for the form of the rate function is as follows. Let δ > 0 be a small time increment. Owing to the fact that Γ n varies slowly when compared to {b i (γ)}, one expects where the symbol "≈" inside the probability means that the indicated quantities are within a small fixed constant ε > 0 of each other. Suppose that we interpret γ as a probability measure on {e 0 , . . . , e I+1 }, and let {Y j } be independent and identically distributed (i.i.d.) with distribution γ. Then the sequence of i.i.d. random vectors {b j (γ)} can be realized by setting By Sanov's theorem, for any probability vector θ ∈ S I , Thus, Approximating an arbitrary trajectory by a piecewise linear trajectory with nearly equal cost and using the Markov property, one expects where θ and γ are related byγ = M θ, γ(0) = α. Thus, the rate function on path space should be J(γ).
The zero cost trajectories are of course the law of large numbers limits, and can easily be computed. For example, if α = (1, 0, . . . ) (so all cells are initially empty) and i ≤ I, then J(γ) = 0 implies that γ i (t) = e −t t i /i!. In other words, γ(t) is the Poisson distribution with mean t, save that all mass corresponding to i > I is collected together into the state I + 1. Throughout this paper we will denote the Poisson distribution with mean t by P(t), We are primarily interested in the distribution of Γ n (β). The contraction principle (e.g., [11], Theorem 1.3.2) implies the following variational representation for the rate function for {Γ n (β), n = 1, 2, . . .}. Let A(α, ω, β) denote the set of valid occupancy paths γ on [0, β] satisfying γ(0) = α and γ(β) = ω. Remark 2.1. Using the explicit formula for J (ω) stated in Theorem 2.7 and the convexity of relative entropy in its first argument, it follows that J is, in fact, strictly convex.

Remark 2.2.
It is sometimes useful to show that the large deviation lower bound holds for sets with no interior relative to the ambient space. Such bounds can often be proved for processes, such as ours, that take values in a discrete lattice. An example would be a set A ⊂ {γ ∈ S I : γ I+ = 0}, for which the minimizing trajectories must be polynomial extremals (defined after Theorem 2.6). Although we do not need such results in the present paper, it is worth observing that lower bounds of this kind can be proved.

Characterization of the terminal rate function and minimizing paths.
The results of this section were obtained using calculus of variations techniques, the details of which are given in the Appendix. The presentation begins with the case in which all urns are initially empty because it appears in many applications and because it is a building block for the general case. In each case, first we give a characterization of J (ω) as a minimal relative entropy, which may be computed explicitly in this form. We then give an explicit functional form for the sample path minimizer. The function form constain parameters determined by the solutions to fixed point equations.
Before stating these theorems, it is helpful to specify the domain over which J (ω) is finite. We define an endpoint constraint to be a triple (α, ω, β), where α, ω ∈ S I are the initial and terminal occupancies, and where β > 0 is the number of balls thrown per urn. We assume without loss that α 0 > 0, that is, that some fraction of urns are initially empty, and we denote the index set of positive initial occupancies by K = {k : α k > 0}. Since we do not distinguish between urns having more than I balls, we can always suppose that no urns initially have more than I + 1 balls, and denote the last element of α by α I+1 . The last element of ω is denoted ω I+ , signifying that it collects all urns with occupancy greater than or equal to I + 1.  This lemma is proved in the Appendix. Condition (2.3) relates to the fact that the ψ i (x) must decrease monotonically and (2.4) to a conservation constraint for the number of balls thrown. The right-hand side of the inequality equals the initial number of balls per urn, plus the additional balls per urn thrown up to time β, while the left-hand side is a lower bound on the number of balls per urn at time β.
In the treatment of general initial conditions, the following further definition will be useful. For a reducible set of constraints, let i be the first index such that i k=0 α k = i k=0 ω k . This condition can only be met if no balls are ever thrown into i-occupied urns, and it follows that urns which initially contain i balls or less will always contain i balls or less. Thus, these urns may be treated in isolation from the urns containing more than i balls. Furthermore, by subtracting i + 1 balls from each urn in this latter set, we obtain another occupancy problem in standard form, that is, with α 0 > 0. Continuing in this way, a given problem with constraints (α, ω, β) may be divided into a finite number of isolated, irreducible subproblems. It is only necessary therefore to treat problems with irreducible constraints, and wherever necessary we suppose this to be the case.
2.2.1. Empty initial conditions. An important special case of the initial constraint is when all urns are initially empty, that is, α 0 = 1 and α i = 0 for i > 0. We abuse notation and denote this case by α = 1.
Define the set F (1, ω, β) to be the set of distributions π on the nonnegative integers satisfying π i = ω i for i = 0, . . . , I and the constraint In the empty case, the conditions for feasibility of (1, ω, β) reduce to I i=0 iω i + (I + 1)ω I+ ≤ β, from which it follows that the set F is nonempty if and only if (1, ω, β) is feasible. As we now discuss, the infimum of the rate function J over paths A(1, ω, β) can be represented as an infimum of a relative entropy over distributions in F (1, ω, β). Theorem 2.5 (Terminal rate function, empty case). Given the initial condition α = 1, the rate function J (ω) : S I → R + defined in Corollary 2.3 may be determined as if (1, ω, β) is feasible, and is otherwise infinite. The minimizing argument π * ∈ F (1, ω, β) is unique.
The above expression is of interest in its own right. Moreover, the optimal solution π * can be computed explicitly. Using Lagrange multipliers, one can show, in fact, that the solution takes the form π * i = CP i (ρβ) for i > I for some constants C ≥ 0 and ρ > 0 that we refer to as twist parameters.
Here ρ is related to the Lagrange multiplier for the conservation constraint ∞ i=0 iπ * i = β, while C is a normalization constant ensuring that ∞ i=0 π * i = 1. These two constraints may be solved to determine ρ and C. If we have the strict equality I i=0 iω i + (I + 1)ω I+ = β, there are just enough balls to meet the terminal constraints and we may replace I by I + 1 if necessary to ensure that ω I+ = 1 − I i=0 ω i = 0. In this case, it turns out that F (1, ω, β) has only one element; we then have C = 0, and we may take ρ = 1. Otherwise, we define ρ to be the unique positive root of the equation Because of the strict inequality in the conservation condition (2.4), the righthand side of the last equation is strictly greater than I + 1. The left-hand side of the equation is the conditional mean E[Y | Y > I] of a Poisson random variable Y with mean ρβ. As a function of ρ, this conditional mean is a strictly monotonic and continuous map from (0, ∞) to (I + 1, ∞) and, hence, the equation has exactly one positive root. C is given by Evaluating the relative entropy of π * and P(β), the rate function of Γ n (β) can be expressed as The next theorem shows that the least cost path γ * satisfying J(γ * ) = J (ω) can also be expressed explicitly in terms of the twist parameters C and ρ. The least cost path is of interest for a number of reasons. First of all, the proof of Theorem 2.5 is obtained by evaluating (2.2), using the explicit form of γ * . In a similar way, the least cost paths may be used as a tool in other problems of interest, such as for determining the rate function of Γ n (β) when β is random. Second, the least cost path provides insight into the expected behavior of occupancy experiments, conditioned on the occurrence of a rare event. Third, they allow empirical estimation of rare event probabilities by change-of-measure importance sampling. A key step in proving the minimality of the proposed least cost path is to show that the path satisfies the Euler-Lagrange equations (defined in the Appendix).
Theorem 2.6 (Globally minimizing path, empty case). Suppose that (1,ω,β) are feasible constraints with empty initial conditions. The infimum of where ρ > 0 and C ≥ 0 are twist parameters associated with the constraints. In addition, γ satisfies the Euler-Lagrange equations.
Note that the entire path γ(x) is completely determined by the empty component γ 0 (x) and its derivatives. In particular, the components γ i (x) are the terms in the Taylor expansion of γ 0 (x) about x, γ 0 (x + y) = γ 0 (x) + yγ (1) 0 (x) + · · · evaluated at time 0, that is, with y = −x. Note that γ 0 (x) is the sum of a polynomial and a single exponential term, so that the Taylor expansion always exists. When C = 0, there is no exponential term, and we say that γ is a polynomial extremal. Otherwise, C > 0, we have an exponential extremal.

2.2.2.
General initial conditions. Occupancy problems with general initial conditions may be thought of as a coupled set of problems with empty initial conditions. In particular, we consider the set of urns initially containing k balls to form a class. The evolution of excess balls (beyond k) entering urns of this class may be denoted by occupancy functions of the form γ k,j (t) representing the fraction of balls initially having k urns which have k + j urns at time t. The fraction of urns containing i balls in the overall system is obtained by summing contributions from all subproblem components with k + j = i.
As in the empty case, the rate function J (ω) can be expressed as the solution to a minimization problem. Let S ∞ denote the set of distributions on the nonnegative integers, and let S n ∞ denote the set of n-tuples of such distributions. Recall that K is set of indices k such that α k > 0. We will denote an element of S |K| ∞ by π = {π (0) , . . . , π (k) , . . . , π (K) }, where for any k ∈ K a component distribution is denoted π (k) = {π k,0 , π k,1 , . . . }, and it is understood that the corresponding π (k) is omitted if α k = 0. Finally, let F (α, β, ω) be the set of π ∈ S |K| ∞ which satisfies the terminal constraints As in the empty case, it may be established that F is nonempty if and only if (α, ω, β) is feasible.
As discussed above, we may suppose the constraints are irreducible, and then, as shown in the Appendix, Lagrange multipliers will always exist for this problem. When we have strict inequality in the conservation condition (2.4) (the exponential case), the solution takes the form In the case of equality in (2.4) (the polynomial case), the corresponding form is As for empty initial conditions, ρ may be associated with the conservation condition. The W i correspond to the terminal constraints ω i , and the C k , D k are normalization constants. The constants C k , ρ, W i and D i can all be computed numerically using Lagrangian methods for constrained optimization (see, e.g., [4]). Given these constants, the optimizing trajectory γ(t) may be constructed explicitly. This construction may be most simply expressed in terms of the minimizing trajectories in the empty case. For k ∈ K, denote the mean of π * (k) by β k = ∞ j=0 jπ * k,j , and define the terminal condition ω (k) ∈ S I−k by ω k,j = π * k,j , for j = 0, . . . , I − k. Then the constraints (1, ω (k) , β k ) are feasible constraints, and Theorem 2.6 determines the associated least cost paths, which we denote γ (k) = {γ k,j (x)}. The least cost paths for the subproblems combine to form the overall least cost path.
In addition, γ satisfies the Euler-Lagrange equations.
3. Proof of Theorem 2.2. The purpose of this section is to prove the main large deviations result. We recall the processes and notation defined at the beginning of Section 2.
For ζ ∈ R I+2 and γ ∈ S I , definē where "·" denotes inner product. Since the support of b i (γ) is bounded uniformly in i and γ, there exists a function h : R → R such thatH(γ, ζ) ≤ h(|ζ|) for all ζ and γ. Also, since the distribution of b i (γ) is weakly continuous in γ,H(γ, ζ) is jointly continuous. It follows from [10], Theorem 4.1, that the sequence {Γ n , n = 1, 2, . . .} satisfies a large deviation upper bound with a rate functionJ , which we now define. LetL be the Legendre-Fenchel transform ofH(γ, ζ) in ζ: If γ(x), 0 ≤ x ≤ β is an absolutely continuous function that takes values in S I , thenJ If γ is not absolutely continuous, thenJ(γ) = ∞. ( [10] assumes that the vector fields b i (γ) are defined for all γ ∈ R I+2 . It is easy to check that we can extend the definition to this set with the boundH(γ, ζ) ≤ h(|ζ|) and the continuity ofH(γ, ζ) preserved. However, if the process Γ n starts in S I , then it stays in S I , and so the exact form of the extension has no effect on the rate function.) We recall the definition of the matrix M given in (2.1). To complete the proof of the upper bound we must show thatJ = J , where J is defined as in (2.2). This will hold if we can show thatL(γ, η) is finite only when η = M θ for a unique probability vector θ, and that in this casē It is well known thatL(γ, η) is finite if and only if η is in the convex hull of the support of b i (γ) (see, e.g., [11], Lemma 6.2.3(d)). Therefore if L(γ, η) < ∞, then η can be written as a convex combination of the form where θ j ≥ 0 and I j=0 θ j ≤ 1. Since the vectors {(e j+1 − e j ), j = 0, 1, . . . , I} are linearly independent, these values are unique. Setting θ I+1 = 1− I j=0 θ j , we have η = M θ for a unique probability vector θ. Now assume that η takes this form. Then Given any values µ 0 , . . . , µ I+1 , we can define ζ 0 , . . . , ζ I+1 recursively by ζ 0 = −µ I+1 and ζ j+1 − ζ j = µ j − µ I+1 . With these definitions, it is apparent that the last display is equal to According to the Donsker-Varadhan variational formula for relative entropy (e.g., [11], Lemma 1.4.3(a)), the last display equals D(θ γ), thereby completing the proof of the upper bound.
We turn now to the proof of the lower bound. In this proof we will assume that γ 0 (0) > 0. Since γ 0 is always nonincreasing, γ 0 (0) = 0 implies that γ 0 (x) = 0 for all x and, therefore, under this condition the first component plays no significant role. A proof analogous to the one given below applies when γ 0 (0) = 0, where the role of γ 0 (0) here is played by the first positive component of γ(0).
As we have remarked, a source of difficulty is the singular behavior of the transition rates of the process when Γ n is near the boundary of S I . We first show that this can be avoided at all times save x = 0. To do this, we show that for any a > 0, there exist b > 0, K ∈ N and an occupancy function y such that y(0) = γ(0), sup 0≤x≤β |y(x) − γ(x)| < a, y j (x) > bx K for all j = 0, 1, . . . , I, I+ and 0 < x ≤ β, and such that Consider the zero cost trajectory defined bẏ We have the following expression for z j when j ≤ I: It is easy to check from this explicit formula that z j (x) >bx K for somē b > 0, K = I, and all j = 0, 1, . . . , I, I+ and 0 < x ≤ β. For ρ ∈ (0, 1), let y ρ = ρz + (1 − ρ)γ. Then y ρ is the occupancy function that corresponds to the rate ρz + (1 − ρ)θ. Using the joint convexity of relative entropy in both variables ( [11], Lemma 1.4.3(b)) and the fact that D(z z) = 0, we have All required properties are then obtained by letting y = y ρ for suitably small ρ ∈ (0, 1).
It follows that in proving the lower bound, we can assume without loss of generality that for some fixed constants b > 0 and K ∈ N, γ i (x) ≥ bx K for all x ∈ [0, β]. We now return to the proof of the lower bound. Our first objective is to show that the process can be moved into a small neighborhood of γ(τ ) (for τ > 0 small) with sufficiently high probability. Given τ ∈ (0, β], σ > 0, and ε > 0, define For n large enough that |γ(⌊nτ ⌋/n) − γ(τ )| ≤ σ/2 (and independent of τ ∈ (0, β]), we have the inequality We next exploit a representation for exponential integrals that will give us an explicit lower bound on the last quantity. Consider a processΓ n (x) constructed as follows. The process dynamics are of the same general structure as those of Γ n , save that b i (Γ n (i/n)) is replaced by a sequenceb n i : Furthermore, the distribution ofb n i is allowed to depend in any measurable way upon the set of values {Γ n (j/n), 0 ≤ j ≤ i}. Let µ γ denote the distribution of b i (γ), and (without explicitly exhibiting all the dependencies) letμ n i denote the (random) distribution ofb n i , given {Γ n (j/n), 0 ≤ j ≤ i}. We let E Γ n (0) denote expectation on the space that supports these processes. It follows from [11], Theorem 4.3.1, that where the infimum is over all such processesΓ n (x). In order to obtain a lower bound, we now simply insert a particular choice for the random variablesb n i . We can write γ(τ ) − γ(0) = M vτ for some probability vector v. Define a processb n i as follows: In other words,b n i defines a deterministic, discrete time approximation to the continuous time occupancy rate process that uses e 0 − e 1 for an amount of time v 0 τ , e 1 − e 2 for an amount of time v 1 τ and so on. This continuous time process will move the occupancy process from γ(0) to γ(τ ) at time τ . If e j − e j−1 is used at the discrete time step i, then sinceμ n i concentrates its mass on e j − e j−1 , the cost is The processΓ n (i/n) possesses important monotonicity and convergence properties. SinceΓ n j−1 ( as n → ∞ and η → 0. Furthermore, as observed previously, (3.2) implies the existence of b > 0 and K ∈ N such that γ j (τ ) ≥ bτ K for j = 0, . . . I. Thus, at any given time step i we have a strictly positive lower bound on the relevant component ofΓ n , which in turn provides a strictly finite upper bound on the corresponding relative entropy cost. Indeed, it follows from (3.3) and γ j (τ ) ≥ bτ K that for all sufficiently large n and small η > 0, there are C 1 , C 2 < ∞ (and independent of τ ) such that whenever |Γ n (0) − γ(0)| < η, for all i, In addition, as n → ∞ and η → 0, By the Lebesgue dominated convergence theorem, for all sufficiently large n and sufficiently small η > 0, We now choose τ > 0 so that −C 2 τ log τ ≤ ε/2. Choosing τ > 0 smaller if need be, we can also guarantee that |Γ n (x) − γ(x)| ≤ δ for all x ∈ [0, τ ] w.p.1 if |Γ n (0) − γ(0)| < η and η > 0 is sufficiently small. The following bound is therefore valid for the given τ > 0: for any σ > 0 and all sufficiently small Note that the asymptotic lower bound on the normalized log of the probability is independent of σ > 0. To obtain the lower bound for all x ∈ [0, β], we will use the Markov property and an existing lower bound for paths which avoid that boundary. This latter lower bound will hold uniformly in a neighborhood of the initial condition γ(τ ). Since we do not know a priori how small this neighborhood must be, it is important that the lower bound in the last display should be independent of σ > 0. Now choose ζ ∈ (0, δ] such that γ(x) is at least distance 2ζ from the boundary of S I for all x ∈ [τ, β]. Recall that when considered as a function of γ, the distribution of b i (γ) is continuous in the weak topology, and moreover that the support of this distribution is independent of γ so long as γ i > 0 for all i ∈ {0, 1, . . . , I + 1} (i.e., γ ∈ S • I , where S • I denotes interior relative to the smallest affine space that contains S I ). It then follows from Proposition 6.6.1 of [11] (see also the discussion on [11], page 165, regarding uniformity) that {Γ n , n = 1, 2, . . .} satisfies the following uniform large deviations lower bound: given any ε > 0 and ζ > 0 defined above, there is σ > 0 such that as long as |Γ n (⌊nτ ⌋/n) − γ(⌊nτ ⌋/n)| < σ, where P Γ n (⌊nτ ⌋/n),⌊nτ ⌋/n denotes probability given the occupancy levels Γ n (⌊nτ ⌋/n) at time ⌊nτ ⌋/n. Proposition 6.6.1 of [11] assumes Condition 6.3.2. It is worth noting that in the present setting this condition holds with the particularly simple choiceβ = γ (using the notation of [11]). The lower bound (3.1) now follows by the Markov property and the last two displays. The proof that J has compact level sets is as in [10], and therefore omitted.

Examples and extensions.
In this section we apply the results of the previous sections to three different occupancy problems. We show how the parameters of interest may be computed numerically and plot the solutions to the associated calculus of variations problems. In Section 4.4 we list some other asymptotic problems of interest which can be solved by relatively straightforward generalizations of the results presented in this paper.
In the calculus of variations problems solved in Section 2, precise initial and terminal points were always given. In typical applications, one is interested in the minimum value of the rate function over a constraint set. When the constraint set is sufficiently simple, such problems may still be solved easily using the tools provided in Section 2.2. The three problems of this section are of this type.
Suppose that the event of interest is that the random endpoint Γ n (β) should lie in a terminal constraint set Ω. To apply the LDP for {Γ n (β)} established by Corollary 2.3, one must compute exponents of the form Using Theorem 2.7, we can write where we have abused notation to define F (α, Ω, β) = ω∈Ω F (α, ω, β). In many cases, for example, when the terminal set Ω is convex and defined by linear constraints, the exponent J can be computed directly from (4.1) using Lagrange multipliers. That is, one solves minimization problems of the type given in Theorem 2.7, but with the endpoint constraints (2.10) replaced by constraints defining Ω. This is the approach used in the second and third example below. We do not prove that appropriate Lagrange multipliers always exist; if needed, existence may be established using methods similar to those used in the Appendix for the case Ω = {ω}. Because of the convexity of relative entropy in (4.1), a local minimum is always a global minimum over convex sets. Hence, in any particular scenario with convex Ω, it is sufficient to establish a local minimum by numerically computing a set of Lagrange multipliers.
An alternative approach for computing J (Ω) could be to return to the sample path level and use natural boundary conditions on the extremal curves (see [25]).
A set Ω with interior Ω • and closureΩ is a J -continuity set if and only if inf ω∈Ω • J (ω) = inf ω∈Ω J (ω). For such sets the large deviations lower and upper bounds coincide so that − lim 1/n log P (Γ n (β) ∈ Ω) = inf ω∈Ω J (ω). It may readily be verified in each of the following examples that the event of interest is a J -continuity set.
4.1. The classical occupancy problem. In the classical occupancy problem, the urns are initially empty and one only distinguishes between empty and occupied urns, or in other words, I = 0. The associated large deviations problem was solved using a sample path approach in [28]; we show here how this case may be obtained with our results. We might be interested in the probability of having an unusually large number of empty urns Γ n 0 (β) > ω 0 > e −β , or an unusually small number of empty urns Γ n 0 (β) < ω 0 < e −β . In either case, the calculus of variation problem is that in which γ 0 (β) = ω 0 . From (2.6), it is immediate that C = 1/ρ and Using (2.5), we find that ρ is determined by the unique nonnegative solution to Finally, (2.7) provides a simple expression for J (ω) in terms of ω 0 , β, C and ρ.

23
In addition, our analysis gives the sample paths for the higher occupancies, conditioned on an unusual number of empty urns, namely, γ i (x) = P i (ρx)/ρ for i > 0. Figure 1 depicts the first five occupancy levels as a function of balls per urn thrown x. In this example, the terminal fraction of empty urns ω 0 = 0.15 is three times larger than the expected value P 0 (3.0) = 0.05.

4.2.
The overflow problem. In the overflow problem an urn is considered full when it reaches a finite capacity I > 0. Once an urn has been filled, successive balls thrown to that urn fall to the floor. For specificity, we consider the problem of determining the probability that an unusually large number of balls end up on the floor, and assume the empty initial conditions α 0 = 1.
The problem can be handled using urns of infinite capacity in the following way. The number of balls that would have fallen on the floor in a finite capacity system is the number of balls in urns with occupancy greater than I, minus I times the number of such urns. When r balls have been thrown, the random number of overflowing balls w(r) is thus In order to compute we therefore consider sample paths which satisfy the end constraint Note that ζ can be interpreted as the average spare capacity per urn, which must satisfy the bounds [I − β] + ≤ ζ < I, and that the average overflow satisfies [β − I] + ≤ η < β. Assuming that η (and ζ) is larger than would be expected in the zero cost case, the minimum large deviations exponent will be achieved with equality in the constraint (4.2). Assuming that η > 0, we are in the exponential case, and the large deviations exponent J O (η, β) will be given by minimizing the divergence between π and P(β), under the linear equality constraints with Lagrange multipliers y, z and λ. On differentiating, it follows that the minimizing distribution π * should satisfy the conditions log π * i = log P i (β) − 1 + y + iz + (I − i) + λ. In terms of variables C, ρ and ν, we may write The distribution is conditionally Poisson ρβ/ν for i ≤ I and conditionally Poisson ρβ for i ≥ I. For convenience, we introduce the notation Since π * must satisfy the three linear constraints (4.3), the constants C, ρ and ν must solve the equations There can be at most one positive triple (C, ρ, ν) satisfying these equations, since each such triple identifies a local minimum of D(π P(β)) for π in a convex set, and there can be only one such minimum. The equations can be solved numerically in a number of ways to obtain C, ρ and ν. For example, from the first constraint, C can be expressed C = (R I + Q I ) −1 . Substituting this expression into the second and third constraints, we obtain the equations Each equation implicitly defines a curve ν as a function of ρ, and the intersection of the two curves gives the desired (ρ, ν). We note that larger than expected values of ζ will lead to ν > ρ > 1, while smaller than expected values of ζ give ν < ρ < 1.
The large deviations exponent for the overflow problem may then be expressed

4.3.
Partial coupon collection, with initial conditions. In the coupon collector's problem, the urns represent the n types of coupons that are required to form a complete collection. The placement of a ball in a given urn corresponds to choosing a new coupon at random, and the problem is to see how many coupons must be collected before I + 1 complete sets are obtained. This event corresponds to the constraint ω i = 0, i ≤ I.
In this section we solve a generalization of this problem. Beginning from nonempty initial conditions (a collection already in progress), we collect βn additional coupons with the goal of obtaining more than I coupons of as many types as possible. We want to determine how likely it is that number of types for which we have collected I or fewer coupons is less than ξn.
In terms of the urn problems we have considered, we are given initial occupancies α and wish to compute is an unusually small number of low occupancy urns.
The exponent J C will be given by computing J (ω) as defined in Theorem 2.7 subject to the conservation constraint (2.11), replacing the terminal where K ≤ I since any sets which are initially complete may be left out of the problem. After constructing a Lagrangian and differentiating, we find that the minimizing solution must be of the form As in the previous example, the unknown constants may be determined by substituting the given form of the solution into the constraint equations, and solving the resulting system of equations. In terms of these constants, the large deviations exponent may be expressed

Extensions.
There are a number of variations of the basic occupancy problem which can be solved by fairly straightforward generalizations of the results of this paper, but which we will only mention briefly. These include the following problems: (i) a random number of balls are thrown, (ii) balls have a probability p of not entering any urn, (iii) balls enter different subsets of urns with differing probabilities, (iv) an event of interest may occur at any time in the interval (0, β], rather than just at time β.
Some comments are in order. A particular example of (i) appeared in [13], where the number of balls thrown, r, was binomially distributed with parameters 0 < a < 1 and n. An urn model proposed by [16] is of type (ii). Here, the goal is to determine the distribution of the number of targets hit when r shots are fired at n targets, and when the probability of missing the target is p. In problem (iii) there are K > 1 urn classes with a fraction α k , k = 1, 2, . . . , K of urns in each class. Urns enter class k with a fixed probability p k but then enter any urn within that class with uniform probability. Similar analysis to that for nonempty initial conditions can be applied to this problem. For an example of type (iv), suppose that an infinite sequence of balls is thrown into n initially empty urns, and that one would like to know the probability that the number of urns containing exactly one ball ever exceeds n/2. The probability of this occurring after βn balls have been thrown can be bounded above by the probability that the number of empty and singly occupied urns exceeds n/2 when exactly βn balls have been thrown. This computation fits into the framework of a partial coupon collectors problem, and the probability can be made negligible from the point of view of large deviations by taking β sufficiently large. The remaining possibility, that the event occurs before βn balls have been thrown, is then a problem of type (iv). The associated calculus of variations problem is to find the lowest cost occupancy curve on (0, β] among all curves with γ 1 (x) > 0.5 for some x ∈ (0, β].

APPENDIX
Analysis of the calculus of variations problem. The Appendix is dedicated to proving the calculus of variations results given in Section 2.2. Recall that these results provide explicit representations for the terminal rate function J (ω) defined in Corollary 2.3, and for the minimizing occupancy functions γ * satisfying J (ω) = J(γ * ).
In the first step of the proof, we characterize a set of extremal occupancy paths, that is, paths which satisfy the Euler-Lagrange equations. For all feasible terminal conditions of the form (1, ω, β), Theorem A.1 shows that occupancy paths of the form given in Theorem 2.6 are extremals and that paths of this form can be constructed to meet any feasible constraints of the form (1, ω, β). Likewise, Lemma A.6 and Theorem A.11 show that occupancy paths of the form given in Theorem 2.8 are extremals, and such paths can be constructed to meet all general feasible conditions (α, ω, β). The special form of the extremals is used in Theorem A.5 and Theorem A.13 to show that the extremals have the costs given in Theorem 2.5 and Theorem 2.7, respectively. Ifγ is the extremal occupancy path constructed for given constraints (α, ω, β), we thus have the upper bound J (ω) ≤ J(γ). The assertion in Theorem 2.5 and Theorem 2.7 that the minimum relative entropy is achieved by a unique distribution π * is established in Lemma A.6. The final step needed to prove Theorems 2.5-2.8 is the lower bound J (ω) ≥ J(γ). This bound is proved in Theorem A.14, using the Euler-Lagrange equations together with properties of the relative entropy.
satisfy the constraints and the conditions of Lemma 2.1. Properties (a) and (b) are immediate, and property (c) will be established by showing that − I i=0ψ i ≤ 1. Indeed, −β I i=0ψ i is equal to the left-hand side of (A.6) and, therefore, − I i=0ψ i ≤ 1 follows from (A.5).
A.3. Euler-Lagrange equations. Given the numerous descriptions of occupancy processes and rates (ψ, γ, θ,γ,ψ, etc.), it is convenient to abuse notation. Thus, for example, we will write both J(γ) and J(ψ), with the understanding that the fundamental object of interest is the occupancy function γ, and that J(ψ) is merely J(γ) when ψ is the cumulative occupancy process that corresponds to γ. Also, sinceψ i = −θ i for i = 0, . . . , I, we can define the local rate function (which is usually written as a function of ψ anḋ ψ) as a function of ψ and θ, and represent the overall cost of a cumulative occupancy trajectory ψ as an integral of the form Because the balls are thrown uniformly and randomly into the urns, the expected rate for balls to enter urns of occupancy i is γ i = ψ i − ψ i−1 . As discussed in Section 2, the cost of a deviation of a given path ψ from its expected behavior at a given instant is given by the rate function The rate function is defined to be infinity if the curve is not a cumulative occupancy function. The calculus of variations problem is to find the path ψ having least cost among all paths satisfying given initial conditions and endpoint constraints, and to find the cost of such a minimal path. As illustrated in the examples in Section 4, the results extend to cases where the terminal point (or the initial point) are required to lie in a given constraint set.
Although the Euler-Lagrange equations are neither necessary nor sufficient conditions for minimality in general, extremals do turn out to be minimal in many cases. In the following sections we will construct a family of extremal paths for the cost function given above, and show that the extremal paths are, in fact, globally minimal.
In the case at hand, the Euler-Lagrange equations are given by for i = 0, . . . , I − 1, and by In the case when we have equality in the conservation constraint (2.4), and by taking I + 1 to be I if necessary, we have that I i=0 ω i = 1. Such cases of equality are referred to as the polynomial case. When this holds, every valid occupancy path must have ψ I (x) = 1 and, therefore, θ I (x) = θ I+ (x) = 0. For all such occupancy paths, the rate function L(ψ, θ) then reduces to The Euler-Lagrange equations pertinent to the problem of minimizing this restricted set of occupancy paths are just 10) for i = 0, . . . , I − 1.
A.4. Characterization of the extremals under empty initial conditions. In this section we consider the simplest and most important case, in which the urns are all initially empty, α 0 = 1. Recall that to each feasible endpoint constraint, (1, ω, β) correspond to twist parameters C ≥ 0, ρ > 0 which satisfy the equations Theorem A.1. Suppose that (1, ω, β) are feasible terminal constraints, and that ρ and C are the corresponding twist parameters. Then the set of functions γ defined by are extremals on [0, β] which satisfy the terminal constraints along with the initial constraint ψ 0 (0) = 1.
Recall that in the special case C = 0, the first component of the extremal is simply the Ith order polynomial We refer to such paths as polynomial extremals, and to extremals with C > 0 as exponential extremals.
The following definition and lemma are useful in the proof of the above theorem. This definition is based on the one pertaining to Bernstein's theorem, which characterizes Laplace transforms, see [15]. However, our definition differs in that it considers only a finite interval [a, b]. Proof. Clearly, ψ 0 (x) is infinitely differentiable. Now suppose first that In the polynomial case C = 0 the argument proceeds similarly on noting that Proof of Theorem A.1. The terminal constraints can be verified immediately by inspection. The initial constraints follow from the construction of C in (2.6), since
To establish that the given functions are valid occupancy curves, it is useful to introduce the infinite sequence of functions γ i and corresponding ψ i obtained by extending (A.9) to all i: As the sum of an exponential and a polynomial, ψ 0 has a Taylor series representation of unlimited radius about any point x.
Since, by Lemma A.2, the γ i are nonnegative on [0, β], we have {γ i (x)} ∈ S ∞ for all x in that interval. It follows from (A.13) that for all i ≥ 0, the rate of decrease of each cumulative occupancy is Forming the Taylor series representation of ψ  Finally, we must show that the given curves solve the Euler-Lagrange differential equations in (0, β). We begin with the exponential case C > 0. The I+ terms satisfy the simple expressions where the first display uses θ = −ψ and equations (A.12) and (A.14), and the second uses (A.12) and (A.13). Then the ratio θ I+ (x)/(1 − ψ I (x)) = ρ is constant, and the corresponding terms drop out of the right-hand side of (A.7) and (A.8).
From the expressions for γ i (x) andψ i (x) given in (A.13) and (A.14), it follows that A.5. Interpretation of the twist parameter ρ. For an exponential extremal the twist parameter ρ may be interpreted as follows. The expected rate for balls to enter urns with more than I balls is equal to the proportion of such urns, namely, 1 − ψ I . The twist parameter ρ is then a multiplicative factor applied to 1 − ψ I to give the actual rate at which balls enter these urns. Thus, if ρ > 1, balls unusually pile into high-occupancy urns, while if ρ < 1, they instead concentrate on the low-occupancy urns. The occupancy distribution of the high-occupancy urns remains Poisson but with a modified parameter.
The infinite sequence of occupancy functions introduced in the proof just given is a useful construct. Operations which are technically difficult in infinite dimensions may nevertheless be carried out formally on the infinite sequence of functions, giving insight in to the solution for the finitedimensional system. The next two lemmas compute the cost of extremal curves in a general form which will also apply to the nonempty case of the next section. The conditions of the lemmas are satisfied by the exponential and polynomial extremals of Theorem A.1, as can be readily verified.
Using our convention that ψ −1 (x) = 0, the integral on the right may be written as The above expression is valid as long as the left and right series in the first line converge. But this follows from the finite mean condition on {γ i }(x) since, for i > I, and similarly forψ i (x) log |ψ (i+1) 0 (x)|. Applying integration by parts and using (A.15) for each term of (A.18), the integral is The lemma follows on taking limits as ε ↓ 0.
A similar result holds in the case of the polynomial extremal.
for all x ∈ [0, β]. Then the cost J(γ) is given by Proof. The cost obtained by integrating the reduced cost function (A.9) from 0 to β, using the same substitutions and integration by parts as in the proof of Theorem A.3.
A.6. Characterization of the extremal cost. In the case of empty initial conditions, recall that the γ i defined in the proof of Theorem A.1 satisfy γ i (x) = x i |ψ  .19), we find that the cost J(γ) is simply the relative entropy D(γ(β) P(β)) between the γ i (β) and the Poisson, zero cost distribution. It turns out that the given γ i (β) minimize the relative entropy, among all distributions for which the first I + 1 elements are determined by ω, and which have mean β. Denoting the set of all such distributions by F (1, ω, β), we may prove Theorem 2.5, which we restate here.
Proof. We first solve the minimization problem, and then relate the problem to J(γ). The result is trivially true for polynomial extremals, since then F (1, ω, β) has only one element. In the case of an exponential extremal, the given minimization problem can be solved using Lagrange multipliers, which turn out to be simple functions of the twist parameters ρ and C > 0 associated with the given endpoint constraints. We consider the set of nonnegative sequences {π j } ∞ j=0 ∈ R ∞ + satisfying π i = ω i for i = 0, . . . , I, and define the Lagrangian L on this set to be where z . = log ρ and y .
where the latter are determined as in the proof of Theorem A.1 with the given C, ρ. For any i > I, the definitions of π * i , x and y and the strict convexity of x log x imply that π * i is the unique global minimizer of x → x log x − x[log P i (β) + y + iz]. Therefore, for any i > I and π i ∈ [0, ∞), = D(π * P(β)).
Since π * ∈ F (1, ω, β), it follows that π * , the terminal distribution, is the minimizer of the relative entropy. The uniqueness of π * follows from the strict convexity of the relative entropy with respect to its first argument. Substituting the particular form of π * i into (A.17), we have The cost for an exponential extremal can be written explicitly in terms of ρ, ω and β as where C is defined by (2.6). In the polynomial case, the cost is simply given by the first term in the above expression.
A.7. Characterization of the extremals under general initial conditions. We now generalize the solution to the Euler-Lagrange equations for the case when the urns are not all initially empty, but in which they may contain up to K balls. Recall that the fraction of urns having k balls initially is denoted α k , and the set of urn occupancies k with α k > 0 is denoted K. Without loss of generality, we may assume that some urns are initially empty (hence, 0 ∈ K) and we may take K = max K.
In the case K ≥ 1, we regard the urns as belonging to |K| classes, according to their initial occupancies. We denote the final number of additional balls per urn entering the kth class by β k , in which case the total number of additional balls per urn is β = k∈K α k β k . It turns out in the solution of the Euler-Lagrange equations that the fraction of balls entering the kth class in any time period is α k β k /β. After rescaling time by the factor β k /β, the evolution of additional balls entering each class of urns becomes an occupancy problem with initially empty conditions and terminal time β k .
We can thus define |K| occupancy curves γ (k) = {γ k,i } i , where the function γ k,i : [0, β k ] → [0, 1] represents the fraction of class k urns which contain i additional balls (thus, k + i total balls) after x balls per urn have been given to this class. The overall extremal occupancy curves for the general initial conditions are then given by We will see that the occupancy curve γ (k) for the kth subproblem is an extremal of the form given by Theorem A.1, with I − k terminal constraints. Given the appropriate subproblem terminal conditions (1, ω (k) , β k ), the results of the previous section determine the twist parameters C k and ρ k and corresponding extremals.
At this point we come to the main obstacle in determining the extremals for nonempty initial conditions. This is to show that there exist subproblem terminal conditions (1, ω (k) , β k ) which yield the extremal solution in the overall problem. To show that such conditions and the corresponding extremals exist, we will first give the form of the final cost function (which can be obtained by formal arguments). We then show that the cost function is the solution of a minimization problem, that the problem has a unique minimizing argument, that it has corresponding Lagrange multipliers, and that the extremal curves can be constructed using the Lagrange multipliers.
The large deviations exponent for the case of nonempty initial conditions α turns out to be Recall that S |K| ∞ is the set of all |K|-tuples of distributions {π (k) } k∈K , where each π (k) is a distribution on the nonnegative integers. It is straightforward to show that this problem is feasible whenever (α, ω, β) are feasible constraints, as we discuss in the proof of Lemma A.6. As in the empty case, each polynomial problem can be formulated in a standard way so that ω I+ = 0, in which case equality holds in the monotonicity condition I j=0 α j = I j=0 ω j = 1 as well as in the conservation condition (2.4). Unlike in the empty case, the minimization problem does not become trivial in the polynomial case since degrees of freedom remain in allocating balls among the |K| classes. In the polynomial case, the constraints imply that π k,j = 0, k + j > I (A.23) so that the minimization problem is finite dimensional. The polynomial problem can be stated equivalently as minimization of (A.20) subject to (A.23) and the endpoint constraints (A. 22), in which case the conservation constraint (A.21) need not be included explicitly.
As written, the vector of distributions π = (π (0) , . . . , π (k) , . . . , π (K) ) is such that k only ranges over indices with α k > 0. Including all indices 0 ≤ k ≤ K yields an equivalent problem in which the minimizing solution is not unique, since the π (k) with α k = 0 make no contribution to the objective function or the constraints. In the form given, however, the solution can be shown to be unique. Proof. Recall that F (α, ω, β) denotes the set of all distributions π ∈ S |K| ∞ satisfying the constraints (A.21) and (A.22). The feasibility of (α, ω, β) implies that F has at least one element. Moreover, it has at least one element with finite support and, thus, finite cost. A sketch argument for this point is as follows: First of all, any set of exponential constraints with terminal condition ω ∈ S I can be reformulated as a set of polynomial constraints with terminal conditionω ∈ SÎ , whereÎ > I. Any feasible point for constraints (α,ω, β) would also be feasible for the original constraints, and would have finite support. It remains to show that there is at least one feasible point for each set of feasible polynomial constraints. Such a feasible point may be constructed by an ordered filling construction. First, we assign π 0,0 = ω 0 /α 0 . The first monotonicity condition (i = 0) in (2.3) ensures that this is possible with less than or equal to unit mass. Next, some of the remaining mass from the distribution π (0) is applied to π 0,1 , and mass from π (1) is applied to π 1,0 as necessary until the constraint α 0 π 0,1 + α 1 π 1,0 = ω 1 is satisfied. That π (0) and π (1) have sufficient mass to do so follows from the (i = 1) condition in (2.3). This process continues until all constraints ω i have been satisfied. The equality in the conservation condition (2.4) implies that the final step uses up all of the probability mass in the distributions {π (k) }.
It will be useful to consider |K|-tuples of distributions in S ∞ under the topology of weak convergence, with the distance between distributions given by the Prohorov metric [5]. For two distributions P , Q in S ∞ , this distance is simply and the metric extends to |K|-tuples by treating them as elements of a product space. For each A < ∞, define the set The level sets of the relative entropy are compact under the above topology ( [11], Lemma 1.4.3), from which it follows that H A is also compact. For later reference, we note that a finite sum of relative entropy functions also inherits from the relative entropy the properties of lower semi-continuity and of strict convexity with respect to its first argument. As the next step in proving the lemma, we wish to show for some finite A that is compact and nonempty. This will enable us to find the minimum as a limit of a sequence of distributions in Q A .
Since there are solutions with finite cost, it is automatic that Q A (α, ω, β) is nonempty for large enough A. Since the set Q A is bounded, it is enough to verify for each convergent sequence of distributions π (n) ∈ Q A that the limiting distribution π lies in F (α, β, ω). (That it lies in H A is immediate since this set is compact.) The only difficulty lies in showing that the mean of the kth subdistribution π (k) is equal to the limit of the means of the π (n) (k) . This will be the case if we can show for any sequence in Q A and for an arbitrary k that the sequence π (n) (k) is uniformly integrable. In the present context, uniform integrability means that for each ε > 0, there is m < ∞ such that for all n and k. Since where by convention 0 log 0 = 0. Observe that this inequality is valid for all y and all x ≥ 0, and that x log x − x + 1 is nonnegative. We will also make use of the fact that the Poisson distribution has exponential moments: for any δ > 0, ∞ j=0 e 1/δj P j (β) = ∞ j=0 e 1/δj e −β β j j! = e βe 1/δ −β < ∞.
where the second equality uses the fact that both π (n) (k) and P(β) are probability distributions. Thus, (A.24) follows by first picking δ > 0 sufficiently small and then m < ∞ sufficiently large. [Note also for use in Corollary A.7 that the analogous result holds if β is replaced by a sequence β (n) → β ∈ (0, ∞)].
We now apply the uniform integrability to analyze the limits of the means. It follows from [5], Theorem 5.4, that so that π ∈ F (β, α, ω) and Q A is compact. We have shown that Q A is compact under the Prohorov metric and that it is nonempty. Now let Choose a sequence π (n) ∈ Q A such that K k=0 α k D(π (n) (k) P(β)) ≤ G + 1/n. Since Q A is compact this has a convergent subsequence, and to simplify the notation we index this subsequence by n. Let π * ∈ Q A be the limit point. Since relative entropy D(π η) is lower semi-continuous in π ( [11], Lemma 1.4.3(b)), it follows that where in fact we have equality by definition of G. The uniqueness of this minimizing vector of distributions follows from the strict convexity of the objective function.
Before continuing with the question of the existence of the extremals, we pause to obtain a corollary which will be useful in establishing the strong minimum in Theorem A.14. Define J (α, ω, β) to be the minimum cost in the problem (A.20) if the constraints are feasible, and ∞ otherwise.
We now turn to the existence of the Lagrange multipliers corresponding to the minimization problem (A.20). For a given vector ω, it will be helpful to define the set of integers I(ω), where i ∈ I(ω) if 0 ≤ i ≤ I and ω i > 0, or if i > I and ω I+ > 0. This is the set of terminal urn occupancy levels which the constraints do not force to be empty. As we will show, for irreducible constraints, the optimal {π k,j } with k + j ∈ I(ω) are always strictly positive. This result does not hold directly for reducible constraints, but as we discussed earlier, any problem with reducible constraints can be replaced by a finite number of subproblems with irreducible constraints. Then π * k,j > 0 for all k + j ∈ I(ω) and π * k,j = 0 if k + j / ∈ I(ω).
Proof. For k + j / ∈ I(ω), the constraints force the π k,j to be zero for all feasible points of the problem, and hence, for the minimizer in particular. The main point is to show that it is feasible for any other element to be positive, and the result will then follow from the infinite derivative of the objective function near the boundary.
Let π ∈ S |K| ∞ be any feasible solution meeting the given constraints, and suppose that π m,n = 0 for some particular (m, n) with m + n ∈ I(ω). Let π be an arbitrary set of probability distributions in S |K| ∞ subject to the restrictions thatπ m,n > 0, thatπ k,j = 0 for all k + j / ∈ I(ω), and thatπ has finite support. If we definẽ thenπ is a feasible solution for the constraints (α,ω,β). Next, for any η > 0, we may defineβ .
We may now letπ be a feasible point for (α,ω,β), and finally form π = ηπ + (1 − η)π. By construction,π is a feasible solution corresponding to the original constraints (α, ω, β), and, in addition,π m,n > 0. As discussed in the proof of Lemma A.6, we may takeπ to have finite support so thatπ also has finite support.
We will show that π is not a minimizer by proving that a sufficiently small perturbation towardπ reduces the objective function. Because the constraints are linear, the points π ε = επ + (1 − ε)π are feasible solutions to the original constraints for all 0 ≤ ε ≤ 1. Let f (ε) denote the value of the objective function evaluated at π ε . The derivative of this function is In the limit as ε → 0, the third term in the last display tends to − k α k D(π (k) P(β)) ≤ 0.
The second term is bounded above by the expression − k α k jπk,j log P j (β), which is finite becauseπ has finite support. The first term in the display tends to −∞, which establishes that f (δ) < f (0) for some sufficiently small δ > 0. We have shown that, for any m + n ∈ I(ω), π cannot minimize (A. 20) if π m,n = 0. As π m,n is arbitrary within m + n ∈ I(ω), it follows that π * m,n > 0 whenever m + n ∈ I(ω).
We now establish the existence of Lagrange multipliers and the form of the optimal solution for the polynomial case.
Theorem A.9. Suppose that (α, ω, β) are irreducible feasible constraints yielding equality in (2.4), and let π * be the corresponding unique minimizer from Lemma A.6. Then there exist positive constants {D k } k∈K and {W i } i∈I such that the minimizer takes the form otherwise.
Proof. The strict equality in the constraints requires every feasible point to be supported on the finite set satisfying k ∈ K and k + j ∈ I and, hence, the minimization problem (A.20) may be considered to be a finite-dimensional problem over this set. By Lemma A.8 the minimizer π * is strictly positive. Since the objective function is continuously differentiable in a neighborhood of π * , and the constraints are linear, Lagrange multipliers are guaranteed to exist for this problem (see, e.g., [4], Proposition 1.33). Specifically, there are constants z k and w i such that the Lagrangian is also minimized at π * , with all partial derivatives of L being zero at the optimal point. Taking partial derivatives and rearranging, the optimality condition yields π * k,j = P j (β)e z k −1+w k+j . The result follows on defining D k = e z k −1 and W i = e w i .
We now give the corresponding theorem for the exponential case.
Theorem A. 10. Suppose that (α, ω, β) are irreducible feasible constraints yielding strict inequality in (2.4), and let π * be the corresponding unique minimizer from Lemma A.6. Then there exist positive constants ρ, {C k } k∈K , and {W i } i∈I,i≤I such that the minimizer takes the form Proof. To avoid difficulties with infinite-dimensional Lagrangians, consider a sequence of truncated problems indexed by a sequence of integers M > I.
By construction, the minimizer of this problem is obtained simply by truncating π * . As in the previous lemma, the strict positivity of the minimizer, together with the linearity of the constraints, guarantees the existence of Lagrange multipliers via [4], Proposition 1.33. The Lagrangian for the M th problem is Since the derivative of L with respect to π k,j must be zero at the minimizer, it follows that for all j < M and k + j ∈ I, where for convenience we have defined w i = 0 for i > I. For k + j > I, note that are also independent of M . Then the above expression for π * k,j holds for all k + j ∈ I, with fixed Lagrange multipliers y, {z k } and {w i }.
The form expressed in the theorem is based on the substitutions ρ = e y , C k = e (ρ−1)β−1+z k and W i = e w i . Now that we have the general form of the minimizing endpoint values π * k,j , we are ready to characterize the extremal curves. We denote the mean of the kth distribution π * (k) by β k . = j jπ * k,j . In the exponential case, we define ρ k = ρβ/β k so that the distribution π (k) meets I − k terminal constraints, has mean β k and a Poisson ρ k β k tail. Denoting the terminal constraints by ω k,j . = π * k,j and ω (k) = (ω k,0 , . . . , ω k,I−k ), we see that π * (k) is the minimizing distribution arising in Theorem A.1 for the terminal constraints (1, ω (k) , β k ), with associated twist parameters ρ k and C k . In the polynomial case, the terminal constraints (1, ω (k) , β k ) mean that each subproblem is polynomial, with C k = 0. In either case, Theorem A.1 gives the form of the extremal occupancy curves γ k,j (x) for each of these k subproblems. We now show that the subproblem curves sum to form the general extremals.
Proof. We assume without loss of generality that the constraints are irreducible. Otherwise, each irreducible subproblem may be treated separately.
We extend the definition of γ i (x) for i > I by using the extended definition of γ k,j (x) used in the proof of Theorem A.1 [see (A. 13)]. Also, for convenience, define γ k,j (x) . = γ k,j (xβ k /β) and likewise, define ψ k,j . The ψ i inherit from the γ i the relation To see that the γ i are valid occupancy curves, note that Also, the −ψ i (x) are all nonnegative on [0, β], and where the last equality follows from the fact that the π * k,j satisfy the conservation constraint (A.21). Hence, curves γ i (x), i ≤ I and γ I+ (x) satisfy the conditions of Lemma 2.1.
It is clear that the γ i satisfy the desired initial conditions since γ k,0 (0) = 1 and γ k,j (0) = 0 for j > 0. The terminal conditions are guaranteed by the fact that the values γ k,j (β k ) = π * k,j satisfy the constraints (A.22). In order to establish that the curves satisfy the Euler-Lagrange equations, we first show that the rescaled zero-occupancy curve ψ k,0 for the kth subproblem is proportional to the kth derivative of the overall zero-occupancy curve ψ 0 .
First, take the exponential case, and recall that ρ k β k = ρβ. The kth zerooccupancy curve, after rescaling, is ψ k,0 (x) = C k e −ρ k (xβ k /β) + Here we have used that ω k,i = π * k,i = C k P i (β)W k+i when i ≤ I − k. The kth derivative of ψ 0 = α 0 ψ 0,0 is Using Theorem A.1 to express γ k,j in terms of ψ k,0 , we have Similarly, we obtain so that the extremals satisfy the simple relation , (A. 26) which also arose in the case of empty initial conditions. Because the polynomial portion of ψ 0 has degree I, the ratio θ i (x)/γ i (x) is given by the constant ρ for i > I, which establishes (as in the proof of Lemma A.3) that and that In order to demonstrate a strong minimum we will need the following.
Proof. We may take α 0 > 0 without loss of generality. By Theorem A.11, the extremals satisfy the usual form of the Euler-Lagrange equations. The above indefinite integral is log(−ψ   xβ k β e β = γ k,j (x) (−x) j e −β /j! .
By construction, the endpoints γ k,j (β) coincide with the optimal arguments π * k,j of the minimization problem. The proof of the polynomial case is almost identical, except that we use Lemma A.4 and (A.28).
A.8. Extremal curves have globally minimal cost. In this section we prove the following theorem: Theorem A.14 (Strong minimum). Given feasible constraints (α, ω, β), let γ be the corresponding extremal occupancy path defined in Theorem A.11, and letγ be any other occupancy path satisfying the same constraints. Then J(γ) ≤ J(γ). We first introduce some notation. Let O denote the set of valid occupancy functions, that is, vector functions γ such that the cumulative occupancy functions ψ satisfy the conditions of Lemma 2.1, and let O(α, ω, β) . = {γ ∈ O : γ(0) = α, γ(β) = ω} be the subset of valid occupancy functions satisfying feasible constraints (α, ω, β). The proof of the following lemma is a straightforward consequence of the convexity of the map (θ, γ) → D(θ γ) and, hence, omitted.
To simplify the notation, we do not explicitly indicate the dependence of G onγ andγ. Lemma A.15 ensures that G is a well-defined, convex function for anyγ,γ ∈ O(α, ω, β).
For the remainder of this section, we once again restrict attention to irreducible constraints, without loss of generality. The following lemma establishes the minimality of the extremals in an important special case. The proof uses the fact that the extremal curve and its derivative can be bounded away from zero.
Lemma A. 16. Suppose that (α, ω, β) are strictly positive, irreducible feasible constraints, where the upper indices K and I of α and ω satisfy K = I + 1 in the exponential case, or K = I in the polynomial case. Suppose that γ is the extremal curve for these constraints, defined in Theorem A.11, and thatγ is any competing occupancy function satisfying the same constraints. Then J(γ) ≤ J(γ).
Proof. We construct the family of paths γ ε = (1−ε)γ +εγ, with G[ε] = J(γ ε ). It follows from convexity that G is left and right differentiable wherever it is finite. We will show that G ′ + [0] = 0, where G ′ + [ε] denotes the right derivative of G. The convexity of G then implies the desired result.
It will be convenient to work with the cumulative occupancy functions ψ ε , and as in Section A.3, we will mix notation by writing, for example, J(γ) = β 0 L(ψ, θ) dx.
After defining we may write We can assume without loss that G(1) = J(γ) < ∞, since there is nothing to prove otherwise. We wish to show that differentiation under the integral sign with respect to ε is valid in a neighborhood of 0. The validity of this operation will follow from [23], Corollary 39.2, if we can provide a constant bound on the partial derivative of g with respect to ε for almost every x ∈ [0, β].
To construct this bound, we will first establish that the components γ i (x) and derivatives θ i (x) = −ψ i (x) are uniformly bounded away from zero. For specificity, we first assume that (α, ω, β) are exponential constraints. Note that in the empty case studied in Section A.4, γ 0 (x) decreases monotonically to γ 0 (β) = ω 0 and θ 0 (x) decreases monotonically to θ 0 (β). Inspection of the formula for ψ 0 in Theorem A.1 reveals that θ 0 (β) = ω 1 /β if I > 0 and θ 0 (β) = CP 1 (ρβ)/β otherwise. Hence, for any exponential problem with empty initial conditions and positive terminal conditions ω i , γ 0 and θ 0 are uniformly bounded away from zero. For the constraints (α, ω, β) under consideration, each of the associated subproblems is an exponential empty problem with positive terminal conditions, and so γ k,0 (x) and θ k,0 (x) are uniformly bounded from zero for each subproblem. These, in turn, lower bound the overall γ i and θ i , since, for example, The catch-all term γ I+ (x) is monotonically increasing, and hence, satisfies γ I+ (x) ≥ α I+1 > 0. The identity θ I+ (x) = ργ I+ (x), established in the proof of Theorem A.11, ensures a similar bound on θ I+ (x).