Maximal clades in random binary search trees

MaRDI QIDQ2256128zbMATH OpenFDO

Authors Svante Janson

Publication date 19 February 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6337, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p31

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

binary search treesmaximal cladesphylogenetic treesYule-Harding model

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study maximal clades in random phylogenetic trees with the Yule-Harding model or, equivalently, in binary search trees. We use probabilistic methods to reprove and extend earlier results on moment asymptotics and asymptotic normality. In particular, we give an explanation of the curious phenomenon observed by Drmota, Fuchs and Lee (2014) that asymptotic normality holds, but one should normalize using half the variance.

Review text

Summary: We study maximal clades in random phylogenetic trees with the Yule-Harding model or, equivalently, in binary search trees. We use probabilistic methods to reprove and extend earlier results on moment asymptotics and asymptotic normality. In particular, we give an explanation of the curious phenomenon observed by \textit{M. Drmota}, \textit{M. Fuchs} and \textit{Y.-W. Lee} [``Limit laws for the number of groups formed by social animals under the extra clustering model (Extended abstract), in: Proceedings of the 25th international conference on probabilistic, combinatorial and asymptotic methods for the analysis of algorithms, AofA '14 Paris, Discrete Math. Theor. Comput. Sci., Proc. 2014, 73--84 (2014)] that asymptotic normality holds, but one should normalize using half the variance.

Recommendations

• On the subtrees of random binary search trees
• Asymptotic distribution of two-protected nodes in random binary search trees
• Distribution of distances in random binary search trees.
• On the richness of the collection of subtrees in random binary search trees
• Limit laws for local counters in random binary search trees

Cites work

• Asymptotic fringe distributions for general families of random trees
• scientific article; zbMATH DE number 3723610 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• scientific article; zbMATH DE number 850224 (Why is no real title available?)
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Limit laws for local counters in random binary search trees
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Limit laws for the number of groups formed by social animals under the extra clustering model
• Limit theorems for patterns in phylogenetic trees
• Martingale Convergence to Infinitely Divisible Laws with Finite Variances
• Minimal clade size and external branch length under the neutral coalescent
• NIST handbook of mathematical functions
• Prediction of group patterns in social mammals based on a coalescent model
• Probabilistic analysis of a genealogical model of animal group patterns
• Probability: a graduate course
• Random Trees
• The coalescent
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance

Cited in

(1)

• Stochastic analysis of the extra clustering model for animal grouping

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: Maximal clades in random binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256128)