Title: Fluctuation bounds for sock-sorting and other stochastic processes.

Abstract: We consider stochastic processes which may be defined as averages F_n=n-1 \sum_{i=1}^n f of n independent (or almost independent) random cadlag functions from R to itself, with small total variation. Such processes arise in many contexts, including queueing and storage problems. Using empirical-process techniques, we derive bounds on the fluctuations of such processes, and functional limit theorems. The emphasis is on sufficient conditions which may be verified easily in a wide variety of problems, in which the f may be unbounded, not identically distributed, or not independent. When the expectation E F(t)$ itself has a unique maximum, at a point t_0, we may then also derive second-order bounds for the difference between max F_n(t) and F_n(t_0). While |max F_n(t)-E F_n(t_0)| is stochastically on the order of $n^{-1/2}$ for large n, max F_n(t)-F_n(t_0) is strictly smaller, being only on the order of n^{-q/(2q-1)}, where q is the degree of the maximum at E F_n(t_0). Under fairly general conditions, each of these quantities converges in law to a nontrivial distribution, when divided by the appropriate power of n. Generally this limit is of the form sup_{t\in R} B(t) -D t^q for positive constants and D, and B(t) a two-sided Brownian motion. We give sufficient conditions for this second-order fluctuation to be independent of the first-order one.