The number of accessible paths in the hypercube -

Berestycki, Julien and Brunet, Eric and Shi, ZhanBERNOULLI 22,

653-680 (2016) LPS

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