Rigorous Upper Bound for the Discrete Bak–Sneppen Model
Volkov, Stanislav LU
(2022)
In Journal of Statistical Physics
186(1).
- Abstract
Fix some p∈ [0 , 1] and a positive integer n. The discrete Bak–Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a minimum element (typically, zero) is chosen with equal probability, and it is then replaced alongside both its neighbours by independent Bernoulli(p) random variables. Let ν(n)(p) be the probability that an element of this sequence equals one under the stationary distribution of this Markov chain. It was shown in Barbay and Kenyon (in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 928–933, SIAM, Philadelphia, PA, 2001) that... (More)
Fix some p∈ [0 , 1] and a positive integer n. The discrete Bak–Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a minimum element (typically, zero) is chosen with equal probability, and it is then replaced alongside both its neighbours by independent Bernoulli(p) random variables. Let ν(n)(p) be the probability that an element of this sequence equals one under the stationary distribution of this Markov chain. It was shown in Barbay and Kenyon (in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 928–933, SIAM, Philadelphia, PA, 2001) that ν(n)(p) → 1 as n→ ∞ when p> 0.54 ⋯ ; the proof there is, alas, not rigorous. The complimentary fact that lim supn→∞ν(n)(p)<1 for p∈ (0 , p′) for some p′> 0 is much harder; this was eventually shown in Meester and Znamenski (J Stat Phys 109:987–1004, 2002). The purpose of this note is to provide a rigorous proof of the result from Barbay and Kenyon (in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 928–933, SIAM, Philadelphia, PA, 2001), as well as to improve it, by showing that ν(n)(p) → 1 when p> 0.45. (Our method, in fact, shows that with some finer tuning the same is true for p> 0.419533.)
(Less)
- author
- Volkov, Stanislav
LU
- organization
- publishing date
- 2022-01-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Bak–Sneppen model, Renewal theory, Self-organized criticality
- in
- Journal of Statistical Physics
- volume
- 186
- issue
- 1
- article number
- 8
- publisher
- Springer
- external identifiers
-
- scopus:85120922629
- ISSN
- 0022-4715
- DOI
- 10.1007/s10955-021-02838-7
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2021, The Author(s).
- id
- cf80cc07-eb3a-4562-9c25-0ec843781dd3
- date added to LUP
- 2022-01-27 11:06:40
- date last changed
- 2022-04-19 19:29:18
@article{cf80cc07-eb3a-4562-9c25-0ec843781dd3,
abstract = {{<p>Fix some p∈ [0 , 1] and a positive integer n. The discrete Bak–Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a minimum element (typically, zero) is chosen with equal probability, and it is then replaced alongside both its neighbours by independent Bernoulli(p) random variables. Let ν<sup>(</sup><sup>n</sup><sup>)</sup>(p) be the probability that an element of this sequence equals one under the stationary distribution of this Markov chain. It was shown in Barbay and Kenyon (in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 928–933, SIAM, Philadelphia, PA, 2001) that ν<sup>(</sup><sup>n</sup><sup>)</sup>(p) → 1 as n→ ∞ when p> 0.54 ⋯ ; the proof there is, alas, not rigorous. The complimentary fact that lim supn→∞ν(n)(p)<1 for p∈ (0 , p<sup>′</sup>) for some p<sup>′</sup>> 0 is much harder; this was eventually shown in Meester and Znamenski (J Stat Phys 109:987–1004, 2002). The purpose of this note is to provide a rigorous proof of the result from Barbay and Kenyon (in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 928–933, SIAM, Philadelphia, PA, 2001), as well as to improve it, by showing that ν<sup>(</sup><sup>n</sup><sup>)</sup>(p) → 1 when p> 0.45. (Our method, in fact, shows that with some finer tuning the same is true for p> 0.419533.)</p>}},
author = {{Volkov, Stanislav}},
issn = {{0022-4715}},
keywords = {{Bak–Sneppen model; Renewal theory; Self-organized criticality}},
language = {{eng}},
month = {{01}},
number = {{1}},
publisher = {{Springer}},
series = {{Journal of Statistical Physics}},
title = {{Rigorous Upper Bound for the Discrete Bak–Sneppen Model}},
url = {{http://dx.doi.org/10.1007/s10955-021-02838-7}},
doi = {{10.1007/s10955-021-02838-7}},
volume = {{186}},
year = {{2022}},
}