PRUNING CUT TREES AND THE RECONSTRUCTION PROBLEM Nicolas B ROUTINHui H EMinmin W ANG February 3 2023

2025-05-02 0 0 712.57KB 27 页 10玖币

侵权投诉

PRUNING, CUT TREES,AND THE RECONSTRUCTION PROBLEM

Nicolas BROUTIN *

†Hui HE‡Minmin WANG §

February 3, 2023

Abstract

We consider a pruning of the inhomogeneous continuum random trees, as well as the cut trees that

encode the genealogies of the fragmentations that come with the pruning. We propose a new approach

to the reconstruction problem, which has been treated for the Brownian CRT in [14] [Electron. J.

Probab. vol. 22, 2017] and for the stable trees in [6] [Ann. IHP B, vol 55, 2019]. Our approach does

not rely upon self-similarity and can potentially apply to general L´

evy trees as well.

1 Introduction

In this work, we consider pruning processes of random tree-like metric spaces, which arise in the scaling

limits of prunings of ﬁnite discrete trees. Extending the notion of tree as a loop-free connected graph,

we say that a complete metric space (T, d)is a real tree if for any two points σ, σ0∈ T there is a unique

arc with end points σand σ0denoted by Jσ, σ0K, and that arc is isometric to the interval [0, d(σ, σ0)]. The

reader is encouraged to refer to [19] for a comprehensive study on real trees. We are interested in random

real trees, or more precisely a collection of fractal-like random real trees called continuum random trees

(CRT in short).

Let us take a special case in order to illustrate our general motivation: the celebrated Brownian con-

tinuum random tree of Aldous [7]. Aldous and Pitman [9] have deﬁned a fragmentation process related

to the standard additive coalescent. Informally, this fragmentation process is engineered by logging the

Brownian CRT at uniform locations on its skeleton, resulting in smaller and smaller connected compo-

nents as time goes on. There is a natural notion of genealogy associated to this fragmentation, which

can be represented as a separate continuum random tree, called the cut tree. It turns out that this cut

tree is also distributed like a Brownian continuum random tree [11]. This distributional identity between

the CRT and its cut tree in fact holds for more general families of random trees, including the stable

L´

evy trees [16], the general L´

evy tree under the excursion measures [3], as well as the inhomogeneous

continuum random trees [13].

Roughly speaking, the reconstruction problem asks whether it is possible to rebuild the original CRT

from its cut tree, how to proceed, and what additional information one needs to possess in order to make

this happen. This question has been considered for the Brownian CRT [14] and for the stable L´

evy

trees [6]. However, the approaches in [14] and [6] both rely heavily on the self-similar property of the

underlying trees. These trees also happen to be compact.

*LPSM, Sorbonne Universit´

e, Campus Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France. Email:

nicolas.broutin@sorbonne-universite.fr

†Institut Universitaire de France (IUF)

‡School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China. Email: hehui@bnu.edu.cn

§Department of Mathematics, School of Mathematical and Physical Sciences, University of Sussex, Brighton, BN1 9QH,

United Kingdom. Email: minmin.wang@sussex.ac.uk

arXiv:2210.13948v3 [math.PR] 2 Feb 2023

In the present work, we address the question of reconstruction for models of continuum random trees

that are not necessarily self-similar, nor compact. More precisely, let (T, d, µ)be a CRT belonging to the

family of Inhomogeneous continuum random trees (ICRT) introduced by Aldous and Pitman [9], which

are parametrised by (β, θ)where

β∈[0,∞),θ= (θ1, θ2, . . . )with θ1≥θ2≥ ··· ≥ 0and X

i≥1

θ2

i<∞.(1)

We will assume that

if β= 0,then necessarily X

i≥1

θi=∞,(2)

to avoid trivial cases. Given such a pair (β, θ), the associated ICRT (T, d, µ)is constructed using the

so-called Line-breaking Algorithm due to Aldous & Pitman [9]; we refer to Section 2.1 for details.

Inhomogeneous continuum random trees are the scaling limits of birthday trees (or p-trees), a family

of random trees which generalize uniformly random labelled trees and appear naturally in the study

of the birthday problems [15]. They are also closely related to additive coalescents [9] and models of

inhomogeneous random graphs [12].

The Brownian CRT appears as a particular instance of the ICRT family by taking β= 1 and θi= 0

for all i≥1. Whereas the Brownian CRT emerges in the limit of large uniform binary trees, as soon as

θis non zero, points of inﬁnite degrees or hubs will be found in the corresponding ICRT. We denote by

Br∞(T)the set of these hubs in T, which is necessarily a ﬁnite or countably inﬁnite set. In the current

work, we will focus on the case where Piθi=∞. In that case, Br∞(T)is almost everywhere dense in

T, and our approach to the reconstruction problem relies on a new approximation of the distance din T

using elements of Br∞(T). Let us also point out this distance approximation is used in [22] to conﬁrm

a conjectured mixture relationship between stable L´

evy trees and ICRT.

Plan of the paper. We will need a fair amount of preliminaries in order to be able to give the precise

statement of our results. Section 2is therefore dedicated to the relevant background and results: In

Section 2.1, we introduce the inhomogeneous continuum random trees via the Line-breaking Algorithm.

We explain in Section 2.2 the new approach to distance approximations that is key to our reconstruction

procedure. In Section 2.3, we deﬁne the pruning process on the ICRT and the accompanying cut tree.

Our approach to the reconstruction problem is then described in Section 3. The rest of the paper contains

the proofs of our main results.

2 ICRTs, fragmentation and cut trees

2.1 The inhomogeneous continuum random trees

Let (β, θ)be as in (1). We will use the notation kθk2=Pi≥1θ2

i. The following Line-breaking

construction is a trivial extension to the original version presented in [9], where it is assumed that

β+kθk2= 1. We build a (random) metric space (T, d)with a collection of Poisson processes de-

ﬁned as follows. If β > 0, let {(Uj, Wj), j ≥1}be the atoms of a Poisson point measure on the ﬁrst

octant {(x, y):0≤y≤x}with intensity βper unit area. For every θi>0, let (ξi,j, j ≥1) be the jumps

of a Poisson process on the positive real line with intensity θiper unit length. Note that the hypotheses

on θentail that the only limit point of the set {Uj, j ≥1, ξi,j, i ≥1, j ≥2}is inﬁnity, and therefore can

be ordered as 0< η1< η2< . . . ; we will refer to the ηi’s as cutpoints. Next, we associate to each ηka

jointpoint η∗

kin the following way. If ηk=Ujfor some j≥1, then η∗

k=Wj. If, instead, ηk=ξi,j for

some j≥2, we then set η∗

k=ξi,1. Note that η∗

k< ηkby deﬁnition for each k.

Having got the cutpoints (ηk)k≥1, we use them to partition the half-line [0,∞)into line segments

[ηk, ηk+1],k≥0, with the understanding that η0= 0. We then assemble these line segments into a tree.

More precisely, let R1be simply the single branch [0, η1]. For k≥1, let Rk+1 be the (real) tree obtained

from Rkand [ηk, ηk+1]by identifying ηkwith η∗

k∈ Rk. Then (Rk)k≥1is an increasing sequence of

metric spaces. We then deﬁne (T, d)to be the completion of ∪kRk. It is often convenient to distinguish

the image of 0in T; we refer to it as the root of Tand denote it as ρ. Let Pβ,θbe the law of (T, d, ρ).

Note that it is straightforward to check from the properties of Poisson point process that for c > 0,

(T, d)under Pc2β, cθ(d)

= (T,1

cd)under Pβ,θ.(3)

Say a point σ∈ T (resp. σ∈ Rk) is a leaf if T \ {σ}(resp. Rk\ {σ}) is still connected. It is not

difﬁcult to see that almost surely Rkhas exactly k+ 1 leaves, which are the images of η0, η1, η2, . . . , ηk

in Rk. Let µkbe the empirical measure of Rkon the set of its leaves. It turns out ([9]) that (µk)k≥1

converges in the weak topology of Tto a limit µ, which is referred to as the mass measure of T. More-

over, µhas the following properties: it is non-atomic and supported on the set of leaves of T. Moreover,

let (Vj)j≥0be a sequence of i.i.d. points sampled according to µand let R0

kbe the smallest subtree of

Tcontaining V0, V1, V2,··· , Vkrooted at V0; then R0

khas the same distribution as Rk, the real tree

obtained from the ﬁrst kbranches in the previous construction. Note that Rkcan be seen as a determin-

istic function of Rk+1, and the same is true for R0

kand R0

k+1. Hence, (R0

m,R0

k)d

= (Rm,Rk)for all

m≥k≥1. Letting m→ ∞, we deduce that for all k≥1,

(T,R0

k)has the same law as (T,Rk)under Pβ,θ.(4)

It also follows from the previous construction that for each θi>0, the corresponding jointpoint

ξi,1will be identiﬁed with the endpoints of an inﬁnite number of branches. Denote by Bithe image of

ξi,1in T. For a real tree (T, d), we deﬁne the degree of a point σ∈Tas the possibly inﬁnite number

of connected components of T\ {σ}, and write it as deg(σ, T ). It will also be convenient to deﬁne

deg(σ, T ) = −∞ if σ /∈T. It is then not difﬁcult to see that deg(Bi,Rk)increases to inﬁnity as k

grows. To measure its growth rate, we introduce

Ψ(t) = 1

2βt2+X

i≥1

(e−θit−1 + θit)≤t2

2β+kθk2<∞, t ≥0.(5)

The assumptions (1) and (2) ensure that t7→ Ψ(t)is continuous, strictly increasing, and Ψ(+∞)=+∞.

Let Ψ−1be its inverse function. Recall the set Br∞(T)of points of inﬁnite degree in T. In Section 4.1,

we prove:

Proposition 1. We have Br∞(T) = {Bi:θi>0, i ≥1}a.s. For all σ∈ T , the following limit exists in

probability under Pβ,θ:

∆T(σ) := lim

k→∞

deg(σ, Rk)

Ψ−1(k).(6)

Moreover, ∆T(σ)>0if and only if σ∈Br∞(T); in that case we have ∆T(Bi) = θi, for each

Bi∈Br∞(T). Let (Vi)i≥0be a sequence of i.i.d. points of Twith common law µ, and let R0

∪1≤i≤kJV0, VkKbe the subtree spanning V0, V1, . . . , Vk. Then

deg(Bi,R0

k) : k≥1, i ≥1has the same law as deg(Bi,Rk) : k≥1, i ≥1under Pβ,θ.

As a consequence, we can replace Rkby R0

kin (6)and obtain the same limit almost surely.

We will refer to ∆T(σ)as the local time of σin T. Proposition 1implies that ∆T(σ)is a measurable

function in the Gromov–Prokhorov topology. It follows that almost surely

{θi>0 : i∈N}={∆T(σ)>0 : σ∈ T } ={∆T(σ) : σ∈Br∞(T)}

is a measurable function of (T, d, µ).

Let `∈Nand suppose θ`>0. Let m(`)=P1≤i≤`θiδBibe the ﬁnite measure on Twhich puts a

mass of size θito the point Bi. We have for all k≥1,

R0

k,m(`)(·∩R0

k)has the same law as Rk,m(`)(·∩Rk)under Pβ,θ.(7)

To see why this is true, we note that (7) above is merely a reformulation of Proposition 5(b) in [9], in

which Rkwas regarded as a discrete tree equipped with edge lengths and a subset of labeled vertices.

2.2 Approximations of the tree distance

The following result will allow us to recover the length of a uniform branch in Tby tracking the local

times of the points on that path. It is crucial to our approach for the reconstruction, which will essentially

rely on identifying the points of inﬁnite degree that used to be on any given path.

Proposition 2. Given the continuum random tree (T, d, µ), deﬁned under Pβ,θ. Let Vand V0be two

independent points in Twith distribution µ, let γθ() = Piθi1{θi>}, > 0. Suppose that Pi≥1θi=

∞. Then under Pβ,θ, we have

γθ()X

b∈JV,V 0K∩Br∞(T)

1{∆T(b)>}

→0

−−→ d(V, V 0)in probability. (8)

If the entries of θare all distinct, then the convergence in (8)also takes place almost surely.

As a consequence of Proposition 2, we can always ﬁnd a sequence k→0, which only depends on

(β, θ), so that for Pβ,θ-almost every realisation of T, we have

d(V, V 0) = lim

k→∞

γθ(k)X

b∈JV,V 0K∩Br∞(T)

1{∆T(b)>k}in the a.s. sense.(9)

Proof of the above proposition will be given in Section 4.2. For the moment, let us simply note that the

assumption Piθi=∞is always satisﬁed if β= 0.

2.3 Pruning continuum random trees

Given the continuum random tree (T, d, µ), deﬁned under Pβ,θ, we consider a pruning of Taccording

to a Poisson point measure. To that end, we ﬁrst introduce L, a σ-ﬁnite measure of T, which will serve

as the intensity measure of this Poisson point measure. The skeleton of (T, d)consists of the points of

degree at least two and is deﬁned as

Skel(T) = [

σ,σ0∈T

Kσ, σ0J,

where Kσ, σ0J=Jσ, σ0K\ {σ, σ0}is the open arc between σand σ0. Let `stand for the length measure

of T, which is a σ-ﬁnite measure concentrated on Skel(T)characterised by `(Jσ, σ0K) = d(σ, σ0)for all

σ, σ0∈ T . Recall also that to every point bof inﬁnite degree is associated a positive number ∆T(b), as

speciﬁed in Proposition 1. Recall the parameter βfrom (1). Let

L(dx) := β·`(dx) + X

b∈Br∞(T)

∆T(b)·δb(dx).(10)

We have L(Jσ, σ0K)∈(0,∞),Pβ,θ-a.s. for all distinct σ, σ0∈ T (see Lemma 5.1 of [13]).

Now let P={(ti, xi) : i≥1}be a Poisson point measure on R+× T of intensity dt ⊗ L(dx). An

atom (ti, xi)of Pis interpreted as a cut which disconnects the tree Tat location xiand at time ti. So the

pruning by Pamounts to cutting the skeleton of the tree at a rate proportional to βand removing each

branch point bof inﬁnite degree at an exponential time of rate ∆T(b). The above pruning process on T

induces a fragmentation process as follows. For t≥0, denote by Pt:= {xi:∃ti≤ts.t. (ti, xi)∈ P}

the set of the locations of cuts arriving before t; let us write T \ Ptfor the “forest” obtained from

Tby removing the points in Pt. Let µt= (µt(i))i≥1be the sequence of non zero µ-masses of the

components of T \Ptsorted in decreasing order. Alternatively, µtcan be recovered as the frequencies of

an exchangeable random partition ([10]). More precisely, let (Vi)i≥1be i.i.d. points of Twith common

distribution µ. For t≥0, say i∼tjif and only if i=jor JVi, VjK∩ Pt=∅. Then the equivalence

relation ∼tdeﬁnes a partition of N, denoted as Πt. Moreover, we have a.s.

i∼tj⇐⇒ Vj∈ Tt(Vi) := {σ∈ T :Pt∩JVi, σJ=∅}.(11)

For the block of Πtcontaining i, i.e. {j∈N:i∼tj}, its frequency, deﬁned by

lim

k→∞

kCard j: 1 ≤j≤k, j ∼ti,

exists a.s. by the Law of Large Numbers, and can be identiﬁed as µ(Tt(Vi)). Moreover, µtcoincides

with the rearrangement in decreasing order of the block frequencies of Πt.

2.4 Genealogy of the fragmentation and cut trees

The partition-valued process (Πt)t≥0has a natural genealogical structure: if s>t, then each block Bof

Πsis contained in some block B0of Πt; in that case, we say that Bis a descendant of B0. It turns out

that this genealogical structure can be encoded by another CRT called the cut tree, which also contains

information on the times of fragmentation events. This has been explored in [3,11,13,16]. Let us brieﬂy

recall the construction of the cut tree.

Write N0:= {0,1,2, . . . }. For i6=j, let

τij = inf{t > 0 : Pt∩JVi, VjK6=∅}(12)

be the ﬁrst time when a cut falls on JVi, VjK, which is distributed as an exponential variable of rate

L(JVi, VjK). We introduce a function δ:N0×N0→[0,∞]whose values are given as follows. Set

δ(i, i)=0for all i∈N0; let

δ(0, i) = δ(i, 0) = Z∞

µTs(Vi)ds ∈[0,+∞], i ∈N,(13)

where Ts(Vi)is the part of Tstill connected to Viat time s, as deﬁned in (11); for i, j ≥1and i6=j,

deﬁne

δ(i, j) = δ(j, i) = Z+∞

τij nµTs(Vi)+µTs(Vj)ods. (14)

Theorem 3 ([13], Theorem 3.5).(δ(i, j))i,j∈N0has the same distribution as (d(Vi+1, Vj+1))i,j∈N0under

Pβ,θ.

In particular, Theorem 3implies that δ(i, j)<∞almost surely for all i, j ∈N0. Furthermore, it can

be readily checked from the deﬁnitions (13) and (14) that δis a metric on N0which veriﬁes the four-point

condition, namely δ(i, j) + δ(k, l)≤max{δ(i, k) + δ(j, l), δ(j, k) + δ(i, l)}, for any i, j, k, l ∈N0. Let

(C, δ)be the metric completion of (N0, δ). It turns out that (C, δ)is connected, and thus a real tree. We

deﬁne 0to be its root. Denote by Sk=∪1≤i≤kJ0, iKthe subtree of Cspanning {0,1,2, . . . , k}and by

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

PRUNING,CUTTREES,ANDTHERECONSTRUCTIONPROBLEMNicolasBROUTIN*HuiHEMinminWANG§February3,2023AbstractWeconsiderapruningoftheinhomogeneouscontinuumrandomtrees,aswellasthecuttreesthatencodethegenealogiesofthefragmentationsthatcomewiththepruning.Weproposeanewapproachtothereconstructionproblem,whichhasbee...

展开>> 收起<<

PRUNING CUT TREES AND THE RECONSTRUCTION PROBLEM Nicolas B ROUTINHui H EMinmin W ANG February 3 2023.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

PRUNING CUT TREES AND THE RECONSTRUCTION PROBLEM Nicolas B ROUTINHui H EMinmin W ANG February 3 2023

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: