Local properties of random mappings with exchangeable in-degrees

摘要

In this paper we investigate the 'local' properties of a random mapping model, T-n((D) over cap), which maps the set {1, 2, ..., n} into itself. The random mapping T-n(D), which was introduced in a companion paper (Hansen and Jaworski (2008)), is constructed using a collection of exchangeable random variables (D) over cap (1), ..., (D) over cap (n) , which satisfy Sigma(n)(i=1) (D) over cap (i) = n. in the random digraph, G(n)((D) over cap), which represents the mapping T-n((D) over cap), the in-degree sequence for the vertices is given by the variables (D) over cap (1), (D) over cap (2), ..., (D) over cap (n), and, in some sense, G(n)((D) over cap) 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 G(n)((D) over cap)-for example, the numbers of predecessors and successors of v in G We show that the distribution of several variables associated with the local structure of G(n)((D) over cap) can be expressed in terms of expectations of simple functions of (D) over cap (1), (D) over cap (2), ..., (D) over cap (n), We also consider two special examples of T-n((D) over cap) which correspond to random mappings with preferential and anti-preferential attachment, and determine, for these examples, exact n and asymptotic distributions for the local structure variables considered in this paper. These distributions are also of independent interest.