Title: Fluctuation bounds for socksorting 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
empiricalprocess 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 secondorder 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/(2q1)}, 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 twosided
Brownian motion. We give sufficient conditions for this
secondorder fluctuation to be independent of the firstorder
one.
