The Power of Choice in the Construction of Recursive Trees

Hosam M. Mahmoud ()
Additional contact information
Hosam M. Mahmoud: The George Washington University

Methodology and Computing in Applied Probability, 2010, vol. 12, issue 4, 763-773

Abstract: Abstract The power of choice is known to change the character of random structures and produce desirable optimization effects. We discuss generalizations of random recursive trees, grown under the choice to meet optimization criteria. Specifically, we discuss the random k-minimal (k-maximal) label recursive tree, where a set of k candidate parents, instead of one as in the usual recursive tree, is selected and the node with minimal (maximal) label among them is assigned as parent for the next node. These models are proposed as alternatives for D’Souza et al. (Eur Phys J B59:535–543, 2007) minimal and maximal depth models. The advantage of the label models is that they are tractable and at the same time provide approximations and bounds for the depth models. For the depth of nodes in label models we give the average behavior and exact distributions involving Stirling’s numbers and derive Gaussian limit laws.

Keywords: Random structure; Random tree; Gaussian law; Stirling number; Power of choice; Primary 60C05; 60F05; 05A05; 05C05 (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-009-9159-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:12:y:2010:i:4:d:10.1007_s11009-009-9159-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-009-9159-x

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().