Random Trees and General Branching Processes

Details Random Trees and General Branching Processes Random Trees and General Branching Processes

2005-03-31

arxiv.org/abs/math/0503728v2

Mathematics

Probability

Added references and minor changes, corrected typos. Accepted for publication in Random Structures and Algorithms. 18 pages, n

Scientific paper

We consider a model of random tree growth, where at each time unit a new vertex is added and attached to an already existing vertex chosen at random. The probability with which a vertex with degree $k$ is chosen is proportional to $w(k)$, where the weight function $w$ is the parameter of the model. In the papers of B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, and, independently, Mori, the asymptotic degree distribution is obtained for a model that is equivalent to the special case of ours, when the weight function is linear. The proof therein strongly relies on the linear choice of $w$. We give the asymptotical degree distribution for a wide range of weight functions. Moreover, we provide the asymptotic distribution of the tree itself as seen from a randomly selected vertex. The latter approach gives greater insight to the limiting structure of the tree. Our proof relies on the fact that considering the evolution of the random tree in continuous time, the process may be viewed as a general branching process, this way classical results can be applied.

Affiliated with

Also associated with

No associations

Rating

Random Trees and General Branching Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Trees and General Branching Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Trees and General Branching Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-721035