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

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.

-
It isn't inductive, but are you familiar with Wilson's algorithm for choosing a uniform spanning tree via loop-erased random walk? See en.wikipedia.org/wiki/Loop-erased_random_walk –  Nate Eldredge Aug 24 '10 at 12:20
@Nate, I wrote that in an answer that is currently deleted because I couldn't see how it would help in constructing an inductive procedure like the one the OP is asking. Another algorithm is the one by Aldous(1990) but it didn't seem to help either. On a different note there are other ways to put a bijection between labeled trees and sequences of length $n-2$ which are more "local" in nature than the Prufer code. –  Gjergji Zaimi Aug 24 '10 at 12:30

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).

-
Thank you very much... the Poisson(1) G-W procedure is almost enough for my purposes. The slightly frustrating thing is that it may add a lot of leaves in one iteration, whereas the Luczak-Winkler procedure seems like it would allow one to do it node by node (though maybe it would take some work to make it an explicit algorithm). Thanks for the great references -- I really appreciate the help. –  Ben Golub Aug 25 '10 at 2:06
The tree $T_n$ has exactly $n$ nodes, so if $T_n$ is a subtree of $T_{n+1}$ then $T_{n+1}$ must have been created by adding only a single leaf, not lots of leaves. –  Louigi Addario-Berry Aug 25 '10 at 2:38
Yes, I understand... initially I had considered just making a Poisson(1) random tree generation-by-generation. This shows how to do it one leaf at a time. Thanks! –  Ben Golub Aug 25 '10 at 7:05

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$.

-

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.

-
Thanks very much for your answer. I should have been clearer in the question, but it is important to me not to use the standard Prüfer sequence way of generating random trees, but rather to "build up" -- which is why I introduced the function f. The reason for my desiderata is that I have a decomposition procedure that splits up T into a bunch of pieces (satisfying certain conditions). It is easy to see how this decomposition evolves'' when you add in a vertex and attach it in some simple way, but very hard to do the decomposition straight from a random Prufer sequence. –  Ben Golub Aug 24 '10 at 23:03