Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?

Question

Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following desiderata:

D1. $f(T)$ is a (random) tree on the vertex set $V'=\lbrace 1,\ldots,n+1\rbrace$;

D2. the distribution of $f(T)$ is uniform over the set of all $(n+1)^{n-1}$ labeled trees on $V'$;

D3. $f$ is a simple graph-theoretic recipe.

This $f$ can be a random function. That is, it can flip coins in deciding what to do with $T$: for instance, removing an edge uniformly at random.

One obvious way to satisfy D1 and D2 is:

1. convert $T$ to its Prüfer sequence $s$;

2. independently, with probability $1/(n+1)$, change each entry of $s$ to $n+1$ (otherwise leave it fixed);

3. then add a random number to the end of $s$, drawn uniformly from $V'$;

4. let $f(T)$ be the tree corresponding to the new sequence.

But what this procedure "really does" to $T$ seems not so easy to describe in graph-theoretic terms. I am looking for a recipe that satisfies D1-3 by manipulating the graph "directly" (i.e., adding and removing edges) without opaque steps like (1) and (4) in the above procedure.

Answer 1

This is an interesting question. For any fixed positive integer $d \geq 2$, write $T_d^{\infty}$ for the complete infinite rooted $d$-ary tree (by this I mean every node has exactly $d$ children). Luczak and Winkler proved the existence of a procedure which will generate a sequence $(T_{n,d})_{n \geq 0}$ such that for all $n \geq 1$,

(a) the distribution of T_{n,d} is uniformly random over all $n$-node subtrees of $T^{\infty}_d$ that contain the root of $T^{\infty}_d$; and

(b) $T_{n,d}$ is a subtree of $T_{n+1,d}$.

It is not hard to show that (a) implies that for all $n$, $T_{n,d}$ is distributed as a Galton-Watson tree with offspring distribution $\mathrm{Bin}(d,1/d)$, conditioned to have total size $n$. Since $\mathrm{Bin}(d,1/d)$ tends to a $\mathrm{Poisson}(1)$ distribution as $d$ becomes large, this means that as $d \to \infty$, the distribution of $T_{n,d}$ tends to that of a Galton-Watson tree with offspring distribution $\mathrm{Poisson}(1)$ conditioned to have $n$ nodes (let me write $\mathrm{PGW}_n(1)$ for this distribution). The latter distribution is the same as that of a uniformly random labelled rooted tree on labels $1,\ldots,n$. (At least, the latter is true once we label the Galton-Watson tree uniformly at random, or alternately remove the labels of the labelled rooted tree.)

As noted by Lyons et al. (Theorem 2.1), all this implies in particular that one can define a similar sequence $(T_n)_{n \geq 1}$ such that for all $n$, $T_n$ is a subtree of $T_{n+1}$ and $T_n$ has distribution $\mathrm{PGW}_n(1)$.

However, the construction in the Luczak-Winkler paper uses flows, and it is not 100% obvious how it "passes through to the $d=\infty$ limit." (I say this with the caveat that I didn't make any serious attempt at figuring this out.) As a consequence, while it is known that there exists a generation procedure of the type you are looking for, I am not aware of an explicit description of the actual rule for where the leaf should be attached to $T_n$ to create $T_{n+1}$. I asked Peter Winkler about this at a conference last year and he also didn't know (though I don't know whether he had thought about this specific question in depth, either).

Answer 2

Yes, there is a simple method if you allow some non-determinism. Given a labelled tree $T$ on $n$ vertices, uniformly randomly choose a vertex $v$ and a number $k\in[1,n+1]$. Attach a new vertex via an edge to $v$, add 1 to every label that is $k$ or more, and label the new vertex with $k$. This gives a tree $T'$ with $n+1$ vertices. However, the probability of each labelled tree on $n+1$ being generated is proportional to its number of leaves, since each leaf represents a way this tree could have been generated. We can correct this with a probabilistic filter: if $\ell$ is the number of leaves of $T'$, reject $T'$ and start over with probability $1-2/\ell$. Keep doing this until a tree is accepted. The expected number of trials before a tree is accepted is at most $n/2$. Probably it is close to $n/(2e)$ since the average number of leaves is $n/e$.

Answer 3

I think what you're asking for is a uniform random distribution of trees on $n$ nodes, and not really a (randomizing) function from trees to trees. Consider permutations: does it matter whether you take a given permutation and perturb it, or if you just generate a random permutation.

That said, I see no need to use direct graph manipulation. Just generate a sequence of $n-2$ integers from ${1..n}$ (i.e. a uniformly random Prüfer sequence) and then make a tree out of it. Here you have the generation algorithm and proof immediately. For a perturbing algorithm you'd have to show that you perturbation will result in any possible tree with equal probability.