MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.


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|cite|improve this question
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
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

Your Answer


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

Browse other questions tagged or ask your own question.