Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
In principle, you can always avoid Chernoff bounds, by a result of Philips and Nelson (jstor.org/stable/2684633). The result is well-explained by quoting the article title: "The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities".
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/…
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.
While there is no mention of the purported letter to Erdos, he does say that in the following few days, while assigned to the wood-yard, he proved Turán's theorem.
It turned out that the officer-Joseph Winkler by name- was an engineer. In his youth he had placed at a mathematical competition; in civilian life he was a proofreader at the printing shop where the periodical of the Third Class of the Academy (Mathematical and Natural Sciences) was printed and had seen some of my manuscripts. He could do no more than assign me to a wood-yard where big logs, necessary to railroad building, were stored, classified according to their diameter; my task was merely to show incoming groups the place where they could find those logs with the prescribed width.
Here is the text from "A note of welcome". In September 1940 I was called in for the first time to labor-camp service. We were taken to Transylvania to work at railway building. Our main work was carrying railway ties. It was not very difficult work but a spectator could of course easily recognize that most of us-I was no exception-did it rather awkwardly. One of my more expert comrades said this at one occasion quite explicitly, even mentioning my name. An officer was standing nearby, watching our work. When hearing my name, he asked the comrade whether or not I was a mathematician. (Contd)
