The number of accessible paths in the hypercube

DOI10.3150/14-BEJ641zbMATH Open1341.60103MaRDI QIDQ265261FDOQ265261

Authors Julien Berestycki, Éric Brunet, Zhan Shi

Publication date 1 April 2016

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0246

zbMATH Keywords

treesbranching processesevolutionary biologypercolation

Mathematics Subject Classification ID

Problems related to evolution (92D15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: Motivated by an evolutionary biology question, we study the following problem: we consider the hypercube ${0,1}^L$ where each node carries an independent random variable uniformly distributed on $[0,1]$, except $(1,1,ldots,1)$ which carries the value $1$ and $(0,0,ldots,0)$ which carries the value $xin[0,1]$. We study the number $Theta$ of paths from vertex $(0,0,ldots,0)$ to the opposite vertex $(1,1,ldots,1)$ along which the values on the nodes form an increasing sequence. We show that if the value on $(0,0,ldots,0)$ is set to $x=X/L$ then $Theta/L$ converges in law as $Loinfty$ to $mathrm{e}^{-X}$ times the product of two standard independent exponential variables. As a first step in the analysis, we study the same question when the graph is that of a tree where the root has arity $L$, each node at level 1 has arity $L-1$, ldots, and the nodes at level $L-1$ have only one offspring which are the leaves of the tree (all the leaves are assigned the value 1, the root the value $xin[0,1]$).

Recommendations

• Accessibility percolation with backsteps
• Phase transition for accessibility percolation on hypercubes
• Increasing paths in regular trees
• On the existence of accessible paths in various models of fitness landscapes
• Accessibility percolation with crossing valleys on \(n\)-ary trees

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• A conditional limit theorem for the frontier of a branching Brownian motion
• A simple model for the balance between selection and mutation
• A simple stochastic gene substitution model
• Accessibility percolation with backsteps
• Increasing paths in regular trees
• On the existence of accessible paths in various models of fitness landscapes
• Point-distinguishing chromatic index of the union of paths.

Cited in

(18)

• Evolutionary accessibility of random and structured fitness landscapes
• Phase transition for accessibility percolation on hypercubes
• Undirected polymers in random environment: path properties in the mean field limit
• Accessibility percolation on Cartesian power graphs
• RMF accessibility percolation on oriented graphs
• Galton-Watson processes in varying environment and accessibility percolation
• A general multi-scale description of metastable adaptive motion across fitness valleys
• Accessibility percolation with crossing valleys on \(n\)-ary trees
• Increasing paths in regular trees
• On the existence of accessibility in a tree-indexed percolation model
• Accessibility percolation on random rooted labeled trees
• Measuring epistasis in fitness landscapes: the correlation of fitness effects of mutations
• Oriented first passage percolation in the mean field limit. II: The extremal process
• From adaptive dynamics to adaptive walks
• Accessibility percolation with backsteps
• Stochastic individual-based models with power law mutation rate on a general finite trait space
• Universality classes of interaction structures for NK fitness landscapes
• The path-distance-width of hypercubes

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The number of accessible paths in the hypercube

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