Random Permutations and Queues

2022/09/26 by Alexander Gnedin, Gnedin, Alexander, Dudley Stark +1 · 2 citations
Business, Management and Accounting · Computer Science · Decision Sciences · #60C05 #60K25 #Advanced Queuing Theory Analysis #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Probability and Risk Models

paper · pdf · doi:10.48550/arxiv.2209.12781

openalex publication_date 2022/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a growth rule which sequentially constructs random permutations of increasing degree, the stochastic process version of the rencontre problem asks what is the limiting proportion of time that the permutation has no fixed points (singleton cycles). We show that the discrete-time Chinese Restaurant Process (CRP) does not exhibit this limit. We then consider the related embedding of the CRP in continuous time and thereby show that it does have this and other limits of the time averages. By this embedding the cycle structure of the permutation can be represented as a tandem of infinite-server queues. We use this connection to show how results from the queuing theory can be interpreted in terms of the evolution of the cycle counts of permutations.

Cited by

• A Chinese restaurant process for multiset permutations
• Maximal Counts in the Stopped Occupancy Problem

Related

• Limit theorems for random permutations induced by Chinese restaurant processes
• A Chinese restaurant process for multiset permutations
• A Ray-Knight representation of up-down Chinese restaurants
• Permutations in competing growth processes and balls-in-bins
• Scaling limit for small blocks in the Chinese restaurant process