Consider the set { 1, 2 ,…,* n*} of *n *nodes that attach to each other in the following way. Node 2 attaches to node 1. Node 3 attaches to node 1 with probability and to node 2 with probability . In general, node *k *(* k *= 2, 3 ,..,* n*)* *attaches to a uniformly selected node from the previous ones, independently of previous attachments. The process of *n *steps produces a random rooted tree in which each vertex is one of the nodes and such that *j *being attached to *i *means that *j *is a child of *i*. The resulting trees are called *recursive trees*. Let *size *denote the number of vertices in the recursive tree.

Let be a random variable which denotes the size of the subtree of a randomly chosen vertex in recursive tree of size *m*. Show that

1) For , P( = *m *) =

and, for * *,

2) P( = *k ** *) = , if .

PS:: This result is proved in following paper : ” Breakage and Restoration in Recursive Trees ” . I am looking for different approach. Any Ideas ??

### Like this:

Like Loading...

This entry was posted on November 5, 2009 at 1:17 pm and is filed under Probability Questions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply