Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains

DOI10.1017/S026996480000084XMaRDI QIDQ3415892zbMATH OpenOpenAlexFDO

Authors David Aldous, Barry Flannery, José Luis Palacios

Publication date 19 January 2007

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s026996480000084x

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Stochastic processes (60G99)

Recommendations

• Pólya urn models and connections to random trees: a review
• Polya Urn Models
• A randomly reinforced urn
• Sequential urn schemes and birth processes
• Some limit theorems on distributional patterns of balls in urns

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• Branching processes in the analysis of the heights of trees
• Improving time and space efficiency in generalized binary search trees
• On Quasi-Stationary distributions in absorbing discrete-time finite Markov chains
• On random 2-3 trees
• The analysis of a fringe heuristic for binary search trees
• The theory of fringe analysis and its application to 23 trees and b-trees

Cited in

(33)

• Central limit theorem for stationary Fleming-Viot particle systems in finite spaces
• Balancing \(m\)-ary search trees with compressions on the fringe
• Stochastic approximation of the paths of killed Markov processes conditioned on survival
• First-passage properties of the Pólya urn process
• Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees.
• Variance in randomized play-the-winner clinical trials
• B-urns
• Analytic urns
• Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
• On the expected height of fringe-blanced trees
• Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes
• The limiting behaviour of a stochastic patch occupancy model
• Empirical measure large deviations for reinforced chains on finite spaces
• An approximation scheme for quasi-stationary distributions of killed diffusions
• Random sprouts as internet models, and Pólya processes
• Stochastic approximation of quasi-stationary distributions on compact spaces and applications
• Limit Theorems for Random Triangular URN Schemes
• Approximating quasi-stationary distributions with interacting reinforced random walks
• Universal Limit Laws for Depths in Random Trees
• On the dynamics of systems of urns
• A Markov chain with number-theoretic limit distribution
• Stochastic approximation of quasi-stationary distributions for diffusion processes in a bounded domain
• Analysis of a stochastic approximation algorithm for computing quasi-stationary distributions
• Pólya urn models and connections to random trees: a review
• Assessing mutualistic metacommunity capacity by integrating spatial and interaction networks
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Extinction and quasi-stationarity for discrete-time, endemic SIS and SIR models
• On rotations in fringe-balanced binary trees
• Sampling using adaptive regenerative processes
• Mean and variance of balanced Pólya urns
• Occupancy urn models in the analysis of algorithms
• The size of random bucket trees via urn models
• An almost sure result for path lengths in binary search trees

This page was built for publication: Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3415892)