Feedback on Andrew Lohr and Doron Zeilberger's On The Limiting Distibutions of the Total Height On Families of Trees

Very interesting E-Mail message from Valentin Féray

Dear Andrew, dear Doron,

I've seen your paper about universality of the total height statistics in trees and I think I have an explanation for it.

All families of trees you are considering are Galton-Watson trees conditioned to have $n$ vertices, see: Svante Janson's,

Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation

For such trees it is known that their renormalized *height process* converges towards a λ e , where λ is a constant (depending on the family you consider) and e is the Brownian excursion (universal, in the sense that it does not depend on the family of trees you consider), see:

The depth first processes of Galton-Watson trees converge to the same Brownian excursion by Jean-Francois Marckert and Abdelkader Mokkadem.

But the total height is just the integral of the height process. Therefore it converges towards λ (Int(e(t),t=0..1))

The random variable Bex= Int(e(t), t=0..1) has been studied by Svante Janson, see

Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas"  

In particular, he computes its moments (which suggest that your limiting moment would look nicer if you renormalized to have expectation 1, instead of centering and forcing the variance to be 1). But I don't know if a formula for its density is known (too bad for the 100 dollars donation to OEIS; the best would be to ask Svante Janson directly).

With best regards,

Valentin Féray


Back to the article page

Doron Zeilberger's Home Page