Traveling Front Solutions to Directed Diffusion Limited Aggregation, Digital Search Trees and the Lempel-Ziv Data Compression Algorithm

Abstract

We use the traveling front approach to derive exact asymptotic results for the statistics of the number of particles in a class of directed diffusion limited aggregation models on a Cayley tree. We point out that some aspects of these models are closely connected to two different problems in computer science, namely the digital search tree problem in data structures and the Lempel-Ziv algorithm for data compression. The statistics of the number of particles studied here is related to the statistics of height in digital search trees which, in turn, is related to the statistics of the length of the longest word formed by the Lempel-Ziv algorithm. Implications of our results to these computer science problems are pointed out.

Revtex, 11 pages, 3 .eps figures included

Cited by in corpus (17)

• Front propagation into unstable states
• Extreme value statistics of correlated random variables: a pedagogical review
• Extremal statistics for stochastic resetting systems
• Anderson transition on the Cayley tree as a traveling wave critical point for various probability distributions
• Exact Solution of a Field Theory Model of Frontal Photopolymerization
• Universal Extremal Statistics in a Freely Expanding Jepsen Gas
• Extreme value statistics and arcsine laws for heterogeneous diffusion processes
• Phase Transition in the Aldous-Shields Model of Growing Trees
• Extremal statistics for a resetting Brownian motion before its first-passage time
• Exactly solvable reaction diffusion models on a Cayley tree
• Diffusion-Limited One-Species Reactions in the Bethe Lattice
• Random cascade models of multifractality : real-space renormalization and travelling-waves
• Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree : traveling-wave solution of the real space renormalization flow
• Velocity and diffusion coefficient of $A+A\leftrightarrow A$ reaction fronts in one dimension
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Autonomous models on a Cayley tree
• Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis