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 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .