The number of accessible paths in the hypercube

Julien Berestycki; Éric Brunet; Zhan Shi

doi:10.3150/14-BEJ641

paper

The number of accessible paths in the hypercube

arXiv:1304.0246 · doi:10.3150/14-BEJ641

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, \dots, 1)$ which carries the value $1$ and $(0, 0, \dots, 0)$ which carries the value $x \in [0, 1]$ . We study the number $Θ$ of paths from vertex $(0, 0, \dots, 0)$ to the opposite vertex $(1, 1, \dots, 1)$ along which the values on the nodes form an increasing sequence. We show that if the value on $(0, 0, \dots, 0)$ is set to $x = X / L$ then $Θ/ L$ converges in law as $L \to \infty$ to $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 $x \in [0, 1]$ ).

Published at http://dx.doi.org/10.3150/14-BEJ641 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

The number of accessible paths in the hypercube

Abstract

References in corpus (5)

Cited by in corpus (12)