## 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 ??