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. 



"The" random tree
I learned about [The random graph](http://en.wikipedia.org/wiki/Rado_graph) a week ago from [the blog post on n-cafe](http://golem.ph.utexas.edu/category/2009/11/fraisse%5Flimits.html) (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$).


