Psi‐series method for equality of random trees and quadratic convolution recurrences1. Issue 1 (11th May 2012)

• Record Type: Journal Article
• Authors: Chern, Hua‐Huai; Fernández‐Camacho, María‐Inés; Hwang, Hsien‐Kuei; Martínez, Conrado
• Is Part Of: Random structures & algorithms. Volume 44:Issue 1(2014)
• Page Start: 67
• Page End: 108
• Publication Date: 2012-05-11
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20428
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>An unusual and surprising expansion of the form <disp-formula content-type="mathematics" id="rsa20428-disp-0001"><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37jp8h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley:10429832:media:rsa20428:rsa20428-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:msup><mml:mo>ρ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mn>6</mml:mn><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mn>18</mml:mn></mml:mrow><mml:mn>5</mml:mn></mml:mfrac><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mn>336</mml:mn></mml:mrow><mml:mrow><mml:mn>3125</mml:mn></mml:mrow></mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>5</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mn>1008</mml:mn></mml:mrow><mml:mrow><mml:mn>3125</mml:mn></mml:mrow></mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mtext>smaller</mml:mtext><mml:mo> </mml:mo><mml:mtext>order</mml:mtext><mml:mo> </mml:mo><mml:mtext>terms</mml:mtext></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>, </mml:mo></mml:mrow></mml:math></alternatives></disp-formula> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37jp7z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20428:rsa20428-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></alternatives>, is derived for the probability <italic>p</italic><sub><italic>n</italic></sub> 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</p> </abstract>