Using Random5 function ( which returns a integer *k* [1,5] with probability ) , design Random7 function ( which returns a integer *k* [1,7] with probability ).

## Archive for the ‘Probability Questions’ Category

### Probability Question : 2

November 21, 2009### Probability Question : 1

November 5, 2009Consider 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 ??