Random Trees and General Branching Processes

Anna Rudas * , Balint Toth * , Benedek Valko * , ∘ * Institute of Mathematics, TU Budapest ∘ Alfréd Rényi Institute of Mathematics, Budapest

November 27, 2006

Abstract
We consider a tree that grows randomly in time. Each time a new vertex appears, it chooses exactly one of the existing vertices and attaches to it. The probability that the new vertex chooses vertex x   is proportional to w ( deg ( x ) )   , a weight function of the actual degree of x   . The weight function w : N → R +   is the parameter of the model.
In [3] and [9] the authors derive the asymptotic degree distribution for a model that is equivalent to the special case, 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 is new and gives full insight to the limiting structure of the tree.
Our proof is robust and we believe that the method may be used to answer several other questions related to the model. It 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.

1 Introduction

In models of randomly growing networks, the concept of preferential attachment means that when a new vertex appears, it is more likely that it attaches to an already existing vertex if the latter already has more neighbors. One of the realizations of this idea is the Barabási Albert graph. In this model, a tree grows in discrete time-steps: at each step we add a new vertex and connect it to an already existing vertex. This choice is made randomly, using probabilities exactly proportional to the degree of the existing vertices. This model reproduces phenomena observed in certain real-world networks (see [1] ), the power-law decay of the degree sequence, for example. This was proved in a mathematically precise way in [3] and, independently, in [9] .
The probability with which a newly appearing vertex chooses its neighbor could depend on the degrees of the existing vertices in a more general way. We define a weight function, w : N → R +   , and let the probability be proportional to this function of the degree. In [3] and [9] , w   is linear, their techniques strongly depend on martingales that are apparent in the system only in this special case.
General weight functions are considered in the model of Krapivsky and Redner [7] . There w ( k ) ∼ k α   , and non-rigorous results are obtained, showing the different behavior for α > 1   and α ≤ 1   . In the first region the limiting object does not have a non-trivial degree sequence:
a single dominant vertex appears which is linked to almost every other vertex, the others having only finite degree. This statement is made precise and proved rigorously in [11] . The weight functions we consider will be such that this does not happen.
Our main results are the following. We determine the asymptotic distribution of the degree sequence, which equivalently gives the limiting distribution of the degree of a (uniformly) randomly selected vertex. We also look deeper into the structure of the tree: we give the asymptotic distribution of the subtree under a randomly selected vertex. Moreover, we present the asymptotic distribution of the whole tree, seen from a randomly selected vertex.
The latter approaches are new and give full insight to the limiting structure of the random tree.
The key of our method is to place the process into continuous time in such a way that it fits in to the well-developed theory of general branching processes (see Section  5 ). The asymptotic behavior of the continuous time model gives that of the discrete time model, as pointed out in Section  3 . A special case of our model (when w   is linear) is equivalent to those studied in [3] and [9] . The robustness of our method is apparent in the fact that it gives a.s. results for a wide class of weight functions, it generalizes the results mentioned above.
The class of weight functions for which our theorems hold are not fully identified by the condition we make: it is sufficient, but we do not claim that it is also necessary.
In the present paper we do not intend to analyse all the ways we beleive this new approach can be used. We are planning to apply this technique to answer many other questions related to the randomly growing tree model.
The paper is organized as follows. We introduce the terminology and notation in the next section, then in Section  3 we define the model. We state our results in Section  4 and show the simplifications that arise in the linear case. After that, in Section  5 we give a brief introduction to the theory of general branching processes, and quote the theorems that we rely on. We present our proofs in Section  6 . We comment on the asymptotic growth of the tree in the last section.

2 Rooted ordered trees: terminology and notation

Throughout the paper it will be convenient to use genealogical phrasing. We will consider our tree evolving as a genealogical tree: where the individuals are the vertices and the parent child relations are the edges of the tree. It will be also convenient to follow the `birth orders' among children of the same parent. For this purpose we will consider our trees always as rooted ordered trees (sometimes called family trees or rooted planar trees). In the following paragraphs we introduce the (commonly known) terminology for these trees and also some additional notations needed for our theorems.

2.1 Vertices, individuals, trees

We will label the vertices of a rooted ordered tree using a subset of N : = ∞ ⋃ n = 0 Z + n , where Z + : = { 1 , 2 , . . . } , Z + 0 : = { ∅ } .   ∅   denotes the root of the tree, its children are labelled with { 1 , 2 , . . . }   , and in general the children of x = ( x 1 , x 2 , . . . , x k ) ∈ N   are labelled by ( x 1 , x 2 , . . . , x k , 1 ) , ( x 1 , x 2 , . . . , x k , 2 ) , . . .   .
Thus if a vertex has the label x = ( x 1 , x 2 , . . . , x k ) ∈ N   then this means that it is the x k t h   child of its parent, which is the x k − 1 t h   child of its own parent and so on. If x = ( x 1 , x 2 , . . . , x k )   and y = ( y 1 , y 2 , . . . , y l )   we will use the shorthanded notation x y   for the concatenation ( x 1 , x 2 , . . . , x k , y 1 , y 2 , . . . , y l )   , and with a slight abuse of notation for n ∈ Z +   we use x n   for ( x 1 , x 2 , . . . , x k , n )   .
We will identify a rooted ordered tree with the set of labels of its vertices, since this already contains the necessary information about the edges. It is clear that a G ⊂ N   may represent a rooted ordered tree if and only if ∅ ∈ G   and for each ( x 1 , x 2 , . . . , x k ) ∈ G   we have ( x 1 , x 2 , . . . , x k − 1 ) ∈ G   as well as ( x 1 , x 2 , . . . , x k − 1 ) ∈ G   , if x k > 1   .
The set of finite rooted ordered trees will be denoted by G   . We think about G ∈ G   as an oriented tree with edges pointing from parents to children. The degree of a vertex x ∈ G   is just the number of its children in G   : deg ( x , G ) : = max { n ∈ Z + : x n ∈ G } .   The n th   generation of G ∈ G   is G [ n ] : = { x ∈ G : | x | = n } , n ≥ 0 ,   where | x | = n   iff x ∈ Z + n   .
The n th   ancestor of x = ( x 1 , x 2 , . . . , x k ) ∈ N   with k ≥ n   is x n = ( x 1 , x 2 , . . . , x k − n )   if k > n   and x n = ∅   if k = n   .
The subtree rooted at a vertex x ∈ G   is: G ↓ x : = { y : x y ∈ G } ,   this is just the progeny of x   viewed as a rooted ordered tree. Also, (again with a slight abuse of notations) for an x = ( x 1 , x 2 , . . . , x n ) ∈ N   with | x | = n ≥ k   we use the notation x ↓ k = ( x n − k + 1 , x n − k + 2 , . . . , x n )   . This would be the new label given to x ∈ G   in the subtree G ↓ x k   .
Consider a G ∈ G   . An ordering s = ( s 0 , s 1 , . . . , s | G | − 1 )   of the elements of G   is called historical if it gives a possible 'birth order' of the vertices in G   , formally if for each 0 ≤ i ≤ | G | − 1   we have { s 0 , s 1 , . . . , s i } ∈ G   . The set of all historical orderings of G ∈ G   will be denoted S ( G )   . For a fixed s ∈ S ( G )   the rooted ordered trees
G ( s , i ) : = { s 0 , s 1 , . . . , s i } ⊂ G (1)
give the evolution of G   in this historical ordering s   .

2.2 Random trees

Throughout the paper we will use Greek letters to denote random elements (of various distributions) selected from N   and G   : ξ , ζ , ⋅ ⋅ ⋅ ∈ N , Γ , ϒ , ⋅ ⋅ ⋅ ∈ G   Our results will deal with some asymptotic properties of a randomly chosen vertex in a certain random tree. We will investigate the asymptotic distribution of its degree, its progeny and also the progeny of its the k th   ancestor. In order to study the latter object, we introduce rooted ordered trees with a marked vertex in generation k   : G ( k ) : = { ( G , u ) ∈ G × Z k : u ∈ G [ k ] } .   G ( 0 )   is identified with G   , since generation 0 consists of only the root, ∅   . We can use the elements of G ( k )   to describe the progeny of the k th   ancestor of a random vertex: G   is an ordered tree rooted in the k th   ancestor of the selected point and u ∈ G [ k ]   is the position of the random vertex in this tree. Clearly, if ( G , u )   describes the progeny of the k th   ancestor, then for 0 ≤ l ≤ k   the progeny of the l th   ancestor is described by ( G ↓ u l , u ↓ k − l )   .
Thus if π ( k )   is a distribution on G ( k )   which describes the progeny of the k th   ancestor of a chosen vertex, then, if l < k   , the distribution of the progeny of the l th   ancestor is: π ( k , l ) ( H , v ) : = π ( k ) ( { ( G , u ) ∈ G ( k ) : G ↓ u l = G , v = u ↓ k − l } )   The sequence π ( k )   of probability measures on G ( k )   , k = 0 , 1 , 2 , . . .   is called consistent if for any 0 ≤ l ≤ k   , the identity π ( l ) = π ( k , l )   holds.
Without presenting the precise formulation, it is clear that a consistent sequence π ( k )   of probability measures on G ( k )   gives full insight to the limiting structure of the tree as seen from a random vertex, see Remark after Theorem  2 .
We call a probability measure π   on G   steady if
∑ H ∈ G π ( H ) ∑ x ∈ H [ 1 ] 11 { H ↓ x = G } = π ( G ) . (2)
It is easy to check that in this case, for any k = 1 , 2 , . . .   , the similar identity ∑ H ∈ G π ( H ) ∑ x ∈ H [ k ] 11 { H ↓ x = G } = π ( G )   follows. Equivalently, for any bounded function φ : G → R   and any k = 0 , 1 , 2 , . . .   , E ( | Γ [ k ] | φ ( Γ ↓ ξ ) ) = E ( φ ( Γ ) ) ,   where Γ   is a random element of G   with distribution P ( Γ = G ) = π ( G )   , and on the left hand side ξ   is a random vertex selected uniformly from the k   -th generation of Γ   . (We don't have to worry about the fact that Γ [ k ]   may be empty, since in that case the expression | Γ [ k ] | φ ( Γ ↓ ξ )   is automatically 0.) Immediate consequences of this property are that the expected size of the k th   generation is 1 for any k ∈ N   (choose φ   identically 1), and therefore the expected size of the whole tree is infinite.
Backward extensions: Given a steady probability measure π   on G   , define the probability measures π ( k )   on G ( k )   , k = 0 , 1 , 2 . . .   , by π ( k ) ( G , u ) : = π ( G )   One can easily check that, due to the steadiness of the distribution π   , the sequence of probability measures π ( k )   on G ( k )   , k = 0 , 1 , 2 . . .   , is consistent.

3 The Random Tree Model

Given a weight function w : N → R +   , let X ( t )   be a Markovian pure birth process with X ( 0 ) = 0   and birth rates P ( X ( t + d t ) = k + 1 | X ( t ) = k ) = w ( k ) d t + o ( d t ) .   Let ρ : [ 0 , ∞ ) ↦ ( 0 , ∞ ]   be the density of the point process corresponding to the pure birth process X ( t )   and ρ ^ : ( 0 , ∞ ) → ( 0 , ∞ ]   the (formal) Laplace transform of ρ   :
ρ ^ ( λ ) : = ∫ 0 ∞ e − λ t ρ ( t ) d t = ∑ n = 0 ∞ n ∏ i = 0 w ( i ) λ + w ( i ) . (3)
The rightmost expression of ρ ^ ( λ )   is easily computed, given the fact that the intervals between successive jumps of X ( t )   are independent exponentially distributed random variables of parameters w ( 0 ) , w ( 1 ) , w ( 2 ) , . . .   respectively. Let
λ ̲ : = inf { λ > 0 : ρ ^ ( λ ) < ∞ } . (4)
Throughout this paper we impose the following condition on the weight function w   :
lim λ ↘ λ ̲ ρ ( λ ) > 1 . (M)
We are now ready to define our randomly growing tree ϒ ( t )   which will be a continuous time, time-homogeneous Markov chain on the countable state space G   , with initial state ϒ ( 0 ) = { ∅ }   .
The jump rates are the following: if for a t ≥ 0   we have ϒ ( t ) = G   then the process may jump to G ∪ { x k }   with rate w ( deg ( x , G ) )   where x ∈ G   and k = deg ( x , G ) + 1   . This means that each existing vertex x ∈ ϒ ( t )   `gives birth to a child' with rate w ( deg ( x , ϒ ( t ) ) )   independently of the others.
Note that condition  M implies ∑ k = 0 ∞ 1 w ( k ) = ∞   and hence it follows that the Markov chain ϒ ( t )   is well defined for t ∈ [ 0 , ∞ )   , it does not blow up in finite time.
We define the total weight of a tree G ∈ G   as W ( G ) : = ∑ x ∈ G w ( deg ( x , G ) ) .   Described in other words, the Markov chain ϒ ( t )   evolves as follows: assuming ϒ ( t − ) = G   , at time t   a new vertex is added to it with total rate W ( G )   which is attached with an oriented edge (pointing towards the newly added vertex) to the already existing vertex x ∈ G   with probability w ( deg ( x , G ) ) ∑ y ∈ G w ( deg ( y , G ) ) .   Therefore, if we only look at our process at the stopping times when a new vertex is just added to the randomly growing tree: T n : = inf { t : | ϒ ( t ) | = n + 1 }   then we get the discrete time model: ϒ ( T n )   has the same distribution as the discrete time model at time n   .
It will sometimes be convenient to refer to the vertices in the order of their birth, not their genealogical code: let { η k } = ϒ ( T k ) \ ϒ ( T k − 0 )   denote the vertex that appeared at T k   . Of course we will always have η 0 = ∅   and η 1 = 1   .

4 Results

4.1 Statement of results

From condition  M it follows that the equation ρ ^ ( λ ) = 1   has a unique root λ *   .
Now we are ready to state our first theorem.
Theorem 1. Consider a weight function w   satisfying condition  M and let λ *   be defined as above. Consider a bounded function φ : G → R   . Then the following limit holds almost surely: lim t → ∞ 1 | ϒ ( t ) | ∑ x ∈ ϒ ( t ) φ ( ϒ ( t ) ↓ x ) = λ * ∫ 0 ∞ e − λ * t E ( φ ( ϒ ( t ) ) ) d t .  
From Theorem  1 several statements follow, regarding the asymptotic behavior of our random tree as seen from a randomly selected vertex ζ   , chosen uniformly from ϒ ( t )   . As typical examples we determine the asymptotic distribution of the number of children, respectively, that of the whole subtree under the randomly chosen vertex, its k th   ancestor, respectively. That is: the asymptotic distribution of deg ( ζ , ϒ ( t ) ) ∈ N   , ϒ ( t ) ↓ ζ ∈ G   and ( ϒ ( t ) ↓ ζ ( k ) , ζ ↓ k ) ∈ G ( k )   .
In order to formulate these consequences of Theorem  1 we need to introduce some more notation. Let G ∈ G   and one of its historical orderings s = ( s 0 , s 1 , . . . , s | G | − 1 ) ∈ S ( G )   be fixed. The historical sequence of total weights are defined as
W ( G , s , i ) : = W ( G ( s , i ) ) (5)
for 0 ≤ i ≤ | G | − 1   while the respective weights of the appearing vertices are defined as
w ( G , s , i ) : = w ( deg ( ( s i ) 1 , G ( s , i − 1 ) ) ) . (6)
for 1 ≤ i ≤ | G | − 1   . Since deg ( ( s i ) 1 , G ( s , i − 1 ) )   is the degree of s i   's parent just before s i   appeared, w ( G , s , i )   is the rate with which our random tree process jumps from G ( s , i − 1 )   to G ( s , i )   .
Given the weight function w : N → R +   satisfying condition ( M ) and λ *   defined as before define
p w ( k ) : = λ * λ * + w ( k ) k − 1 ∏ i = 0 w ( i ) λ * + w ( i ) , (7)
π w ( G ) : = ∑ s ∈ S ( G ) λ * λ * + W ( G ) | G | − 2 ∏ i = 0 w ( G , s , i + 1 ) λ * + W ( G , s , i ) . (8)
Theorem 2. Consider a weight function w   which satisfies condition (M) and let λ *   be defined as before. Then the following limits hold almost surely:
  • (a) For any fixed k ∈ N   lim t → ∞ | { x ∈ ϒ ( t ) : deg ( x , ϒ ( t ) ) = k } | | ϒ ( t ) | = p w ( k ) .  
  • (b) For any fixed G ∈ G   lim t → ∞ | { x ∈ ϒ ( t ) : ϒ ( t ) ↓ x = G } | | ϒ ( t ) | = π w ( G ) .  
  • (c) For any fixed ( G , u ) ∈ G ( k )   lim t → ∞ | { x ∈ ϒ ( t ) : ( ϒ ( t ) ↓ x ( k ) , x ↓ k ) = ( G , u ) } | | ϒ ( t ) | = π w ( G ) .  
Furthermore, the functions p w , π w   are probability distributions on N   and G   , respectively, and π w   is steady (i.e. identity  2 holds).
Remarks. 1. Parts (a), (b) and (c) of Theorem  2 , in turn, give more and more information about the asymptotic shape of the randomly growing tree ϒ ( t )   , as seen from a random vertex ζ   chosen with uniform distribution. Part (a) identifies the a.s. limit as t → ∞   , of the degree distribution of ζ   . Part (b) identifies the a.s. limit as t → ∞   , of the distribution of the progeny of ζ   . Finally, part (c) does the same for the distribution of the progeny of the k th   ancestor of the randomly selected vertex with the position of this vertex marked.
2. From part (c) it is easy to derive the asymptotic distribution of the progeny of the k th   ancestor of the randomly selected vertex (as a rooted ordered tree without any marked vertices): lim t → ∞ | { x ∈ ϒ ( t ) : ϒ ( t ) ↓ x ( k ) = G } | | ϒ ( t ) | = π w ( G ) | G [ k ] | .   The limit is the size-biased version of π w ( G )   , with the biasing done by the size of the k th   generation.
3. Since the distribution π w   is steady, part (c) identifies the asymptotic distribution of the whole family tree of the randomly selected vertex ζ   (relatives of arbitrary degree included).
Hence asymptotically, as t → ∞   , the tree ϒ ( t )   viewed from a random vertex ζ   will have the following structure (we omit the precise formulation):
– there exists an infinite path of ancestors ζ 1 , ζ 2 , ζ 3 , . . .   `going back in time', – we have finite ordered random trees rooted at each vertex of this path, – the tree rooted at ζ k   with the position of ζ   marked on it has distribution π ( k ) w   on G ( k )   where π ( k ) w ( G , u ) = π w ( G )   .

4.2 Linear weight function

In the linear case w ( k ) = k + β   ( β > 0 )   all computations are rather explicit. In this case the asymptotic degree distribution p w   (computed in [3] , [9] ) is reproduced, of course. But even in this simplest case the asymptotic distribution π w   of the subtree under a randomly selected vertex seems to be new.
For sake of completeness, in the rest of this section we perform these (explicit and straightforward) computations for the linear case. Multiplying the rate function with a positive constant only means the rescaling of time in our model thus it is enough to consider w ( k ) = k + β   (with β > 0   ). In this case it is straightforward to compute that condition (M) holds, ρ ^ ( λ ) = β λ − 1   , λ ̲ = 1   and λ * = 1 + β   . Thus both Theorems  1 and  2 hold.
For the asymptotic degree distribution we get p w ( k ) = ( 1 + β ) ( k − 1 + β ) k ( k + 1 + 2 β ) k + 1 ,   where we used the shorthanded notation ( x ) k : = k − 1 ∏ i = 0 ( x − i ) = Γ ( x + 1 ) Γ ( x − k + 1 ) , k = 0 , 1 , 2 , . . . .   For the calculation of π w ( G )   first we show that the sum which defines it contains identical elements. In order to avoid heavy notation, during the following computations we will use n : = | G | − 1   and deg ( x )   instead of deg ( x , G )   .
Clearly, for any s ∈ S ( G )   n − 1 ∏ i = 0 w ( G , s , i + 1 ) = ∏ x ∈ G ( deg ( x ) − 1 ∏ j = 0 w ( j ) ) = ∏ x ∈ G ( deg ( x ) − 1 + β ) deg ( x ) .   (Actually, the first equality holds for every weight function w   .) It is also easy to see that for any G ∈ G   W ( G ) = ∑ x ∈ G ( deg ( x ) + β ) = | G | ( 1 + β ) − 1 ,   thus for any s ∈ S ( G )   λ * λ * + W ( G ) n − 1 ∏ i = 0 1 λ * + W ( G , s , i ) = 1 ( 1 + β ) n ( n + 2 − ( 1 + β ) − 1 ) n + 1 .   Therefore π w ( G ) = | S ( G ) | ∏ x ∈ G ( deg ( x ) − 1 + β ) deg ( x ) ( 1 + β ) n ( n + 2 − ( 1 + β ) − 1 ) n + 1 .   In the β = 1   case (i.e. if we consider random tree proposed in [1] ) the previous calculations give p w ( k ) = 4 ( k + 1 ) ( k + 2 ) ( k + 3 )   and π w ( G ) = 2 | S ( G ) | ( 2 | G | + 1 ) ! ! ∏ x ∈ G deg ( x ) ! .   The value of | S ( G ) |   cannot be written as the function of degrees of G   only, but one can compute it using the values | G ↓ x |   for x ∈ G   . For a given G   and x = ( x 1 , x 2 , . . . , x n ) ∈ G   let us introduce the following notations (these will not be used in the other parts of the paper):
B ( x ) : = { y ∈ G : y = ( x 1 , x 2 , . . . , x n − 1 , k ) , k > x n } ,
a ( x ) : = max ( | G ↓ x | − 1 , 1 ) , b ( x ) : = max ( ∑ y ∈ B ( x ) | G ↓ x | , 1 ) .
It is a simple exercise to prove that for a G ∈ G   with | G | > 1   | S ( G ) | = ( | G | − 2 ) ! ∏ x ∈ G , x ≠ ∅ a ( x ) − 1 b ( x ) − 1 .   The proof is left to the reader.

5 Branching Processes

The random tree model, defined in continuous time, has the big advantage that it fits into the framework of the well-established theory of general branching processes. We give a brief introduction to the fundamentals and state the theorems that we rely on in our proofs.
We do not give a broad survey on the most general types of branching processes here, we choose to focus on the results which may be applied to our process. For more details see the monograph [4] or the papers [5] , [10] , [12] and the references therein. For a survey on branching processes, trees and superprocesses, see [8] .
In the case of a general branching process, there is a population in which each individual reproduces at ages according to i.i.d. copies of a random point process ξ   on [ 0 , ∞ )   . We denote by ξ ( t )   the ξ   -measure of [ 0 , t ]   , this the random number of children an individual has up to time t   .
The individuals in the population are labelled with the elements of N   , as described in Section  3 (see  2.1 ). The basic probability space is ( Ω , A , P ) = ∏ x ∈ N ( Ω x , A x , P x ) ,   where ( Ω x , A x , P x )   are identical spaces on which ξ x   are distributed like ξ   .
For each x ∈ N   there is a . ↓ x   shift defined on Ω   by ( ω ↓ x ) y = ω x y ,   in plain words, ω ↓ x   is the life of the progeny of x   , regarding x   as the ancestor.
The birth times σ x   of the individuals are defined in the obvious way: σ 0 = 0   and if x ′ = x n   with n ∈ Z +   then
σ x ′ = σ x + inf { t : ξ x ( t ) ≥ n } . (9)
The branching process is often counted by a random characteristic, this can be any real-valued process { Φ : R × Ω → R }   . For each individual x   , Φ x   is defined by Φ x ( t , ω ) = Φ ( t , ω ↓ x ) ,   in plain words Φ x ( t )   denotes the value of Φ   evaluated on the progeny of x   , regarding x   as the ancestor, at the time when x   is of age t   . We can think about Φ x ( t )   as a `score' given to x   when its age is t   . With this, Z t Φ = ∑ x ∈ N Φ x ( t − σ x )   is the branching process counted by the random characteristic Φ   (the `total score' of the population at time t   ).
For our applications we only consider random characteristics which are 0 for t < 0   and for t ≥ 0   they are equal to a bounded deterministicfunction of the rooted tree.
This means that only those individuals contribute to Z t Φ   which are born up to time t   and their contribution is a deterministic function of their progeny tree. (Random characteristics may be defined in a more general way, see e.g. [4] , [5] .) One of the important examples is Φ ( t ) = 11 { t ≥ 0 }   when Z t Φ   is just the total number of individuals born up to time t   .
The Laplace-transform of d ξ ( t )   will be of great importance, we denote this random variable by:
ξ ^ ( λ ) : = ∫ 0 ∞ e − λ t d ξ ( t ) . (10)
We shall be interested in supercritical, Malthusian processes, meaning that there exists a finite 0 < λ * < ∞   (the so-called Malthusian parameter) for which
E ξ ^ ( λ * ) = 1 , (11)
and also
κ = − ∂ λ ( E ξ ^ ( λ ) ) | λ = λ * = E ∫ 0 ∞ t e − λ * t d ξ ( t ) < ∞ . (12)
(The last property means that the process is Malthusian and the first means that it is supercritical.) Also, we require the reproduction to be non-lattice, which means that the jumps of ξ ( t )   cannot be supported by any lattice { 0 , d , 2 d , . . . }   , d > 0   with probability one.
We quote here a weaker form of Theorem 6.3 from [10] , using its extension which appears in Section 7 of the same paper. This way the conditions of the original theorem are fulfilled automatically.
Theorem A (Nerman, [10] ). Consider a supercritical, Malthusian branching process with Malthusian parameter λ *   , counted by two random characteristics Φ ( t )   and Ψ ( t )   which have the properties described above (i.e. they are 0 for t < 0   and a deterministic bounded function of the progeny tree for t ≥ 0   ). Suppose that there exists a λ ̲ < λ *   for which E ξ ^ ( λ ̲ ) < ∞ .   Then almost surely
Z t Φ Z t Ψ → Φ ^ ( λ * ) Ψ ^ ( λ * ) as t → ∞ , (13)
where Φ ^ ( λ ) = ∫ 0 ∞ exp ( − λ t ) E ( Φ ( t ) ) d t   .
For a reader interested in how the Malthusian parameter and Φ ^ ( λ )   play a role in the theory, we give a short indication. This part may be skipped without any confusion.
The key observation is the so-called basic decomposition, namely that
Z t Φ = Φ ( t ) + ∑ j ∈ N Z t − σ j Φ j . (14)
The advantage of this formula is that if we know the sequence ( σ j ) j ∈ Z +   (all the birth-times of the children of the root), then Z t − σ j Φ j   has the same conditional distribution as Z t − σ j Φ   .
Therefore, using the notation m t Φ = E Z t Φ   , taking expectation on both sides of  14 in two steps (first conditionally on ( σ j ) j ∈ Z +   , then taking expectation regarding ( σ j ) j ∈ Z + )   , we get
m t Φ = E ( Φ ( t ) ) + ∫ 0 t m t − s Φ d μ ( s ) , (15)
where we used the notation μ ( t ) = E ξ ( t )   . Taking the Laplace transform of both sides,
m ^ ( λ ) = Φ ^ ( λ ) + m ^ ( λ ) μ ^ ( λ ) , (16)
so formally
m ^ ( λ ) = Φ ^ ( λ ) 1 − μ ^ ( λ ) . (17)
Note that μ ^ ( λ ) = E ξ ^ ( λ )   . This shows that if there is a positive interval below λ *   where the Laplace transform is finite, then 1 / ( 1 − μ ^ ( λ ) )   has a simple pole at λ *   (it is easy to check that μ ^ ′ ( λ * ) < 0   and μ ^ ′ ′ ( λ * ) > 0   ). So taking series expansion and inverse Laplace transform results that
m t Φ = 1 κ Φ ^ ( λ * ) e λ * t + o ( e λ * t ) , (18)
where κ   is the finite constant defined in ( 12 ). This means that the ratio of the expectations of Z t Φ   and Z t Ψ   indeed tends to Φ ^ ( λ * ) Ψ ^ ( λ * )   . To get the almost sure convergence of Z t Φ Z t Ψ   to the same limit needs a lot more work and of course its proof is more elaborate (see [10] for example).

6 Proofs

  • Proof of Theorem  1 . Consider the continuous time branching process where the reproduction process ξ ( t )   is the Markovian pure birth process X ( t )   , with rate function w   , described at the beginning of Section  3 .
    Clearly, the time-evolution of the population has the same distribution as the evolution of the continuous time Random Tree Model corresponding to the weight function w   . The vertices are the respective individuals and edges are the parent-child relations.
    It is also not hard to see that the function E ξ ^ ( λ )   for the branching process is the same as ρ ^ ( λ )   which means that by condition (M) we may apply Theorem A with appropriate random characteristics. Given any bounded function φ : G → R   , setting the characteristics Φ , Ψ   as Φ ( t ) : = φ ( ϒ ( t ) ) 11 { t ≥ 0 }   and Ψ ( t ) : = 11 { t ≥ 0 }   we get exactly the statement of Theorem  1 .
  • Proof of Theorem  2 . (a) Apply Theorem  1 with the function φ ( G ) : = 11 { deg ( ∅ , G ) = k } .   This gives that lim t → ∞ | { x ∈ ϒ ( t ) : deg ( x , ϒ ( t ) ) = k } | | ϒ ( t ) | = λ * ∫ 0 ∞ e − λ * t P ( deg ( ∅ , ϒ ( t ) ) = k ) d t ,   almost surely. By the definition of σ k   (see ( 9 )): P ( deg ( ∅ , ϒ ( t ) ) = k ) = P ( σ k < t ) − P ( σ k + 1 < t ) .   Since λ * ∫ 0 ∞ e − λ * t P ( σ k < t ) d t = E ( e − λ * σ k ) ,   and σ k   is the sum of independent exponentially distributed random variables with parameters w ( 0 ) , w ( 1 ) , . . . , w ( k − 1 )   , we get λ * ∫ 0 ∞ e − λ * t P ( deg ( ∅ , ϒ ( t ) ) = k ) d t = λ * λ * + w ( k ) k − 1 ∏ i = 0 w ( i ) λ * + w ( i ) .   This completes the proof of part (a) of the Theorem. Using the identity p w ( k ) = λ * ∫ 0 ∞ e − λ * t P ( deg ( ∅ , ϒ ( t ) ) = k ) d t ,   and the fact that | ϒ ( t ) |   is finite for every t   with probability 1 it is straightforward to prove that p w   is indeed a probability distribution on N   .
    (b) Let G ∈ G   be fixed and denote n = | G | − 1   . We apply Theorem  1 with φ ( H ) = 11 ( H = G )   . We need to compute λ * ∫ 0 ∞ e − λ * t P ( ϒ ( t ) = G ) d t .   Consider the following random stopping times:
    τ G : = sup { t ≥ 0 : ϒ ( t ) ⊆ G } ,
    τ G ′ : = sup { t ≥ 0 : ϒ ( t ) ⊊ G } .
    That is: τ G   is the birth time of the first vertex not in G   , while τ G ′   is the minimum of τ G   and the time when we first have ϒ ( t ) = G   , if the latter ever happens. Since P ( ϒ ( t ) = G ) = P ( ϒ ( t ) ⊆ G ) − P ( ϒ ( t ) ⊊ G ) = P ( t < τ G ) − P ( t < τ G ′ ) ,   we get that
    λ * ∫ 0 ∞ e − λ * t P ( ϒ ( t ) = G ) d t = E ( e − λ * τ G ′ − e − λ * τ G )
    = E ( ( e − λ * τ G ′ − e − λ * τ G ) 11 { τ G ′ < τ G } ) .
    Note that by the definition we always have τ G ′ ≤ τ G   . The event { τ G ′ < τ G }   means that there is a t   when ϒ ( t ) = G   . On this event τ G ′   gives the time when we first have ϒ ( t ) = G   and τ G   gives the appearance of the next vertex. Given the event { τ G ′ < τ G }   , the conditional distribution of τ G − τ G ′   is exponential with parameter W ( G )   and it is (conditionally) independent of τ G ′   . This leads to E ( ( e − λ * τ G ′ − e − λ * τ G ) 11 { τ G ′ < τ G } ) = λ * λ * + W ( G ) E ( e − λ * τ G ′ 11 { τ G ′ < τ G } ) .   Now, it is clear that the following two events are actually the same { τ G ′ < τ G } = { ( η 0 , . . . , η n ) = ( s 0 , . . . , s n ) for some s ∈ S ( G ) } .   This implies that
    E ( e − λ * τ G ′ 11 { τ G ′ < τ G } )
    = ∑ s ∈ S ( G ) E ( e − λ * T n 11 { ( η 0 , . . . , η n ) = ( s 0 , . . . , s n ) } ) .
    For T n   see  3 and the definition below it. Given s ∈ S ( G )   fixed P ( ( η 0 , . . . , η n ) = ( s 0 , . . . , s n ) ) = n − 1 ∏ i = 0 w ( G , s , i + 1 ) W ( G , s , i ) .   (See  3 ,  5 and  6 for the definitions.) Also, if s ∈ S ( G )   is fixed then conditionally on the event { ( η 0 , . . . , η n ) = ( s 0 , . . . , s n ) }   the random variables T k + 1 − T k   , k = 0 , 1 , . . . , n − 1   , are independent and exponentially distributed with parameters W ( G , s , k )   , k = 0 , 1 , . . . , n − 1   , respectively. This is an easy exercise: it may be proved by using the `lack of memory' of the exponential distribution and the fact that the minimum of independent exponentially distributed random variables with parameters ν 1 , ν 2 , . . . , ν l   is also exponentially distributed with parameter ∑ i = 1 l ν i   . Hence it is straightforward to get E ( e − λ * T n 11 { ( η 0 , . . . , η n ) = ( s 0 , . . . , s n ) } ) = n − 1 ∏ i = 0 w ( G , s , i + 1 ) λ * + W ( G , s , i ) .   Collecting our previous calculations part (b) of Theorem  2 follows.
    Using similar considerations as in the end of the proof of part (a) it is apparent that π w   is a probability distribution on G   .
    (c) This is straightforward since for any H ∈ G   and ( G , u ) ∈ G ( k )   we have
    | { x ∈ H : ( H ↓ x ( k ) , x ↓ k ) = ( G , u ) } | = | { x ∈ H : H ↓ x = G } | .
    The statement now follows from part (b).
    The only thing left to prove is that π w   satisfies ( 2 ), i.e. it is steady. First observe, that if G 0 ∈ G   is fixed and ζ   is a uniformly chosen random vertex in G 0   then the distribution of Γ : = ( G 0 ) ↓ ζ   (which is a probability distribution on G   ) is steady. (This follows by simple counting.) Equation ( 2 ) is linear in π   , therefore mixtures of steady distributions are also steady. Thus, if ζ   is a uniformly chosen random vertex in ϒ ( t )   then the distribution of ϒ ( t ) ↓ ζ   (which is a random probability distribution on G   ) is also steady. By part (b) with probability one these distributions converge (in distribution) to π w   and from this an easy consideration shows that π w   must satisfy ( 2 ).

7 Asymptotic growth

In our theorems we determined the asymptotic ratio of vertices in ϒ ( t )   satisfying certain properties. It is also natural to ask if one can prove results about the asymptotic number of the respective vertices. As we have seen, this essentially requires to study the asymptotic behavior of Z t Φ   for a suitable random characteristic Φ   . This has been done in the framework of general branching processes, we shall give a short overview of the relevant results.
We have already seen that
E ( e − λ * t Z t Φ ) → 1 κ Φ ^ ( λ * ) , (19)
where κ   is the constant defined in ( 12 ). Thus we need to divide Z t Φ   by e λ * t   to get something non-trivial. Let us quote a weaker form of Theorem 5.4 of [10] .
Theorem B (Nerman, [10] ). Consider a supercritical, Malthusian branching process with Malthusian parameter λ *   . Suppose that condition (M) holds and Φ   is a random characteristic with properties described in Section  4 . Then almost surely e − λ * t Z t Φ → 1 κ Φ ^ ( λ * ) Θ , as t → ∞ ,   where Θ   is a random variable not depending on Φ   .
The necessary and sufficient condition for the random variable Θ   to be a.s. positive is the so-called x log x   property of the reproduction process ξ   :
E ( ξ ^ ( λ * ) log + ξ ^ ( λ * ) ) < ∞ . (L)
We quote Theorem 5.3 of [5] .
Theorem C (Jagers-Nerman, [5] ). Consider a supercritical, Malthusian branching process with Malthusian parameter λ *   . If condition ( L ) holds then Θ > 0   a.s. and E ( Θ ) = 1   ; otherwise Θ = 0   a.s.
Remark. This theorem is the generalization of the Kesten-Stigum theorem, which states this fact for Galton-Watson processes (see [6] ).
Theorem B applies for the random tree model if condition (M) is fulfilled. We do not intend to identify the necessary and sufficient condition on the weight function w   which would guarantee that the corresponding reproduction process possesses property (L). Still it is worth pointing out that if w ( k ) → ∞   as t → ∞   , then this property holds, this by Theorem C, Θ   is a.s. positive.
Lemma 1. If a weight function w   satisfies condition (M) and w ( n ) → ∞   , as n → ∞   , then the corresponding branching process satisfies condition (L).
  • Proof. We will prove the existence of the second moment of ξ ^ ( λ * )   from which condition (L) trivially follows. Since ξ ^ ( λ * ) = ∑ i = 1 ∞ e − λ * σ k   , we need
    E ( ∑ k = 1 ∞ e − λ * σ k ) 2 < ∞ . (20)
    The random variables σ k + 1 − σ k   are independent exponentials for k = 0 , 1 , 2 , . . .   with parameters w ( 0 ) , w ( 1 ) , . . .   , respectively, thus a simple computation yields that the expression in ( 20 ) is equal to
    − ρ ^ ( 2 λ * ) + 2 ∑ i = 0 ∞ ∑ j = 0 i ( j ∏ l = 0 w ( l ) 2 λ * + w ( l ) i ∏ l = j + 1 w ( l ) λ * + w ( l ) ) .
    Transforming the double sum on the right, we get
    ∑ i = 0 ∞ ( i ∏ l = 0 w ( l ) λ * + w ( l ) ) ∑ j = 0 i j ∏ l = 0 λ * + w ( l ) 2 λ * + w ( l ) ≤ sup i ∑ j = 0 i j ∏ l = 0 λ * + w ( l ) 2 λ * + w ( l )
    where we also used ρ ^ ( λ * ) = 1   . On the other hand,
    ∑ j = 0 i j ∏ l = 0 λ * + w ( l ) 2 λ * + w ( l ) = ∑ j = 0 i j ∏ l = 0 w ( l ) λ ̲ + w ( l ) j ∏ l = 0 ( λ ̲ + w ( l ) ) ( λ * + w ( l ) ) w ( l ) ( 2 λ * + w ( l ) ) .
    Since w ( l ) → ∞   and λ ̲ < λ *   , we have
    ( λ ̲ + w ( l ) ) ( λ * + w ( l ) ) w ( l ) ( 2 λ * + w ( l ) ) < 1
    if l   is large enough. This leads to ∑ j = 0 i j ∏ l = 0 λ * + w ( l ) 2 λ * + w ( l ) < K ∑ j = 0 i j ∏ l = 0 w ( l ) λ ̲ + w ( l ) < K ρ ^ ( λ ̲ ) < ∞ ,   by condition (M) which completes the proof of the lemma.
The distribution of Θ   is usually hard to determine from the weight function w   , however, one can characterize its moment generating function φ ( u ) = E e − u Θ   . Using the idea of the basic decomposition ( 14 ) one can write the following equation for f ( u , t ) : = E e − u | ϒ ( t ) |   f ( u , t ) = e − u E ∏ j ≥ 1 f ( u , t − τ j ) .   By Theorem 4
φ ( u ) = lim t → ∞ f ( u e − λ * t , t ) (21)
which gives
φ ( u ) = E ∏ j ≥ 1 φ ( u e − λ * τ j ) . (22)
It can be proved that this equation characterizes φ   as there is no other bounded function satisfying it with a right derivative − 1   at 0. (See Theorem 6.8.3 in [4] .) In the linear case ( w ( k ) = k + β   ) the distribution of Θ   may be explicitly calculated.
Using the fact that | ϒ ( t ) |   is now a Markov process (which is an easy exercise to prove) and applying standard martingale techniques one can derive a partial differential equation for f ( u , t )   . Solving this pde and using the limit ( 21 ) we get the momentum generating function of ω   from which one can identify the distribution of Θ   as a Gamma distribution with parameters ( β β + 1 , β β + 1 )   .
Acknowledgements: We are thankful to J-F. Le Gall for having called our attention to his review paper [8] and the reference [5] therein. This work was partially supported by the Hungarian Scientific Research Fund (OTKA) grants no. T037685 and TS40719. References

  1. Barabási, A.-L., Albert, R., Emergence of scaling in random networks, Science, 286 (1999), 509-512
  2. Bollobás, B., Mathematical results on scale-free random graphs, in: S. Bornholdt and H.G. Schuster, editors, Handbook of Graphs and Networks, pp 1-34, Wiley, 2002.
  3. Bollobás, B., Riordan, O., Spencer, J., Tusnády, G., The degree sequence of a scale-free random graph process, Random Structures and Algorithms, 18 (2001), 279-290.
  4. Jagers, P., Branching Processes with Biological Applications, Wiley, 1975
  5. Jagers, P., Nerman, O., The growth and composition of branching populations, Adv. Appl. Prob., 16, (1984) 221-259
  6. Kesten, H. Stigum, B., A limit theorem for multidimensional Galton-Watson processes. Ann. Math. Statist. 37 (1966) 1211-1223
  7. Krapivsky, P. L., Redner, S., Organization of Growing Random Networks, Physical Review E, 63, 066123 (2001)
  8. Le Gall, J-F., Processus de branchement, arbres et superprocessus, in: Pier J-P., editor, Development of mathematics 1950-2000, pp 763-793, Birkhäuser, 2000.
  9. Móri, T., On random trees, Studia Sci. Math. Hungar., 39 (2002),143155.
  10. Nerman, O., On the convergence of supercritical (C-M-J) branching processes, Z. Wahrscheinlichkeitstheorie verw. Geb., 57, (1981), 365-395
  11. Olivieri, R., Spencer, J., Connectivity transitions in networks with super-linear preferential attachment, Internet Mathematics, to appear
  12. Olofsson, P., The x log x   condition for general branching processes, J. Appl. Prob., 35, (1998) 537-544

Anna Rudas & Balint Toth Institute of Mathematics Technical University Budapest Egry Jozsef u. 1.
H-1111 Budapest, Hungary {rudasa,balint}@math.bme.hu Benedek Valko Renyi Inst. of Math. Hung. Acad. of Sciences Realtanoda u. 13-15 H-1053 Budapest, Hungary valko@renyi.hu