Archive for the ‘Probability Questions’ Category

Probability Question : 2

November 21, 2009

Using Random5 function ( which returns a integer k \in [1,5]  with probability \frac{1}{5} ) , design Random7 function ( which returns a integer k \in [1,7]  with probability \frac{1}{7} ).


Probability Question : 1

November 5, 2009

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