On large deviation approximations for occupancy problems.

摘要

Occupancy problems concern the distribution of r balls in n urns. We fix the ratio between r and n and study the asymptotics of the empirical distribution of urns that contain a given number of balls. In the first part of the thesis, we obtain theoretical large deviation asymptotics results. In the second part, we investigate numerical simulations that arise in applications.; Part I. In Chapter 2, Large deviation principle (LDP) for general occupancy problems is obtained. In this general setting, we allow the likelihood that a ball lands in a given urn to depend on its contents prior to the throw, as in Bose-Einstein statistics (BE) and Fermi-Dirac statistics (FD). We discuss a parametric family of statistical models of which the MB (Maxwell-Boltzmann), BE and FD statistics are all special cases. A complete large deviation analysis of a process level problem is carried out and the rate function for the original problem is obtained via contraction mapping theorem. We also conjecture that the variational problem that characterizes the rate function can be represented as a finite dimensional minimization problem, which can be solved explicitly. In Chapter 3, we obtain a refined large deviation asymptotics for the classical occupancy problem, where the statistics is MB and we are interested in the distribution of empty urns.; Part II. In Chapter 4, we are interested in dimensioning optical switches. The problem was to determine the number of shared wavelength converters that would be needed to provide sufficiently low blocking probability in a bufferless optical packet switch. This problem can be related to the classical occupancy problem. The large deviation analysis identifies a family of extremal trajectories, based on which importance sampling is implemented to give satisfactory approximations to the blocking probability. The numerical results also confirm the refined approximation results in Chapter 3. In Chapter 5, we are interested to simulate both MB and FD statistics. In Chapter 2, we identified the rate function as a variational problem whose extremals are building blocks of importance sampling schemes. Different heuristics, including "open loop" and "feedback" samplers, are proposed, implemented and compared.; *Research supported in part by the National Science Foundation (NSF-DMS-0306070).