Psi-series method in random trees and moments of high orders

Details Psi-series method in random trees and moments of high orders Psi-series method in random trees and moments of high orders

2010-02-20

arxiv.org/abs/1002.3859v1

Mathematics

Probability

Scientific paper

An unusual and surprising expansion of the form \[ p_n = \rho^{-n-1}(6n +\tfrac{18}5+ \tfrac{336}{3125} n^{-5}+\tfrac{1008}{3125} n^{-6} +\text{smaller order terms}), \] as $n\to\infty$, is derived for the probability $p_n$ that two randomly chosen binary search trees are identical (in shape and in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and analysis of algorithms, and based on the psi-series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed and several attractive phenomena are discovered.

Affiliated with

Also associated with

No associations

Rating

Psi-series method in random trees and moments of high orders 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 Psi-series method in random trees and moments of high orders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Psi-series method in random trees and moments of high orders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692464