Random permutations and queues
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3165055 (Why is no real title available?)
- scientific article; zbMATH DE number 140536 (Why is no real title available?)
- scientific article; zbMATH DE number 1947316 (Why is no real title available?)
- scientific article; zbMATH DE number 1782874 (Why is no real title available?)
- scientific article; zbMATH DE number 3437808 (Why is no real title available?)
- scientific article; zbMATH DE number 227027 (Why is no real title available?)
- M/M/∞ transience revisited
- A Combinatorial Method in the Theory of Queues
- Applied Probability and Queues
- Asymptotic expansions for the congestion period for the M/M/ queue
- Busy period in GIX/G/∞
- Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
- Cycles, permutations and the stucture of the Yule process with immigration
- Extreme value theory for a class of discrete distributions with applications to some stochastic processes
- Feller coupling of cycles of permutations and Poisson spacings in inhomogeneous Bernoulli trials
- First Passage and Recurrence Distributions
- Foundations of Modern Probability
- Logarithmic combinatorial structures: A probabilistic approach
- M/G/ tandem queues
- On infinite server queues with batch arrivals
- On the severity of M/M/∞ congested episodes
- Ordered Cycle Lengths in a Random Permutation
- Reversibility and stochastic networks. With a new preface
- Service-time ages, residuals, and lengths in an \(\mathrm{M}/\mathrm{GI}/\infty \) service system
- Some characteristics of multiphase queuing systems with infinitely many channels
- The Poisson-Dirichlet distribution and related topics. Models and asymptotic behaviors
- The Poisson–Dirichlet Distribution and the Scale-Invariant Poisson Process
- The birth process with immigration, and the genealogical structure of large populations
- The busy period of the queueing system M/G/∞
- The cycle structure of random permutations
- Transformations of Poisson streams and their application to communication systems
- Transient characteristics of an M/M/∞ system
- Upper bounds on Poisson tail probabilities
- Z-measures on partitions and their scaling limits
Cited in
(5)- Quasirandom permutations
- Records in the infinite occupancy scheme
- Markov chains generating random permutations and set partitions
- Scaling limit for small blocks in the Chinese restaurant process
- Urn models, Markov chains and random walks in cosmological topologically massive gravity at the critical point
This page was built for publication: Random permutations and queues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6107827)
