Phase transition in a random fragmentation problem with applications to computer science

DOI10.1088/0305-4470/35/32/101MaRDI QIDQ4466006zbMATH OpenOpenAlexFDO

Authors David S. Dean, Satya N. Majumdar

Publication date 9 June 2004

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0205034

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We study a fragmentation problem where an initial object of size x is broken into m random pieces provided x>x_0 where x_0 is an atomic cut-off. Subsequently the fragmentation process continues for each of those daughter pieces whose sizes are bigger than x_0. The process stops when all the fragments have sizes smaller than x_0. We show that the fluctuation of the total number of splitting events, characterized by the variance, generically undergoes a nontrivial phase transition as one tunes the branching number m through a critical value m=m_c. For m<m_c, the fluctuations are Gaussian where as for m>m_c they are anomalously large and non-Gaussian. We apply this general result to analyze two different search algorithms in computer science.

Recommendations

• The size of random fragmentation trees
• On two fragmentation schemes with algebraic splitting probability
• A phase transition for the heights of a fragmentation tree
• Statistical aspects of random fragmentations
• On Random Fragmentations Arising From Binary Splitting

Cited in

(10)

• On Random Fragmentations Arising From Binary Splitting
• Statistical aspects of random fragmentations
• Phase transition in a generalized Eden growth model on a tree
• A phase transition for the heights of a fragmentation tree
• Fragment size distributions in random fragmentations with cutoff
• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Dependence and phase changes in random \(m\)-ary search trees
• Singularity analysis, Hadamard products, and tree recurrences
• Moments of a non‐homogenous bi‐variate fragmentation process using integral equations tools
• The size of random fragmentation trees

This page was built for publication: Phase transition in a random fragmentation problem with applications to computer science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4466006)