# “The” random tree

One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ to vertex $1$ or $2$ with probability $\frac{1}{2}$. Connect vertex $n+1$ to exactly one of vertices $1,\dots, n$ with equal probability $\frac{1}{n}$. This procedure will construct an infinite tree. The theorem is that with probability $1$, any tree constructed this way will be the same (up to permutation of the vertices).

My question is, does anyone know of a reference for this result? What is the automorphism group of this tree? Can anyone draw a picture of it?

I don't have any reason for knowing about this, just curiosity, and I wasn't able to turn up anything with a (not too extensive) internet/mathscinet search.

-
A related question that just occurred to me: Is a random spanning tree of the Rado graph isomorphic to "the" random tree? Actually I think the hard part of this question is figuring out what the right definition of "random spanning tree" is for the Rado graph. –  Harrison Brown Nov 18 '09 at 20:19
One can perform the similar construction: for a given i, take of the edges between i and some smaller vertex at random; then repeat. The tree will have possess the same two properties, so it's all the same again. –  Ilya Nikokoshev Nov 18 '09 at 20:24
@Ilya: vertex $i$ might not be adjacent to lower-numbered vertices at all. –  Brendan McKay Mar 5 '13 at 23:00
Incidentally, for finite n the tree you construct is called a "random recursive tree", and its properties are very well understood. The resulting infinite tree (ignoring vertex labels) is essentially what is called the Ulam Harris tree. –  Louigi Addario-Berry Sep 27 '13 at 13:36
As suspected by Greg Kuperberg, the random recursive tree is rather different from Aldous's random tree and its finite analogue (a uniform spanning tree of K_n). I happen to have written a blog post, rather recently, about (some of) the differences between them, including their respective heights (log n vs. n^{1/2}). methemedantics.wordpress.com/2013/09/15/… –  Louigi Addario-Berry Sep 27 '13 at 13:40

I learned about The random graph a week ago from the blog post on n-cafe (thanks to Andrew and sdcvvc for the links!).

Your construction, while slightly different, can be examined in the same way as the Rado graph. Note, by the way, that expected number of edges meeting at each point is infinity, as is with Rado's graph.

The lemma you want to prove is, I think, this:

Fix an isomorphism between two finite sets $A\to B$ and number $a\notin A$. Take random trees $X$, $Y$ having property that $X|_A = Y|_B$. Then with probability 1 there exists $b\notin B$ such that the isomorphism can be extended to $A\cup\{a\}$ and $B\cup\{b\}$.

A repeated application of this (or very similar) lemma should yield your result: there is an isomorphism between two random trees with probability 1.

Your trees have actually quite simple structure: with probability 1 all vertices have infinite degree. Any two connected trees with this property can be drawn starting from one point and adding infinitely many edges to it, then to leaves, then adding infinitely edges to each leaves and so on.

Sorry, the quality of the picture isn't good:

+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...


Since the trees you descrived are always connected (see comments), this is "the canonical drawing".

In particular, the stabilizer of a point has a filtration by groups of the form $S_\infty$ and $(S_\infty)^\infty$ (interchanging the "outer" edges of a given leaf is $S_\infty$).

-
–  sdcvvc Nov 18 '09 at 19:43
Ilya, not only is it connected w/ probability 1, it's ALWAYS connected. Suppose such a tree was not connected; then there's a connected component not containing vertex 1. This component has some vertex v of minimum label, but v is adjacent to some vertex of smaller label, which is a contradiction. –  Harrison Brown Nov 18 '09 at 20:12
Indeed! I forgot the exact construction while answering. Thanks! –  Ilya Nikokoshev Nov 18 '09 at 20:15
I didn't spot that the "blog post" you referenced was the n-cafe, hence my answer below. Perhaps when one links off-site, one should say where the link goes to as a courtesy. –  Andrew Stacey Nov 18 '09 at 22:00
Can't resist mentioning a peculiar construction of the random graph I heard from Peter Cameron a while ago - the vertices are primes congruent to 1 mod 4, and two primes p and q are connected by an edge if p is a square mod q (this relation is symmetric because of quadratic reciprocity law). A beautiful one, isn't it? –  Vladimir Dotsenko Nov 19 '09 at 16:50

There is a paper in JSTOR, The continuum random tree, I, by David Aldous, that is similar to your question. That is the first of a three part series of papers. However, it doesn't seem like Aldous' tree (or tree ensemble) can be the same as your tree. Your tree would have infinite valence everywhere, because the harmonic series diverges.

To expand a little on this alternate answer that was studied by David Aldous: Suppose that, instead of the process that Ian suggested, you take a random spanning tree of the complete graph on $n$ vertices. Or more properly, you take the ensemble of spanning trees of the complete graph, and then attempt a limit of those ensembles as $n \to \infty$. You can obtain a good ensemble in that limit by looking, for each $k$, at the $k$-neighborhood (in the tree) of a marked vertex, and then sending $k$ to infinity after $n$ is sent to infinity. Then you get a well-defined ensemble of infinite rooted trees, which is hopefuless the same as what Aldous studies. I think that it is a valid model of what is sometimes called "the" random tree.

For instance, what is the probability that the root is a leaf? Using the formula that there are $n^{n-2}$ labelled trees on $n$ vertices, you can compute that it is $1/e$. If I set up the tree properly, then it would mean that $1/e$ of the vertices are leaves, almost surely.

"The" random tree in this sense is statistically the same everywhere, to every finite size of neighborhood. However, I think that it can't be the same tree out to infinity every time, because it contains an infinite amount of data to distinguish samples. For instance the spacing between leaves is an infinite amount of data. I'm not expert enough to arrive at this rigorously, but I believe that a "translation invariant" random process that really gives you the same tree every time would have to give you a boring tree with the same valence everywhere. (This is what I meant by my joke that it would be barking up the wrong tree.) On the other hand, if you do make a "translation invariant" ensemble of trees, then it could be "the" tree in the sense that you might recover all of the local statistics of the entire ensemble just by average over one typical sample.

An analogue that I understand rather better is the Penrose tiling. It is "the" Penrose tiling in the sense that any one Penrose tiling has the local statistics of all Penrose tilings. On the other hand, there are uncountably many different Penrose tilings. (In a natural sense, the Penrose tilings form an ergodic family; they come from a foliation of an $A_4$-shaped torus by parallel planes.)

-
And as Ilya points out below, this + countability is enough to determine the tree up to isomorphism. –  Harrison Brown Nov 18 '09 at 20:08
Somehow I think that that's barking up the wrong tree. –  Greg Kuperberg Nov 18 '09 at 20:34

Since it is regular of countably infinite degree, it is isomorphic to the union of Bruhat-Tits trees for PGL2(F) as F ranges over unramified extensions of a local field. The automorphism group therefore contains PGL2(Fnr), but I don't know much more.

Edit: The automorphism group is apparently described in a 1970 paper by Tits: Sur le groupe des automorphismes d'un arbre, which is not available on line. There is a description of its subgroups of index less than continuum cardinality in Moller's paper The automorphism groups of regular trees - any such subgroup is either the simple index 2 subgroup generated by stabilizers of points, or lies between the pointwise stabilizer of a finite (possibly empty) subtree and the setwise stabilizer of the same subtree. The stabilizer of a point is a limit of a system of wreath products of Sym(Aleph0).

-

The algorithm you describe is at each stage isomorphic to an algorithm for picking a particular tree from the "Uniform Spanning Tree" (which is THE uniform distribution of all possible spanning trees) when applied to any finite fully connected graph.

One standard method is to iterate choosing new points at random (uniformly from the unconnected ones) and performing a "Loop Erased Random Walk" until "hitting" the existing tree.

The isomorphism of algorithms is because such a fractal growth process is uniform so we can modify it at each LERW by removing the irrelevant intermediate points. This is just shrinking the graph by removing nodes on a line without changing "connected-ness".

The large-scale symmetry under permutations is due to the "uniform probability" property of all finite sub-trees.

Bit of a hand-wavy argument so far I know but UST is the way to go. A fully connected graph is a simpler starting point than the 50% connected Rado graph but .. Corollary .. I imagine any graph with a bounded below probability of connected-ness must almost surely have "THE random tree" as a sub-graph as n grows. Average density of connections of "THE random tree" is $\frac2{n-1}$ and expected neighbours of $k$'th point is $\sum_{i=k+1}^n\frac1i$, so by permuting a large sub-graph of Rado to order the most connected points earliest we can comfortably exceed this everywhere and select at least one tree with probability approaching $1$ as $n\rightarrow\infty$.

-
Welcome to MathOverflow. Just so you know, the website is built on mathjax, so if you put latex in your answer it will know what to do. –  David White Oct 13 '13 at 23:47

Here are some pictures of the random tree reduced over a finite number of nodes.

Over $32$ nodes:

Over $96$ nodes:

Over $512$ nodes:

I employ the following ${\tt Sage}$ code to generate these:

def random_tree(n) :
tree = Graph()
for i in xrange(2, n + 1) :
return tree


and the following code to draw these:

tree = random_tree(32)
tree.plot(vertex_size = 24, vertex_labels = False, graph_border = True, iterations = 4096)

-
Unfortunately, I do not success in displaying the pictures. Please, anyone can fix it? –  Samuele Giraudo Mar 5 '13 at 21:58
hmm, not sure what the problem is. I was able to look at the images by editing your post, then clicking on the urls. –  Ian Agol Mar 6 '13 at 4:10
Strange, I thought that picture were automatically displayed. –  Samuele Giraudo Mar 6 '13 at 11:47
I've filed a bug report on these images at meta.mathoverflow.net/questions/1012/… –  Scott Morrison Oct 12 '13 at 0:46