Random time changes for sock-sorting and other stochastic process limit theorems.

*(English)*Zbl 0929.60023Summary: 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.

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.

##### MSC:

60F17 | Functional limit theorems; invariance principles |

60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |

60G70 | Extreme value theory; extremal stochastic processes |