1
$\begingroup$

(1)

Consider the following method of generating a random tree with $n$ nodes.

First expand the root node into two branches.

Then expand one of the two terminal nodes at random.

At time $k$, choose one of the $k - 1$ terminal nodes according to a uniform distribution and expand it. Continue until $n$ terminal nodes have been generated.

(2)

Consider another generating method.

First choose an integer $N_1$ uniformly distributed on {$1,2,...,n-1$}. Then we expand the root node into to branches with $N_1$ and $n-N_1$ writing under them.

Then do the same thing recursively until some node become 2 and expand into 1 and 1.

I was told such to generating method will yield the same probability distribution. The hint say to use a Polya's urn model to explain it. But I'm confused.

Anyone can explain it to me?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Looks like homework. Is it? $\endgroup$
    – Brendan McKay
    Commented Aug 18, 2012 at 7:29
  • $\begingroup$ It is from the exercises in a Information Theory book. I'm studying it by myself. $\endgroup$
    – user18717
    Commented Aug 18, 2012 at 9:52
  • 1
    $\begingroup$ More specific hint: what is the distribution of the number of nodes in the left side of the tree under both distributions? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Aug 18, 2012 at 16:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .