Search: onr:"swepub:oai:research.chalmers.se:6d706078-9dd5-4190-a294-cb8defa5b51f" >
Scaling limits for ...
Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
-
- Ahlberg, Daniel, 1982 (author)
- Uppsala universitet,Analys och sannolikhetsteori,Inst Nacl Matemat Pura & Aplicada, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, Brazil.;Uppsala Univ, Dept Math, SE-75106 Uppsala, Sweden.
-
- Steif, Jeffrey, 1960 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper,Department of Mathematical Sciences,Univ Gothenburg, Chalmers Univ Technol, Math Sci, SE-41296 Gothenburg, Sweden.
-
- Pete, Gabor (author)
- Magyar Tudomanyos Akademia,Hungarian Academy of Sciences,Budapesti Muszaki es Gazdasagtudomanyi Egyetem,Budapest University of Technology and Economics,Hungarian Acad Sci, Renyi Inst, 13-15 Realtanoda U, H-1053 Budapest, Hungary.;Budapest Univ Technol & Econ, Inst Math, 1 Egry Jozsef U, H-1111 Budapest, Hungary.
-
(creator_code:org_t)
- 2017
- 2017
- English.
-
In: Annales de linstitut Henri Poincare (B) Probability and Statistics. - 0246-0203 .- 1778-7017. ; 53:4, s. 2135-2161
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://research.cha...
-
https://gup.ub.gu.se...
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- Consider a monotone Boolean function f:{0,1}^n \to {0,1} and the canonical monotone coupling {eta_p:p in [0,1]} of an element in {0,1}^n chosen according to product measure with intensity p in [0,1]. The random point p in [0,1] where f(eta_p) flips from 0 to 1 is often concentrated near a particular point, thus exhibiting a threshold phenomenon. For a sequence of such Boolean functions, we peer closely into this threshold window and consider, for large n, the limiting distribution (properly normalized to be nondegenerate) of this random point where the Boolean function switches from being 0 to 1. We determine this distribution for a number of the Boolean functions which are typically studied and pay particular attention to the functions corresponding to iterated majorityand percolation crossings. It turns out that these limiting distributions have quite varying behavior. In fact, we show that any nondegenerate probability measure on R arises in this way for some sequence of Boolean functions.
Subject headings
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Probability Theory and Statistics (hsv//eng)
Keyword
- near- critical percolation
- sharp thresholds
- iterated majority function
- Boolean functions
- influences
- Boolean functions; sharp thresholds; influences; iterated majority function; near- critical percolation
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database