<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
Sorting Using Complete Subintervals and the Maximum Number of Runs in a Randomly Evolving Sequence
Svante Janson
Department of Mathematics, Uppsala University, PO Box 480, SE-751~06 Uppsala, Sweden
Annals of Combinatorics 12 (4) pp.413-443 December, 2008
AMS Subject Classification: 60C05; 68W40
We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length $n$ that starts as a string of $0$'s, and then evolves by changing each $0$ to $1$, with the $n$ changes done in random order. What is the maximal number of runs of $1$'s? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order $n\qq$, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to $1$; there is also a second order term of order $n\qqq$. We also treat some variations, including priority queues and sock-sorting. The proofs use methods originally developed for random graphs.
Keywords: sorting algorithm, runs, priority queues, sock-sorting, evolution of random strings, Brownian motion


1. G. af H¨allstr¨om, Ein lineares Inselproblem der kombinatorischen Wahr-schein-lich-keitsrech- nung, Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1952 (123) (1952) 9 pp.

2. A.D. Barbour, A note on the maximum size of a closed epidemic, J. R. Stat. Soc. Ser. B 37 (3) (1975) 459-–460.

3. A.D. Barbour, Brownian motion and a sharply curved boundary, Adv. in Appl. Probab. 13 (4) (1981) 736–-750.

4. P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York- London-Sydney, 1968.

5. H.E. Daniels, The maximum size of a closed epidemic, Adv. in Appl. Probab. 6 (1974) 607-–621.

6. H.E. Daniels, The maximum of a Gaussian process whose mean path has a maximum, with an application to the strength of bundles of bres, Adv. in Appl. Probab. 21 (2) (1989) 315-– 333.

7. H.E. Daniels and T.H.R. Skyrme, The maximum of a random walk whose mean path has a maximum, Adv. in Appl. Probab. 17 (1) (1985) 85-–99.

8. P. Flajolet, J. Franc¸on, and J. Vuillemin, Sequence of operations analysis for dynamic data structures, J. Algorithms 1 (2) (1980) 111-–141.

9. P. Flajolet, C. Puech, and J. Vuillemin, The analysis of simple list structures, Inform. Sci. 38 (2) (1986) 121-–146.

10. P. Groeneboom, Brownian motion with a parabolic drift and Airy functions, Probab. Theory Related Fields 81 (1) (1989) 79-–109.

11. A. Gut, Probability: A Graduate Course, Springer, New York, 2005.

12. J. Jacod and A.N. Shiryaev, Limit Theorems for Stochastic Processes, Springer-Verlag, Berlin, 1987.

13. S. Janson, A functional limit theorem for random graphs with applications to subgraph count statistics, Random Structures Algorithms 1 (1) (1990) 15-–37.

14. S. Janson, Orthogonal decompositions and dunctional limit theorems for random graph statistics, Mem. Amer. Math. Soc. 111 (534) (1994) vi+78 pp.

15. S. Janson, Functional limit theorems for multitype branching processes and generalized P´olya urns, Stochastic Process. Appl. 110 (2) (2004) 177-–245.

16. O. Kallenberg, Foundations of Modern Probability, 2nd Ed., Springer-Verlag, New York, 2002.

17. C.M. Kenyon and J.S. Vitter, Maximum queue size and hashing with lazy deletion, Algorithmica 6 (4) (1991) 597–-619.

18. W.V. Li and G. Pritchard, A central limit theorem for the sock-sorting problem, In: High Dimensional Probability, Progr. Probab., Vol. 43, Birkh¨auser, Basel, (1998) pp. 245-–248.

19. G. Louchard, Random walks, Gaussian processes and list structures, Theoret. Comput. Sci. 53 (1) (1987) 99-–124.

20. G. Louchard, Large nite population queueing systems part I: the innite server model, Comm. Statist. Stochastic Models 4 (3) (1988) 473-–505.

21. G. Louchard, C. Kenyon, and R. Schott, Data structures' maxima, SIAM J. Comput. 26 (4) (1997) 1006-–1042.

22. A.M. Mood, The distribution theory of runs, Ann. Math. Statistics 11 (1940) 367–-392.

23. D. Steinsaltz, Random time changes for sock-sorting and other stochastic process limit theorems, Electron. J. Probab. 4 (1999) paper 14.

24. W.L. Stevens, Distribution of groups in a sequence of alternatives, Annals of Eugenics 9 (1939) 10-–17.

25. C.J. Van Wyk and J.S. Vitter, The complexity of hashing with lazy deletion, Algorithmica 1 (1986) 17-–29.