Psi‐series method for equality of random trees and quadratic convolution recurrences |
| |
| Authors: | Hua‐Huai Chern María‐Inés Fernández‐Camacho Hsien‐Kuei Hwang Conrado Martínez |
| |
| Institution: | 1. Department of Computer Science, National Taiwan Ocean University, , Keelung, 202 Taiwan;2. Departamento de Sistemas Informáticos y Computación, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid, , Madrid, E‐28040 Spain;3. Institute of Statistical Science, Academia Sinica, , Taipei, 115 Taiwan;4. Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, , Barcelona, E‐08034 Spain |
| |
| Abstract: | An unusual and surprising expansion of the form ![urn:x-wiley:10429832:media:rsa20428:rsa20428-math-0002]( "urn:x-wiley:10429832:media:rsa20428:rsa20428-math-0002") as  , is derived for the probability pn that two randomly chosen binary search trees are identical (in shape, hence 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 the analysis of algorithms, and it is based on the logarithmic 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 in this article and several attractive phenomena are discovered.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 67–108, 2014 |
| |
| Keywords: | psi‐series method nonlinear differential equations random trees recursive structures singularity analysis asymptotic analysis |
|
|
