# The distribution of the uniform random tree

I have a question about how to interpreted the following:

Proposition 2.3. The uniform random tree $$\mathbb{T}_{n}$$ has the same distribution as a tree generated as follows:

• Take a Galton-Watson tree with Poisson(1) offspring distribution;
• Condition it to have total progeny precisely (n);
• Assign the vertices random labels chosen from [n] and forget the original ordering.

Proof. Recall the standard labelling of the vertices of a Galton-Watson tree $$\mathbf{T}$$, and let $$\mathbf{t}$$ be a particular tree with $$\#(\mathbf{t})=n$$ and numbers of offspring $$c\left(v_{1}\right)=c_{1}, \ldots, c\left(v_{n}\right)=c_{n}$$. Then $$\mathbb{P}(\mathbf{T}=\mathbf{t})=\prod_{i=1}^{n} \frac{e^{-1}}{c_{i} !}=e^{-n} \prod_{i=1}^{n} \frac{1}{c_{i} !}$$ Now observe that $$\mathbb{P}(\#(\mathbf{T})=n)$$ is a function only of $$n$$. Hence, $$\mathbb{P}(\mathbf{T}=\mathbf{t} \mid \#(\mathbf{T})=n)=f(n) \prod_{i=1}^{n} \frac{1}{c_{i} !}$$ for some function $$f$$. Now consider labelling the vertices of $$\mathbf{T}$$ with $$[n]:=\{1,2, \ldots, n\}$$. There are $$n!$$ different ways to do this, of which $$\prod_{i=1}^{n} c_{i} !$$ give rise to the same unordered labelled tree, once we forget the ordering. Hence, the probability of obtaining a particular labelled unordered tree $$t$$ is $$f(n) / n !$$. Since this depends only on $$n$$, and not on any other feature of the tree, it must be the case that the tree is uniformly distributed on $$\mathbb{T}_{n}$$.

(From An introduction to random trees by Christina Goldschmidt )

I believe I fully understand how the tree is generated, but what I have trouble with is: $$\mathbb{T}_{n}$$ has the same distribution as a tree generated as above. What does that mean exactly?

Is it, $$\mathbb{P}(\mathbf{T}=\mathbf{t} \mid \#(\mathbf{T})=n)=\mathbb{P}(\mathbf{t} \in \mathbb{T}_{n})$$ and what would $$\mathbb{P}(\mathbf{t} \in \mathbb{T}_{n})$$ be?

## 1 Answer

Despite the varied notation, the following must be true in order for the statements in the proof to make sense:

• $$\mathbb T_n$$ is a random variable: it is a labeled tree uniformly sampled from the set of all labeled $$n$$-vertex trees.
• $$\mathbf T$$ is a random variable: it is an ordered tree generated by the Galton-Watson process.
• $$\mathbf t$$ is a fixed $$n$$-vertex ordered tree.

Now, $$\Pr[\mathbf t \in \mathbb T_n]$$ doesn't make sense: $$\mathbb T_n$$ is not a set. We are closer to wanting to say $$\Pr[\mathbb T_n = \mathbf t]$$, but that also doesn't make sense: $$\mathbb T_n$$ is a labeled tree, and $$\mathbf t$$ is an ordered tree.

To make the statement of the theorem precise, let's define new variables:

• $$\mathbf T'$$ is a labeled tree constructed from $$\mathbf T$$ by forgetting the ordering, and giving the vertices random labels.
• $$t$$ is a fixed $$n$$-vertex labeled tree.

Then our goal is to say that $$\Pr[\mathbf T' = t \mid \#(\mathbf T) = n] = \Pr[\mathbb T_n = t]$$. Here, $$\Pr[\mathbb T_n = t] = \frac1{n^{n-2}}$$, because that's how many labeled $$n$$-vertex trees we are, but for the proof, all we need to know is that $$\Pr[\mathbb T_n = t]$$ is a constant independent of $$t$$ (because $$\mathbb T_n$$ has a uniform distribution). Therefore if $$\Pr[\mathbf T' = t \mid \#(\mathbf T) = n]$$ also does not depend on $$t$$, we obtain the result we want.

The proof shows that $$\Pr[\mathbf T = \mathbf t \mid \#(\mathbf T) = n]$$ is proportional to $$\prod_{i=1}^n \frac1{c_i!}$$, which does depend on $$\mathbf t$$. But also, if $$t$$ is a particular labeling of $$\mathbf t$$, then the probability of obtaining $$t$$ by labeling $$\mathbf t$$ is proportional to $$\prod_{i=1}^n c_i!$$, so the two effects cancel.