Local properties of random mappings with exchangeable in-degrees

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

In this paper we investigate the 'local' properties of a random mapping model, TnD^, which maps the set {1, 2,..., n} into itself. The random mapping TnD^, which was introduced in a companion paper (Hansen and Jaworski (2008)), is constructed using a colle tion of exchangeable random variables D^ l,..., D^n which satisfy ? i=ln D^i = n. In the random digraph, GnD^, 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. By local properties we mean the distributions of random mapping characteristics related to a given vertex v of GnD^ - for example, the numbers of predecessors and successors of v in GnD^. We show that the distribution of several variables associated with the local structure of GnD^ can be expressed in terms of expectations of simple 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, and determine, for these examples, exact and asymptotic distributions for the local structure variables considered in this paper. These distributions are also of independent interest. © Applied Probability Trust 2008.

Original languageEnglish
Pages (from-to)183-205
Number of pages23
JournalAdvances in Applied Probability
Volume40
Issue number1
DOIs
Publication statusPublished - Mar 2008

Keywords

  • Exchangeable in-degrees
  • Local structure
  • Random mapping

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

Cite this