Random mappings with exchangeable in-degrees

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

In this article we introduce a new random mapping model, TnD^, which maps the set {1,2,..., n] into itself. The random mapping TnD^ is constructed using a collection of exchangeable random variables D1,....,Dn which satisfy ?i=1n D^i,- = n. In the random digraph, G nD^, which represents the mapping TnD^, the in-degree sequence for the vertices is given by the variables D^1, D^2,...,D^n, and, in some sense, GnD^ can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components, and the size of a typical component can be expressed in terms of expectations of various functions of D^1, D^2 ,...,D^n. We also consider two special examples of TnD^ which correspond to random mappings with preferential and anti-preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above. © 2007 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)105-126
Number of pages22
JournalRandom Structures and Algorithms
Volume33
Issue number1
DOIs
Publication statusPublished - Aug 2008

Keywords

  • Anti-preferential attachment
  • Component structure
  • Exchangeable in-degree sequence
  • Preferential attachment
  • Random mappings

Fingerprint Dive into the research topics of 'Random mappings with exchangeable in-degrees'. Together they form a unique fingerprint.

Cite this