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

DOI10.1017/S026996480000084XzbMATH Open1134.68592OpenAlexW2009339318MaRDI QIDQ3415892FDOQ3415892

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On Quasi-Stationary distributions in absorbing discrete-time finite Markov chains
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• Improving time and space efficiency in generalized binary search trees
• 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
• Branching processes in the analysis of the heights of trees

Cited In (33)

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