You are here

The Critical Beta-splitting Random Tree

David Aldous , U.C. Berkeley and University of Washington
Monday, November 20, 2023 - 2:30pm to 3:20pm
SMI 305
In the critical beta-splitting model of a random \$n\$-leaf rooted tree, clades (subtrees) are recursively split into sub-clades, and a clade of \$m\$ leaves is split into sub-clades containing  \$i\$ and \$m-i\$ leaves with probabilities \$\propto 1/(i(m-i))\$.  This model turns out to have interesting properties: a wide range of results and open problems can be found in two preprints at and
In brief:
There is a canonical embedding into a continuous-time model (CTCS(n)).
 There is an inductive construction of CTCS(n) as \$n\$ increases, analogous to the stick-breaking constructions of the uniform random tree and its limit continuum random tree.
 We study the heights of leaves and the limit {\em fringe distribution} relative to a random leaf. 
There is a scaling limit, a process of fragmentation of the unit interval.
 In addition to familiar probabilistic methods, there are analytic methods (developed by co-author Boris Pittel) based on explicit recurrences which often give more precise results.  So this model provides an interesting concrete setting in which to compare and contrast these methods.
Event Type: 
Event Subcalendar: