Random allocations: new and extended models and techniques with applications and numerics.

Abstract

This thesis provides a general methodology for classifying and describing many combinatoric problems, systematising and finding theoretical expressions for quantities of interest, and investigating their feasible numerical evaluation. Unifying notation and definitions are provided. Our knowledge of random allocations is also extended. This is achieved by investigating new processes, generalising known processes, and by providing a formal structure and innovative techniques for analysing them. The random allocation models described in this thesis can be classified as occupancy urn models, in which we have a sequence of urns and throw balls into them, and investigate static, waiting-time and dynamic processes. Various structures are placed on the relationship(s) between cells, balls, and the selection of items being distributed, including varieties, batch arrivals, taboo sets and blocking sets. Static, waiting-time and dynamic processes are investigated. Both without-replacement and with-replacement sampling types are considered. Emphasis is placed on the distributions of waiting-times for one or more events to occur measured from the time a particular event occurs; this begins as an abstraction and generalisation of a model of departures of cars parked in lanes. One of several additional determinations is the platoon size distribution. Models are analysed using combinatorial analysis and Markov Chains. Global attributes are measured, including maximum waits, maximum room required, moments and the clustering of completions. Various conversion formulae have been devised to reduce calculation times by several orders of magnitude. New and extended applications include Queueing in Lanes, Cake Displays, Coupon Collector's Problem, Sock-Sorting, Matching Dependent Sets (including Genetic Code Attribute Matching and the game SET), the Zig-Zag Problem, Testing for Randomness (including the Cake Display Test, which is a without-replacement test similar to the standard Empty Cell test), Waiting for Luggage at an Airport, Breakdowns in a Network, Learning Theory and Estimating the Number of Skeletons at an Archaeological Dig. Fundamental, reduction and covering theorems provide ways to reduce the number of calculations required. New combinatorial identities are discovered and a well-known one is proved in a combinatorial way for the first time. Some known results are derived from simple cases of the general models.