Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
arXiv:cond-mat/0109313 · doi:10.1103/PhysRevE.65.036127
Abstract
We study the statistics of height and balanced height in the binary search tree problem in computer science. The search tree problem is first mapped to a fragmentation problem which is then further mapped to a modified directed polymer problem on a Cayley tree. We employ the techniques of traveling fronts to solve the polymer problem and translate back to derive exact asymptotic properties in the original search tree problem. The second mapping allows us not only to re-derive the already known results for random binary trees but to obtain new exact results for search trees where the entries arrive according to an arbitrary distribution, not necessarily randomly. Besides it allows us to derive the asymptotic shape of the full probability distribution of height and not just its moments. Our results are then generalized to -ary search trees with arbitrary distribution. An attempt has been made to make the article accessible to both physicists and computer scientists.
16 pages, two-column revtex
References in corpus (2)
Cited by in corpus (40)
- Front propagation into unstable states
- Extreme value statistics of correlated random variables: a pedagogical review
- Physics of the Riemann Hypothesis
- Random Convex Hulls and Extreme Value Statistics
- A branching random walk seen from the tip
- Statistics at the tip of a branching random walk and the delay of traveling waves
- Spatial extent of an outbreak in animal epidemics
- Extreme Value Statistics and Traveling Fronts: Various Applications
- Density of near-extreme events
- Maximal height statistics for 1/f^alpha signals
- Extremal statistics for stochastic resetting systems
- Extreme values and fat tails of multifractal fluctuations
- Anderson transition on the Cayley tree as a traveling wave critical point for various probability distributions
- Shattering Transitions in Collision-Induced Fragmentation
- Traveling Front Solutions to Directed Diffusion Limited Aggregation, Digital Search Trees and the Lempel-Ziv Data Compression Algorithm
- Universal Extremal Statistics in a Freely Expanding Jepsen Gas
- Uncovering latent singularities from multifractal scaling laws in mixed asymptotic regime. Application to turbulence
- Extreme value statistics and arcsine laws for heterogeneous diffusion processes
- Time to reach the maximum for a stationary stochastic process
- Exact extreme, order and sum statistics in a class of strongly correlated system
- Discrete Sampling of Extreme Events Modifies Their Statistics
- Extreme value statistics and return intervals in long-range correlated uniform deviates
- Phase Transition in a Random Fragmentation Problem with Applications to Computer Science
- Approximate analysis of search algorithms with "physical" methods
- On the genealogy of branching random walks and of directed polymers
- Phase Transition in the Aldous-Shields Model of Growing Trees
- Fragmentation of fractal random structures
- Extremal statistics for a resetting Brownian motion before its first-passage time
- On the critical weight statistics of the Random Energy Model and of the Directed Polymer on the Cayley Tree
- Random cascade models of multifractality : real-space renormalization and travelling-waves
- Records in Fractal Stochastic Processes
- Darcy's law of yield stress fluids on a treelike network
- Spin-glass chain in a magnetic field : influence of the disorder distribution on ground state properties and low-energy excitations
- Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree : traveling-wave solution of the real space renormalization flow
- Fluctuating Fronts as Correlated Extreme Value Problems: An Example of Gaussian Statistics
- Random walk through a fertile site
- Continuum Cascade Model: Branching Random Walk for Traveling Wave
- Growth over time-correlated disorder: a spectral approach to Mean-field
- Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis
- Monotonicity in the averaging process