The number of accessible paths in the hypercube

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

Zhan Shi, Julien Berestycki, Éric Brunet

Publication date: 1 April 2016

Published in: Bernoulli (Search for Journal in Brave)

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]$).

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

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

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)

Cites Work

• Title not available (Why is that?)
• A conditional limit theorem for the frontier of a branching Brownian motion
• A simple stochastic gene substitution model
• On the existence of accessible paths in various models of fitness landscapes
• Point-distinguishing chromatic index of the union of paths
• Accessibility percolation with backsteps
• A simple model for the balance between selection and mutation
• Title not available (Why is that?)
• Increasing paths in regular trees

Cited In (17)

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

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)