Extremal properties of random trees

Details Extremal properties of random trees Extremal properties of random trees

2001-05-15

arxiv.org/abs/cond-mat/0105309v1

Phys. Rev. E 64, R035101 (2001)

Physics

Condensed Matter

Statistical Mechanics

4 pages, revtex

Scientific paper

10.1103/PhysRevE.64.035101

We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal heights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and conversely, the front in the maximal case is governed by the large-extremal-height tail of the distribution. We determine several statistical characteristics of the extremal height distribution analytically. In particular, the expected minimal and maximal heights grow logarithmically with the tree size, N, hmin ~ vmin ln N, and hmax ~ vmax ln N, with vmin=0.373365 and vmax=4.31107, respectively. Corrections to this asymptotic behavior are of order O(ln ln N).

Affiliated with

Also associated with

No associations

Rating

Extremal properties of random trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extremal properties of random trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal properties of random trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-151214