From trees to seeds: On the inference of the seed from large trees in the uniform attachment model

Sébastien Bubeck; Ronen Eldan; Elchanan Mossel; Miklós Z. Rácz

doi:10.3150/16-BEJ831

From trees to seeds: On the inference of the seed from large trees in the uniform attachment model

Sébastien Bubeck, Ronen Eldan, Elchanan Mossel, Miklós Z. Rácz

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.

Original language	English (US)
Pages (from-to)	2887-2916
Number of pages	30
Journal	Bernoulli
Volume	23
Issue number	4A
DOIs	https://doi.org/10.3150/16-BEJ831
State	Published - Nov 2017

All Science Journal Classification (ASJC) codes

Statistics and Probability

Keywords

Random trees
Seed tree
Statistical inference
Uniform attachment

Access to Document

10.3150/16-BEJ831

Cite this

@article{eca4756a03a842ca85ad49f0d1b84015,

title = "From trees to seeds: On the inference of the seed from large trees in the uniform attachment model",

abstract = "We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global {"}balancedness{"} properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.",

keywords = "Random trees, Seed tree, Statistical inference, Uniform attachment",

author = "S{\'e}bastien Bubeck and Ronen Eldan and Elchanan Mossel and R{\'a}cz, {Mikl{\'o}s Z.}",

note = "Publisher Copyright: {\textcopyright} 2017 ISI/BS.",

year = "2017",

month = nov,

doi = "10.3150/16-BEJ831",

language = "English (US)",

volume = "23",

pages = "2887--2916",

journal = "Bernoulli",

issn = "1350-7265",

publisher = "Bernoulli Society for Mathematical Statistics and Probability",

number = "4A",

}

TY - JOUR

T1 - From trees to seeds

T2 - On the inference of the seed from large trees in the uniform attachment model

AU - Bubeck, Sébastien

AU - Eldan, Ronen

AU - Mossel, Elchanan

AU - Rácz, Miklós Z.

PY - 2017/11

Y1 - 2017/11

N2 - We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.

AB - We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.

KW - Random trees

KW - Seed tree

KW - Statistical inference

KW - Uniform attachment

UR - http://www.scopus.com/inward/record.url?scp=85019086281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019086281&partnerID=8YFLogxK

U2 - 10.3150/16-BEJ831

DO - 10.3150/16-BEJ831

M3 - Article

AN - SCOPUS:85019086281

SN - 1350-7265

VL - 23

SP - 2887

EP - 2916

JO - Bernoulli

JF - Bernoulli

IS - 4A

ER -

From trees to seeds: On the inference of the seed from large trees in the uniform attachment model

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this