Critical beta-splitting, via contraction
Brett Kolesnik



Critical beta-splitting, via contraction]
Critical beta-splitting, via contraction


















 
The critical beta-splitting tree, introduced by Aldous, 
is a Markov branching phylogenetic tree  
of poly-logarithmic height.  
Recently, by a technical analysis, 
Aldous and Pittel proved, amongst other results, 
a central limit theorem for the 
height H_n
of a random leaf. 

We give an alternative proof, 
via contraction methods for 
random recursive structures. 
These techniques were developed by 
Neininger and Rüschendorf, 
motivated by 
 Pittel's article 
“Normal convergence problem? 
Two moments and a recurrence may be the clues.”
Aldous and Pittel estimated  
the first two moments of H_n, with great precision. 
We show that a limit theorem follows, 
and bound the distance from normality.  


[
    
Damien Tourret^1,*, 
Rouhollah Tavakoli^1,2, 
Adrian D. Boccardo^1, 
Ahmed K. Boukellal^1,3, 
Muzi Li^1
 and 
Jon Molina-Aldareguia^1,4

    April 29, 2024
=============================================================================================================================================
























§ INTRODUCTION


The 
critical beta-splitting tree _n, 
introduced by Aldous <cit.>, 
is a random recursive combinatorial structure, 
constructed in the following way. 
Assume that n≥2. 
We begin with the set {1,…,n}. 
Let 

    ϑ(n) = ∑_i=1^n 1/i∼log n

denote the harmonic sum. 
The first split occurs between some i and i+1
with probability 

    p(n,i)=
    1/2ϑ (n-1)n/i(n-i),
        
    1≤ i≤ n-1,

in which case {1,…,n} separates  
into {1,…,i}
and {i+1,…,n}.  
We call p(n,i) the critical beta-splitting distribution. 
See <ref>. 



The construction continues recursively, 
splitting 
{1,…,i}
and {i+1,…,n}
independently, etc., until 
only the singleton sets {1},…,{n} remain. 

Finally, the tree _n is obtained as follows. 
Let  denote the set of subsets of 
{1,…,n}, determined by the splits
in the above procedure. 
For each 1≤ j≤ n, a leaf v(j)=v({j}) is placed at height 

    h(j)=#{S∈:j∈ S}-1.

The “-1” 
above accounts for the singleton set {j}∈, 
which does not contribute to the height of v(j). 

An internal node v(S) is added
to the tree, for each S∈ with #S>1. 
The two children of v(S) are v(S_1)
and v(S_2), 
where S_1,S_2∈ are the unique
pair for which S=S_1∪ S_2. 
There are n-1 internal nodes in total, 
one between 
each i and i+1. 
The first internal node ρ=v({1,…,n})
is called the root of _n. 
The height h(j) is simply the graph distance 
(number of edges) 
between ρ and v(j). 
See <ref> for an example. 


As discussed in <cit.>, 
the tree _n is “critical” in the following sense. 
A tree could be constructed in a similar way, 
but with p(n,i) instead
proportional 
to  i^β(n-i)^β. 
The value β=-1 in the above construction 
is of particular interest, since at this point  
typical heights h(j) 
switch from polynomial order 1/n^β+1
to poly-logarithmic order log^2 n. 




























 §.§ Results
 

Amongst other results, 
Aldous and Pittel <cit.> 
recently proved a central limit theorem for 
H_n=h(J), 
where J is uniformly random in {1,2,…,n}. 
In other words, H_n is the height 
of a random leaf in _n. 

Let 

    ζ(s)=∑_n=1^∞1/n^s

denote the 
Riemann zeta function. 



As n→∞, 
we have that 

    H_n-1/2ζ(2)log^2n/√(2ζ(3)/3ζ^3(2)log^3 n)

is asymptotically normal. 


























 §.§ Purpose



Our purpose is to give another proof of <ref>, 
along with a bound on the rate of convergence, 
see <ref> below. 
We will use the contraction methods 
of 
Neininger and Rüschendorf <cit.> (cf. 
Rösler <cit.>,  
 Rachev and Rüschendorf
<cit.>
and Rösler and Rüschendorf <cit.>), 
together with the 
estimates for the mean and variance of H_n  
obtained in <cit.>, 
see (<ref>) below. 


We will also 
discuss, in 
<ref> below, 
connections with a 
result of 
Iksanov, Marynych and Möhle <cit.>, 
on collisions in the beta-coalescent. 

























 §.§ Discussion



The limit theory in
<cit.> was, in part, developed in response
to work of Pittel <cit.>, in which 
 limit theorems are proved for various combinatorial 
quantities of interest (e.g., the independence number 
of a uniformly random labelled tree) 
with mean and variance that are close to linear. 

The following line of reasoning is referred to as  
“Pittel’s principle” in <cit.>. 
Indeed, in <cit.>, the author states that:  

For various global characteristics of large size 
combinatorial structures [...]
one can usually estimate the mean and the variance, 
and also obtain a recurrence 
for the generating function 
[...].

As a heuristic principle based on our experience, 
we claim that such a characteristic is asymptotically 
normal if the mean and the variance are “nearly linear” [...]. 

The technical reason is that in such a case the 
moment generating function [...]
of the normal distribution 
with the same two moments “almost” satisfies the recurrence.



A general theory is developed in <cit.>, 
which, in particular, yields limit theorems in such situations
(see <cit.>). 
In fact, their results apply to a large family of 
random structures X_n, which satisfy a distributional 
recurrence of the form
(see <cit.>) 

    X_nd=∑_i=1^K A_r(n)X^(r)_I_r^(n)+b_n.

As discussed in <cit.>, 
such situations arise, e.g., in divide-and-conquer
type algorithms. 
In this context, b_n is called the toll function,
associated with the “cost” of splitting into smaller, but similar 
subproblems. 

Under certain conditions, 
a limit theorem can be proved
for X_n satisfying (<ref>), via the 
so-called 
contraction method. 
Roughly speaking, this strategy   
aims to identify the limiting distribution of X_n,  
by means of the fixed point equation 

    X
    d=∑_i=1^K A_r^* X^(r) +b^*,

obtained 
by taking n→∞ in (<ref>).
The normal distribution is associated with  
the situation that 
∑_i=1^K (A_r^*)^2=1 and 
b_*=0. 

See <cit.>
for their univariate results. 
See also 
<cit.>
for discussion on the multivariate case, 
and when K=K_n is random, and potentially also 
K_n→∞. 

The height H_n of 
a random leaf in 
the critical beta-splitting tree _n
satisfies a
simple recurrence. 
Specifically, by (<ref>),  
we have that 

    H_n
    d= 
    H_I_n
    +1,

where

    (I_n=i) = 1/(n-i)ϑ (n-1), 
         1≤ i≤ n-1.

That being said, 
the results in <cit.> do not apply. 
The problem is that b_*=0, 
K=1,  and that, as it turns out (see (<ref>) below), 
the mean and variance
of H_n are of poly-logarithmic order. 
This leads to a trivial  fixed point equation 
Xd=X, 
which yields no information about X. 

However, the follow-up article <cit.>, 
by the same authors, deals with 
this very situation, 
and it is these results that we will apply in the current article. 
Specifically, we will use Theorem 2.1 in <cit.>. 
In fact, this result does not apply as stated, but we will 
show that its proof can be suitably adapted. 

We note that several applications of 
contraction methods are 
discussed in, e.g., 
<cit.> and <cit.>. 
In many cases, limit theorems 
follow quite easily using these
techniques. 
We were introduced to them,   
while studying 
randomized importance sampling algorithms 
for perfect matchings  
<cit.> (cf. Neininger and Straub <cit.>). 










 §.§ Time-heights



In closing, let us mention that it is also natural 
to consider an alternative formation of _n, 
in which  
splitting events occur continuously in time. 
In <cit.>, the authors analyze the case of  
exponential holding times on subsets, 
with rates ϑ(k-1)
on subsets of size k. 
In this setting, a central limit theorem is proved 
for the time-height D_n of a random leaf. 
Aldous <cit.> 
has given an alternative, probabilistic 
proof, via martingales. 

A limit theorem for D_n 
seems to be out of reach, however, by the methods in 
the current article, mainly due to the fact that
D_n has smaller variance, 
see (<ref>) and (<ref>) below. 
Therefore, it would appear that 
the critical beta-splitting tree 
provides an 
example of a model,  
at the borderline
of what can be analyzed using 
current 
contraction techniques. 

















 §.§ Acknowledgments

We thank David Aldous and 
Boris Pittel  
for inspiring conversations. 























§ CONTRACTION, WITH TRIVIAL FIXED POINT


To begin, let us state the main 
result in <cit.>. 

Suppose that a sequence (X_n) of random variables
satisfies

    X_n
    d= 
    X_I_n +b_n,

where (I_n,b_n) and (X_n) are independent, 
and I_n takes values
in {1,…,n-1}. (In <cit.>, I_n can 
take values in  
{0,1,…,n}, but we have no use for this.)


Let μ_n=(X_n) and σ^2_n= Var(X_n). 

As usual, Y_p=(|Y|^p)^1/p 
denotes the L_p-norm. 



Suppose that (X_n) satisfies (<ref>), with 
X_n_3<∞, 

    lim sup_n→∞[log(I_n/n)]<0,
        sup_n≥1log(I_n/n)_3<∞.

Assume also that, 
for some α,λ,κ∈
with 0≤λ<2α, 
and some C>0, we have that 

    b_n-μ_n+μ_I_n_3=O(log^κ n),
        σ^2_n=Clog^2αn+O(log^λ n),

and 

    β=
    min{
    3/2,3(α-κ),3(α-λ/2),α-κ+1
    }>1.

Then, as n→∞, 

    X_n-μ_n/√(C)log^α n

is asymptotically normal. 


Furthermore, it is shown that the 
distance from normality
is O(1/log^β-1n), with respect to the 
Zolotarev metric ζ_3 <cit.>. 
As discussed in <cit.>,

    ζ_3(U,V)=sup| f(U)- f(V)|,

where the supremum is over all twice differentiable 
f, with 1-Lipschitz f”. Convergence with respect to 
ζ_3 implies weak convergence.














§ PROOF OF <REF>


In proving <ref>, we will 
not apply <ref> directly. 
Instead, we will adapt its proof. 

We will use the following, remarkably precise,  
estimates in 
<cit.>. 
Throughout this section, we let
μ_n=(H_n) and σ^2_n= Var(H_n). 
We have that 

    μ_n   =1/2ζ(2)log^2n
    +γζ(2)+ζ(3)/ζ^2(2)log n+O(1),
    σ^2_n   =2ζ(3)/3ζ^3(2)log^3n+O(1),

where 

    γ
    =lim_n→∞(ϑ(n)-log n)

is the Euler–Mascheroni constant. 

The reason <ref> does not apply directly
is that, 
by (<ref>) and (<ref>), 
we have that 

    |log(I_n/n)|^k
       =
    1/ϑ (n-1)∑_i=1^n-1|log(i/n)|^k/n-i
       ∼1/log n∫_0^1|log(1-x)|^k/xdx
    =k!ζ(k+1)/log n.

We do, however, have the distributional recurrence 
(<ref>). Hence, by 
(<ref>) and (<ref>), 
we have, in the notation of 
<ref>, that 
b_n=1, κ=2/3, α=3/2 and 
λ=0. 
In particular, to see that κ=2/3, let us note that, 
by elementary arguments 
it can be shown, 
using (<ref>) and (<ref>), 
that 

    1-μ_n+μ_I_n_3
    =O(log n)log(I_n/n)_3
    =O(log^2/3n).




We will prove the following result, 
which, as we will see, 
follows by the proof of 
<ref> (Theorem 2.1 in <cit.>), 
after a few adjustments. 


 

Let H_n be the height of a uniformly 
random leaf in the critical beta-splitting 
tree _n. 
Then

    H_n^*=H_n-μ_n/σ_n

is asymptotically normal, where 
μ_n=(H_n) and σ^2_n= Var(H_n). 
Furthermore, for any >0, 

    ζ_3(H_n^*,Z)
    =O(1/log^1/2- n),

where Z is a standard normal random variable. 


In what follows, we will assume familiarity with the proof
of Theorem 2.1 in <cit.>, 
and the notation introduced therein. 
Since only a few changes 
are required, we will not explain the full proof here, 
but rather only discuss the 
places that need adjustment. 




We put
C=2ζ(3)/3ζ^3(2), 
so that, by (<ref>), 

    σ^2_n=Clog^3n+O(1).


There are two main parts of 
the proof of <cit.>
that need attention. The first is the technical result
<cit.>. 
In fact, the proof of this result simplifies. 
Secondly, we will revisit the upper bound
<cit.>, as this 
estimate is used in the inductive proof of 
<cit.>. 

Let us start with the second part. 
Recall that (I_n∈{0,n})=0. 
We set 
δ=1, and let 
ℓ_n=log n+_n=1 play the role of 
L_δ(n). 


As noted above, α=3/2. 
In particular, we simply have 

    b^(n)   =1-μ_n+μ_I_n/√(C)ℓ_n^3/2,
    τ_n   =σ_n/√(C)ℓ_n^3/2,
    
    G_n   =σ_I_n/√(C)ℓ_n^3/2.


We claim
that 
the right hand side of 
<cit.> (and so 
also the left hand side of <cit.>) 
is O(1/log^5/2n). 
To see this, we first note, 
using (<ref>), that 
b^(n)_3^3=O(1/log^5/2n). 
Similarly, it can be shown that b^(n)_2=O(1/log n). 
Next, we observe that, clearly, 
|τ_n-1|=O(1/log^3 n). 
Finally, we note, by similar arguments as (<ref>), that

    |G_n-1|
    =O(1+(log n)^2|log(I_n/n)| /log^3 n).

It follows that 
G_n-1_2=O(1/log^3/2 n),  
G_n-1_3^3=O(1/log^4 n)
and

    Δ_n_3^3
    =|τ_n^2-G_n^2|^3/2=O(1/log^5/2 n).

Altogether, the 
right hand side of 
<cit.> is 
O(1/log^5/2n),
as claimed. 

Therefore, to the complete the proof, it remains only the 
prove the following analogue of 
the technical result in 
<cit.>. 



Let I_n be as in (<ref>). Suppose that 
nonnegative sequences (d_n) and (r_n) satisfy 

    d_n≤[(ℓ_I_n/ℓ_n)^9/2 d_I_n] 
    +r_n,     n≥2,

and 

    r_n=O(1/log^5/2 n).

Then, for all small >0, it follows that 

    d_n=O(1/log^1/2-n).



To see this, we will follow the proof of <cit.>.
We can, in fact, make some simplifications in this special case. 
Using (<ref>), (<ref>) and (<ref>), 
let M>0 and n_1 be such that 
r_n
≤ M/log^5/2 n
and 

    [log (I_n/n)]/log n
    +(I_n=1)/log n
    +1/log^2+ n≤ 0

for all n≥ n_1. 

Put

    R=M∨max{d_kℓ^1/2-_k:1≤ k≤ n_1}.

To prove the claim, we will show, by induction, that 
d_n≤ R/ℓ_n^1/2-. 
By the choice of R, there is nothing to prove for n≤ n_1. 
On the other hand, for n> n_1, by 
(<ref>), the choice of n_1, and 
the inductive hypothesis, 

    d_n
       ≤[(ℓ_I_n/ℓ_n)^9/2R/ℓ^1/2-_I_n]
    + M/log^5/2 n
       ≤R/ℓ^1/2-_n[(ℓ_I_n/ℓ_n)
    +1/log^2+ n]
       ≤R/ℓ^1/2-_n(1+
    [log (I_n/n)]/log n
    +(I_n=1)/log n
    +1/log^2+ n)
       ≤ R/ℓ^1/2-_n,

as required. 

This 
finishes the proof, 
as the rest of the proof of 
Theorem 2.1 in 
<cit.>
applies, without any further changes. 




















§ FINAL REMARKS



















 §.§ Time-height

Recall, as discussed in <ref> above, 
that D_n is the time-height of the 
critical beta-splitting tree with exponential 
holding times.
In <cit.>, it is shown that 

    (D_n)   =1/ζ(2)log n+O(1),
     var(D_n)   =(1+o(1))2ζ(3)/ζ^3(2)log n.

Finer estimates are available, 
assuming a certain “h-ansatz,” 
see <cit.>. 

The proof of <ref> 
does not seem to work for D_n. 
First of all, the o(1) in the above variance 
estimate effectively gives only λ=2α. 
Furthermore, since α=1/2 for D_n, rather than α=3/2
for H_n, the  
right hand side of 
<cit.> is 
≫ 1/log^2 n. As a result, 
the contribution from [log (I_n/n)]/log n
is not enough to yield an analogue of 
<ref>.





















 §.§ Collisions



Finally, as mentioned in <ref> above, let us discuss
the central limit theorem proved by 
in <cit.>
for the number of collisions Ξ_n 
in the β(2,b)-coalescent. 
See, e.g., Pitman <cit.>, Sagitov <cit.>
and the survey by Gnedin, Iksanov and Marynych <cit.>
for background. 

In <cit.>, there is a similar recurrence 
as (<ref>) above. Also, <ref> 
does not apply 
for similar reasons 
(compare  (<ref>) 
with <cit.>). 
To overcome this issue, 
an alternative, and more complicated, 
recurrence is derived <cit.>, and then 
<ref> is applied. 
However, the authors
ask <cit.>
if a more direct proof, using the simpler recursion <cit.>, 
is possible.  

It seems that we cannot quite answer this question. 
The reason is that, by <cit.>, 

    (Ξ_n)   =Alog^2 n+Blog n+O(1),
     var(Ξ_n)   =Clog^3 n+O(log^2n),

for explicit constants A,B,C. 
Therefore, 
λ=2 for Ξ_n, 
whereas λ=0 for H_n. 
As such, once again, 
the right hand side of 
<cit.> is 
≫ 1/log^2 n. 












iblabel[1]#1.







10

Ald23
D. Aldous, The critical beta-splitting random tree II: Overview and
  open problems, preprint available at <https://arxiv.org/abs/2303.02529>.

Ald96
, Probability distributions on cladograms, Random discrete
  structures (Minneapolis, MN, 1993), IMA Vol. Math. Appl., vol. 76,
  Springer, New York, 1996, pp. 1–18.

AP23
D. Aldous and B. Pittel, The critical beta-splitting random tree: Heights
  and related results, preprint available at
  <https://arxiv.org/abs/2303.02529>.

DK21
P. Diaconis and B. Kolesnik, Randomized sequential importance sampling
  for estimating the number of perfect matchings in bipartite graphs, Adv. in
  Appl. Math. 131 (2021), Paper No. 102247, 41.

GIM14
A. Gnedin, A. Iksanov, and A. Marynych, Λ-coalescents: a
  survey, J. Appl. Probab. 51A (2014), no. Celebrating 50 Years of
  The Applied Probability Trust, 23–40.

IMM09
A. Iksanov, A. Marynych, and M. Möhle, On the number of collisions in
  beta(2,b)-coalescents, Bernoulli 15 (2009), no. 3,
  829–845.

NR04a
R. Neininger and L. Rüschendorf, A general limit theorem for
  recursive algorithms and combinatorial structures, Ann. Appl. Probab.
  14 (2004), no. 1, 378–418.

NR04b
, On the contraction method with degenerate limit equation, Ann.
  Probab. 32 (2004), no. 3B, 2838–2856.

NS22
R. Neininger and J. Straub, On the contraction method with reduced
  independence assumptions, 33rd International Conference on
  Probabilistic, Combinatorial and Asymptotic Methods for the
  Analysis of Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 225,
  Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Art. No. 14, 13.

Pitman99
J. Pitman, Coalescents with multiple collisions, Ann. Probab.
  27 (1999), no. 4, 1870–1902.

Pit99
B. Pittel, Normal convergence problem? Two moments and a recurrence may
  be the clues, Ann. Appl. Probab. 9 (1999), no. 4, 1260–1302.

RR95
S. T. Rachev and L. Rüschendorf, Probability metrics and recursive
  algorithms, Adv. in Appl. Probab. 27 (1995), no. 3, 770–799.

Ros91
U. Rösler, A limit theorem for “Quicksort”, RAIRO Inform.
  Théor. Appl. 25 (1991), no. 1, 85–100.

Ros92
, A fixed point theorem for distributions, Stochastic Process.
  Appl. 42 (1992), no. 2, 195–214.

RR01
U. Rösler and L. Rüschendorf, The contraction method for
  recursive algorithms, vol. 29, 2001, Average-case analysis of algorithms
  (Princeton, NJ, 1998), pp. 3–33.

Sag99
S. Sagitov, The general coalescent with asynchronous mergers of ancestral
  lines, J. Appl. Probab. 36 (1999), no. 4, 1116–1125.

Zol76
V. M. Zolotarev, Approximation of the distributions of sums of
  independent random variables with values in infinite-dimensional spaces,
  Teor. Verojatnost. i Primenen. 21 (1976), no. 4, 741–758.

Zol77
, Ideal metrics in the problem of approximating the distributions
  of sums of independent random variables, Teor. Verojatnost. i Primenen.
  22 (1977), no. 3, 449–465.






