Header

UZH-Logo

Maintenance Infos

A tale of three couplings: Poisson-Dirichlet and GEM approximations for random permutations


Arratia, R; Barbour, A D; Tavaré, S (2006). A tale of three couplings: Poisson-Dirichlet and GEM approximations for random permutations. Combinatorics, Probability & Computing, 15(1-2):31-62.

Abstract

For a random permutation of $n$ objects, as $n \to \infty$, the process giving the proportion of elements in the longest cycle, the second-longest cycle, and so on, converges in distribution to the Poisson–Dirichlet process with parameter 1. This was proved in 1977 by Kingman and by Vershik and Schmidt. For soft reasons, this is equivalent to the statement that the random permutations and the Poisson–Dirichlet process can be coupled so that zero is the limit of the expected $\ell_1$ distance between the process of cycle length proportions and the Poisson–Dirichlet process. We investigate how rapid this metric convergence can be, and in doing so, give two new proofs of the distributional convergence.

One of the couplings we consider has an analogue for the prime factorizations of a uniformly distributed random integer, and these couplings rely on the ‘scale-invariant spacing lemma’ for the scale-invariant Poisson processes, proved in this paper.

Abstract

For a random permutation of $n$ objects, as $n \to \infty$, the process giving the proportion of elements in the longest cycle, the second-longest cycle, and so on, converges in distribution to the Poisson–Dirichlet process with parameter 1. This was proved in 1977 by Kingman and by Vershik and Schmidt. For soft reasons, this is equivalent to the statement that the random permutations and the Poisson–Dirichlet process can be coupled so that zero is the limit of the expected $\ell_1$ distance between the process of cycle length proportions and the Poisson–Dirichlet process. We investigate how rapid this metric convergence can be, and in doing so, give two new proofs of the distributional convergence.

One of the couplings we consider has an analogue for the prime factorizations of a uniformly distributed random integer, and these couplings rely on the ‘scale-invariant spacing lemma’ for the scale-invariant Poisson processes, proved in this paper.

Statistics

Citations

Dimensions.ai Metrics
5 citations in Web of Science®
4 citations in Scopus®
6 citations in Microsoft Academic
Google Scholar™

Altmetrics

Downloads

59 downloads since deposited on 05 Jan 2010
4 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2006
Deposited On:05 Jan 2010 15:00
Last Modified:19 Feb 2018 06:49
Publisher:Cambridge University Press
ISSN:0963-5483
Additional Information:Copyright © 2006 Cambridge University Press
OA Status:Green
Publisher DOI:https://doi.org/10.1017/S0963548305007054

Download

Download PDF  'A tale of three couplings: Poisson-Dirichlet and GEM approximations for random permutations'.
Preview
Filetype: PDF (Verlags-PDF)
Size: 1MB
View at publisher