Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
Looks like homework. Is it? –  Brendan McKay Aug 18 '12 at 7:29
    
It is from the exercises in a Information Theory book. I'm studying it by myself. –  user18717 Aug 18 '12 at 9:52
1  
More specific hint: what is the distribution of the number of nodes in the left side of the tree under both distributions? –  Ori Gurel-Gurevich Aug 18 '12 at 16:48
    
I got it! Thank you, Ori! –  user18717 Aug 19 '12 at 5:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.