A random mapping with preferential attachment

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_n^? was 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_n^? which represents the action of T_n^? on 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 ? 8. In this article we consider the asymptotic structure of G_n^? when the attraction parameter ? = ?(n) is a function of n as n ? 8. We show that there are three distinct regimes during the evolution of G _n^? (i) ?n ? 8 as n ? 8, (ii)?n ? ß > 0 as n ? 8, and (iii) ?n ? 0 as n ? 8. It turns out that the asymptotic structure of G _n^? is, 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.