The number of accessible paths in the hypercube
<p style="text-align:justify;"> Motivated by an evolutionary biology question, we study the following problem: we consider the hypercube <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo fence="false" stretchy="false">{</mo> <mn...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Bernoulli Society for Mathematical Statistics and Probability
2015
|
| _version_ | 1797106901621669888 |
|---|---|
| author | Berestycki, J Brunet, E Shi, Z |
| author_facet | Berestycki, J Brunet, E Shi, Z |
| author_sort | Berestycki, J |
| collection | OXFORD |
| description | <p style="text-align:justify;"> Motivated by an evolutionary biology question, we study the following problem: we consider the hypercube <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mi>L</mi> </msup> </math> 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∈[0,1]. We study the number Θ 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 <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>x</mi> <mo>=</mo> <mi>X</mi> <mo>/</mo> <mi>L</mi> </math> then <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi mathvariant="normal">Θ<!-- Θ --></mi> <mo>/</mo> <mi>L</mi> </math> converges in law as <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>L</mi> <mo stretchy="false">→<!-- → --></mo> <mi mathvariant="normal">∞<!-- ∞ --></mi> </math> to e−X times the product of two standard independent exponential variables.<br/> 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 <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>x</mi> <mo>∈<!-- ∈ --></mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </math>. </p> |
| first_indexed | 2024-03-07T07:07:38Z |
| format | Journal article |
| id | oxford-uuid:5576e5e8-cc88-471c-9c75-5d46e90a564e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:07:38Z |
| publishDate | 2015 |
| publisher | Bernoulli Society for Mathematical Statistics and Probability |
| record_format | dspace |
| spelling | oxford-uuid:5576e5e8-cc88-471c-9c75-5d46e90a564e2022-05-26T15:32:48ZThe number of accessible paths in the hypercubeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5576e5e8-cc88-471c-9c75-5d46e90a564eEnglishSymplectic Elements at OxfordBernoulli Society for Mathematical Statistics and Probability2015Berestycki, JBrunet, EShi, Z <p style="text-align:justify;"> Motivated by an evolutionary biology question, we study the following problem: we consider the hypercube <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mi>L</mi> </msup> </math> 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∈[0,1]. We study the number Θ 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 <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>x</mi> <mo>=</mo> <mi>X</mi> <mo>/</mo> <mi>L</mi> </math> then <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi mathvariant="normal">Θ<!-- Θ --></mi> <mo>/</mo> <mi>L</mi> </math> converges in law as <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>L</mi> <mo stretchy="false">→<!-- → --></mo> <mi mathvariant="normal">∞<!-- ∞ --></mi> </math> to e−X times the product of two standard independent exponential variables.<br/> 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 <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>x</mi> <mo>∈<!-- ∈ --></mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </math>. </p> |
| spellingShingle | Berestycki, J Brunet, E Shi, Z The number of accessible paths in the hypercube |
| title | The number of accessible paths in the hypercube |
| title_full | The number of accessible paths in the hypercube |
| title_fullStr | The number of accessible paths in the hypercube |
| title_full_unstemmed | The number of accessible paths in the hypercube |
| title_short | The number of accessible paths in the hypercube |
| title_sort | number of accessible paths in the hypercube |
| work_keys_str_mv | AT berestyckij thenumberofaccessiblepathsinthehypercube AT brunete thenumberofaccessiblepathsinthehypercube AT shiz thenumberofaccessiblepathsinthehypercube AT berestyckij numberofaccessiblepathsinthehypercube AT brunete numberofaccessiblepathsinthehypercube AT shiz numberofaccessiblepathsinthehypercube |