论文标题
随机排列和队列
Random Permutations and Queues
论文作者
论文摘要
鉴于生长规则，该规则依次构建了增加程度的随机排列，因此rencontre问题的随机过程版本询问置换没有固定点（Singleton Cycles）的时间比例是多少。我们表明，离散时间中国餐厅流程（CRP）没有显示此限制。然后，我们考虑CRP连续时间的相关嵌入，从而表明它确实具有时间平均的和其他限制。通过这种嵌入，置换的循环结构可以表示为无限 - 服务器队列的串联。我们使用这种联系来展示如何根据排列周期计数的演变来解释排队理论的结果。
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.
