Random time changes for sock-sorting and other stochastic process limit theorems. (English) Zbl 0929.60023

Summary: A common technique in the theory of stochastic processes is to replace a discrete time coordinate by a continuous randomized time, defined by an independent Poisson or other process. Once the analysis is complete on this Poissonized process, translating the results back to the original setting may be nontrivial. It is shown here that, under fairly general conditions, if the process \(S_n\) and the time change \(\varphi_n\) both converge, when normalized by the same constant, to limit processes, the combined process \(S_n(\varphi_n(t))\) converges, when properly normalized, to a sum of the limit of the orginal process, and the limit of the time change multiplied by the derivative of \(E S_n\). It is also shown that earlier results on the fine structure of the maxima are preserved by these time changes.
The remainder of the paper applies these simple results to processes which arise in a natural way from sorting procedures, and from random allocations. The first example is a generalization of “sock-sorting”: Given a pile of \(n\) mixed-up pairs of socks, we draw out one at a time, laying it on a table if its partner has not yet been drawn, and putting completed pairs away. The question is: What is the distribution of the maximum number of socks ever on the table, for large \(n\)? Similarly, when randomly throwing balls into \(n\) (a large number) boxes, we examine the distribution of the maximum over all times of the number of boxes that have (for example) exactly one ball.


60F17 Functional limit theorems; invariance principles
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60G70 Extreme value theory; extremal stochastic processes

Online Encyclopedia of Integer Sequences:

Numerator of answer to sock-sorting problem with n socks.