Title: Socks & Boxes: Variations on Daniel Bernoulli's marriage problem. Abstract: Starting from a classical problem about the expected number of singletons when a given number n of draws are made at random from a collection of 2N paired objects --- for instance, socks in a basket which are to be sorted into pairs --- we adapt general empirical-process and martingale methods to describe the asymptotic behavior of a varied class of stochastic processes. In particular, we are concerned with processes whose expectations starts at a small value, rise up to a clear maximum, and then fall back down. In many such cases, as in this sock-sorting process, the process itself converges, when properly normalized, to a Gaussian limit, as N->. The maximum of the process is closely approximated by the maximum of the expectation, and its fluctuations about this value are nearly normal, for large N, with a size on the order of $\sqrt{N}$. Moreover, under fairly general conditions we find that there is an extra term of order $\sqrt[3]{N}$ which for large N approaches the distribution of the maximum of a Brownian motion with downward quadratic drift. These two terms are asymptotically independent as N grows large. While the $\sqrt{N}$ term has expectation 0, the $\sqrt[3]{N}$ term has positive expectation; this means that the difference between the expected maximum and the maximum expectation in fact grows at this slower $\sqrt[3]{N}$ rate. Applications of these methods to queueing theory, random allocations and the theory of random graphs, among others, are discussed. |