A cutting process for random mappings

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

Abstract

In this paper we consider a cutting process for random mappings. Specifically, for 0 < m < n, we consider the initial (uniform) random mapping digraph Gn on n labeled vertices, and we delete (if possible), uniformly and at random, m noncyclic directed edges from G n. The maximal random digraph consisting of the unicyclic components obtained after cutting the m edges is called the trimmed random mapping and is denoted by Gnm. If the number of noncyclic directed edges is less than m, then Gnm consists of the cycles, including loops, of the initial mapping Gn. We consider the component structure of the trimmed mapping Gnm. In particular, using the exact distribution we determine the asymptotic distribution of the size of a typical random connected component of Gnm as n, m ? 8. This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) m = o(vn), (ii) m = ß vn, where ß > 0 is a fixed parameter, and (iii) vn = o(m). This allows us to study the joint distribution of the order statistics of the normalized component sizes of Gnm. When m = o(vn), we obtain the Poisson-Dirichlet(1/2) distribution in the limit, whereas when vn = o(m) the limiting distribution is Poisson-Dirichlet(1). Convergence to the Poisson-Dirichlet(?) distribution breaks down when m = O(vn), and in particular, there is no smooth transition from the PD(1/2) distribution to the PD(1) via the Poisson-Dirichlet distribution as the number of edges cut increases relative to n, the number of vertices in Gn. © 2006 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)287-306
Number of pages20
JournalRandom Structures and Algorithms
Volume30
Issue number1-2
DOIs
Publication statusPublished - Jan 2007

Fingerprint

Poisson-Dirichlet Distribution
Random Mapping
Dirichlet
Siméon Denis Poisson
Limiting Distribution
Order Statistics
Joint Distribution
Breakdown

Keywords

  • Component structure
  • Poisson-Dirichlet distribution
  • Random mappings

Cite this

Hansen, Jennie C. ; Jaworski, Jerzy. / A cutting process for random mappings. In: Random Structures and Algorithms. 2007 ; Vol. 30, No. 1-2. pp. 287-306.
@article{71efef3f816c4e76a2b1a4e462b2499c,
title = "A cutting process for random mappings",
abstract = "In this paper we consider a cutting process for random mappings. Specifically, for 0 < m < n, we consider the initial (uniform) random mapping digraph Gn on n labeled vertices, and we delete (if possible), uniformly and at random, m noncyclic directed edges from G n. The maximal random digraph consisting of the unicyclic components obtained after cutting the m edges is called the trimmed random mapping and is denoted by Gnm. If the number of noncyclic directed edges is less than m, then Gnm consists of the cycles, including loops, of the initial mapping Gn. We consider the component structure of the trimmed mapping Gnm. In particular, using the exact distribution we determine the asymptotic distribution of the size of a typical random connected component of Gnm as n, m ? 8. This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) m = o(vn), (ii) m = {\ss} vn, where {\ss} > 0 is a fixed parameter, and (iii) vn = o(m). This allows us to study the joint distribution of the order statistics of the normalized component sizes of Gnm. When m = o(vn), we obtain the Poisson-Dirichlet(1/2) distribution in the limit, whereas when vn = o(m) the limiting distribution is Poisson-Dirichlet(1). Convergence to the Poisson-Dirichlet(?) distribution breaks down when m = O(vn), and in particular, there is no smooth transition from the PD(1/2) distribution to the PD(1) via the Poisson-Dirichlet distribution as the number of edges cut increases relative to n, the number of vertices in Gn. {\circledC} 2006 Wiley Periodicals, Inc.",
keywords = "Component structure, Poisson-Dirichlet distribution, Random mappings",
author = "Hansen, {Jennie C.} and Jerzy Jaworski",
year = "2007",
month = "1",
doi = "10.1002/rsa.20159",
language = "English",
volume = "30",
pages = "287--306",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "1-2",

}

A cutting process for random mappings. / Hansen, Jennie C.; Jaworski, Jerzy.

In: Random Structures and Algorithms, Vol. 30, No. 1-2, 01.2007, p. 287-306.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A cutting process for random mappings

AU - Hansen, Jennie C.

AU - Jaworski, Jerzy

PY - 2007/1

Y1 - 2007/1

N2 - In this paper we consider a cutting process for random mappings. Specifically, for 0 < m < n, we consider the initial (uniform) random mapping digraph Gn on n labeled vertices, and we delete (if possible), uniformly and at random, m noncyclic directed edges from G n. The maximal random digraph consisting of the unicyclic components obtained after cutting the m edges is called the trimmed random mapping and is denoted by Gnm. If the number of noncyclic directed edges is less than m, then Gnm consists of the cycles, including loops, of the initial mapping Gn. We consider the component structure of the trimmed mapping Gnm. In particular, using the exact distribution we determine the asymptotic distribution of the size of a typical random connected component of Gnm as n, m ? 8. This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) m = o(vn), (ii) m = ß vn, where ß > 0 is a fixed parameter, and (iii) vn = o(m). This allows us to study the joint distribution of the order statistics of the normalized component sizes of Gnm. When m = o(vn), we obtain the Poisson-Dirichlet(1/2) distribution in the limit, whereas when vn = o(m) the limiting distribution is Poisson-Dirichlet(1). Convergence to the Poisson-Dirichlet(?) distribution breaks down when m = O(vn), and in particular, there is no smooth transition from the PD(1/2) distribution to the PD(1) via the Poisson-Dirichlet distribution as the number of edges cut increases relative to n, the number of vertices in Gn. © 2006 Wiley Periodicals, Inc.

AB - In this paper we consider a cutting process for random mappings. Specifically, for 0 < m < n, we consider the initial (uniform) random mapping digraph Gn on n labeled vertices, and we delete (if possible), uniformly and at random, m noncyclic directed edges from G n. The maximal random digraph consisting of the unicyclic components obtained after cutting the m edges is called the trimmed random mapping and is denoted by Gnm. If the number of noncyclic directed edges is less than m, then Gnm consists of the cycles, including loops, of the initial mapping Gn. We consider the component structure of the trimmed mapping Gnm. In particular, using the exact distribution we determine the asymptotic distribution of the size of a typical random connected component of Gnm as n, m ? 8. This asymptotic distribution depends on the relationship between n and m and we show that there are three distinct cases: (i) m = o(vn), (ii) m = ß vn, where ß > 0 is a fixed parameter, and (iii) vn = o(m). This allows us to study the joint distribution of the order statistics of the normalized component sizes of Gnm. When m = o(vn), we obtain the Poisson-Dirichlet(1/2) distribution in the limit, whereas when vn = o(m) the limiting distribution is Poisson-Dirichlet(1). Convergence to the Poisson-Dirichlet(?) distribution breaks down when m = O(vn), and in particular, there is no smooth transition from the PD(1/2) distribution to the PD(1) via the Poisson-Dirichlet distribution as the number of edges cut increases relative to n, the number of vertices in Gn. © 2006 Wiley Periodicals, Inc.

KW - Component structure

KW - Poisson-Dirichlet distribution

KW - Random mappings

UR - http://www.scopus.com/inward/record.url?scp=33846671561&partnerID=8YFLogxK

U2 - 10.1002/rsa.20159

DO - 10.1002/rsa.20159

M3 - Article

VL - 30

SP - 287

EP - 306

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1-2

ER -