Publication 2006-006

To exploit large deviation approximations for allocation and occupancy problems one must solve a deterministic optimal control problem (or equivalently, a calculus of variations problem). As this paper demonstrates, and in sharp contrast to the great majority of large deviation problems for processes with state dependence, for allocation problems one can construct more-or-less explicit solutions. Two classes of allocation problems are studied. The first class considers objects of a single type with a parameterized family of placement probabilities. The second class considers only equally likely placement probabilities, but allows for more than one type of object. In both cases, we identify the Hamilton-Jacobi-Bellman equation whose solution characterizes the minimal cost, explicitly construct solutions, and identify the minimizing trajectories. The explicit construction is possible because of the very tractable properties of the relative entropy function with respect to optimization.