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

DOI10.1017/S026996480000084XzbMath1134.68592OpenAlexW2009339318MaRDI QIDQ3415892

David J. Aldous, José Luis Palacios, Barry Flannery

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)

Related Items (28)

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

Cites Work

• Unnamed Item
• Improving time and space efficiency in generalized binary search trees
• Branching processes in the analysis of the heights of trees
• On random 2-3 trees
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• The analysis of a fringe heuristic for binary search trees
• The theory of fringe analysis and its application to 23 trees and b-trees
• On Quasi-Stationary distributions in absorbing discrete-time finite Markov chains

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