Premium
A random mapping with preferential attachment
Author(s) -
Hansen Jennie C.,
Jaworski Jerzy
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20251
Subject(s) - struct , mathematics , limiting , random graph , combinatorics , function (biology) , asymptotic distribution , discrete mathematics , graph , pure mathematics , statistical physics , physics , computer science , statistics , mechanical engineering , evolutionary biology , estimator , engineering , biology , programming language
Abstract In this article we investigate the asymptotic structure of a random mapping model with preferential attachment, T ρ n , which maps the set {1,2,…, n } into itself. The model T ρ nwas introduced in a companion article [Hansen and Jaworski, Random Struct Algorithms 33 (2008), 105–126] and the asymptotic structure of the associated directed graph G ρ nwhich represents the action of T ρ non the set {1,2,…, n } was investigated in [Hansen and Jaworski, Random Struct Algorithms 33 (2008), 105–126] and [Hansen and Jaworski, Adv Appl Probab 40 (2008), 183–205] in the case when the attraction parameter ρ > 0 is fixed as n → ∞ . In this article we consider the asymptotic structure of G ρ nwhen the attraction parameter ρ ρ ( n ) is a function of n as n → ∞ . We show that there are three distinct regimes during the evolution of G ρ n : (i) ρ n → ∞ as n → ∞ , (ii) ρ n → β > 0 as n → ∞ , and (iii) ρ n → 0 as n → ∞ . It turns out that the asymptotic structure of G ρ nis, in some cases, quite different from the asymptotic structure of well‐known models such as the uniform random mapping model and models with an attracting center. In particular, in regime (ii) we obtain some interesting new limiting distributions which are related to the incomplete gamma function. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009