Probability Question : 1

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 \frac{1}{2} and to node 2 with probability \frac{1}{2} . 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 X_m 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 m\geq{1} , P( X_m = m ) = \frac{1}{m}

and, for m\geq{ 2},

2) P( X_m = k ) = \frac{1}{ k(k+1) }, if 1 \leq{k} \leq{m-1}.

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: