# A tale of three couplings: Poisson-Dirichlet and GEM approximations for random permutations - Zurich Open Repository and Archive

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.

## Citations

4 citations in Web of Science®
3 citations in Scopus®
Google Scholar™

## Downloads

47 downloads since deposited on 05 Jan 2010
12 downloads since 12 months
Detailed statistics

## Additional indexing

Item Type: Journal Article, refereed, original work 07 Faculty of Science > Institute of Mathematics 510 Mathematics English 2006 05 Jan 2010 15:00 05 Apr 2016 13:23 Cambridge University Press 0963-5483 Copyright © 2006 Cambridge University Press https://doi.org/10.1017/S0963548305007054

## Download

Preview
Filetype: PDF (Verlags-PDF)
Size: 1MB
View at publisher

## TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.