uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory. Inst Nacl Matemat Pura & Aplicada, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, Brazil.;Uppsala Univ, Dept Math, SE-75106 Uppsala, Sweden..
Univ Gothenburg, Chalmers Univ Technol, Math Sci, SE-41296 Gothenburg, Sweden..
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..
2017 (English)In: Annales de l'I.H.P. Probabilites et statistiques, ISSN 0246-0203, E-ISSN 1778-7017, Vol. 53, no 4, p. 2135-2161Article in journal (Refereed) Published
Abstract [en]

Consider a monotone Boolean function f : {0, 1}(n) -> {0, 1} and the canonical monotone coupling {eta(p) : p is an element of [0, 1]} of an element in {0, 1}(n) chosen according to product measure with intensity p is an element of [0, 1]. The random point p is an element of [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 majority and 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.

Place, publisher, year, edition, pages
2017. Vol. 53, no 4, p. 2135-2161
Keywords [en]
Boolean functions, Sharp thresholds, Influences, Iterated majority function, Near-critical percolation
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-345263DOI: 10.1214/16-AIHP786ISI: 000416376500025OAI: oai:DiVA.org:uu-345263DiVA, id: diva2:1189215
Funder
Knut and Alice Wallenberg FoundationSwedish Research Council, 637-2013-7302Available from: 2018-03-09 Created: 2018-03-09 Last updated: 2018-03-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Ahlberg, Daniel

Search in DiVA

By author/editor
Ahlberg, Daniel
By organisation
Analysis and Probability Theory
In the same journal
Annales de l'I.H.P. Probabilites et statistiques
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 70 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf