Subtractive random forests

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Broutin, Nicolas
• dc.contributor.author Devroye, Luc
• dc.contributor.author Lugosi, Gábor
• dc.contributor.author Oliveira, Roberto Imbuzeiro
• dc.date.accessioned 2025-06-17T15:28:47Z
• dc.date.available 2025-06-17T15:28:47Z
• dc.date.issued 2024
• dc.date.updated 2025-06-17T15:28:47Z
• dc.description.abstract Motivated by online recommendation systems, we study a family of random forests. The vertices of the forest are labeled by integers. Each non-positive integer i ≤ 0 is the root of a tree. Vertices labeled by positive integers n ≥ 1 are attached sequentially such that the parent of vertex n is n−Zn, where the Zn are i.i.d. random variables taking values in Z+. We study several characteristics of the resulting random forest. In particular, we establish bounds for the expected tree sizes, the number of trees in the forest, the number of leaves, the maximum degree, and the height of the forest. We show that for all distributions of the Zn, the forest contains at most one infinite tree, almost surely. If EZn < ∞, then there is a unique infinite tree and the total size of the remaining trees is finite, with finite expected value if EZ2 n < ∞. If EZn = ∞ then almost surely all trees are finite.
• dc.description.sponsorship Luc Devroye is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) G. Lugosi acknowledges the support of Ayudas Fundación BBVA a Proyectos de Investigación Científica 2021 and the Spanish Ministry of Economy and Competitiveness grant PID2022-138268NB-I00, financed by MCIN/AEI/10.13039/501100011033, FSE+MTM2015-67304-P, and FEDER, EU.
• dc.format.mimetype application/pdf
• dc.identifier.citation Broutin N, Devroye L, Lugosi G, Oliveira RI. Subtractive random forests. ALEA, Lat. Am. J. Probab. Math. Stat. 2024;21:575-91. DOI: 10.30757/ALEA.v21-23
• dc.identifier.doi http://dx.doi.org/10.30757/ALEA.v21-23
• dc.identifier.issn 1980-0436
• dc.identifier.uri http://hdl.handle.net/10230/70706
• dc.language.iso eng
• dc.publisher Institute for Applied and Pure Mathematics (IMPA)
• dc.relation.ispartof Alea: Latin American Journal of Probability and Mathematical Statistics. 2024;21:575-91
• dc.relation.projectID info:eu-repo/grantAgreement/ES/3PE/PID2022-138268NB-I00
• dc.rights ALEA is an electronic journal of the Latin-american probability and statistical community which provides open access to all of its content and uses only free programs. Authors are allowed to deposit their published article into their institutional repository, freely and with no embargo, as long as they acknowledge the source of the paper.
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Subtractive random forests
• dc.subject.keyword Recommendation systems
• dc.subject.keyword Ancestral process
• dc.title Subtractive random forests
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion