Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
From MaRDI portal
Publication:3415892
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
Related Items (26)
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 ⋮ Stochastic approximation of quasi-stationary distributions for diffusion processes in a bounded domain ⋮ 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
