uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen, 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..
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 (Engelska)Ingår i: Annales de l'I.H.P. Probabilites et statistiques, ISSN 0246-0203, E-ISSN 1778-7017, Vol. 53, nr 4, s. 2135-2161Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2017. Vol. 53, nr 4, s. 2135-2161
Nyckelord [en]
Boolean functions, Sharp thresholds, Influences, Iterated majority function, Near-critical percolation
Nationell ämneskategori
Sannolikhetsteori och statistik
Identifikatorer
URN: urn:nbn:se:uu:diva-345263DOI: 10.1214/16-AIHP786ISI: 000416376500025OAI: oai:DiVA.org:uu-345263DiVA, id: diva2:1189215
Forskningsfinansiär
Knut och Alice Wallenbergs StiftelseVetenskapsrådet, 637-2013-7302Tillgänglig från: 2018-03-09 Skapad: 2018-03-09 Senast uppdaterad: 2018-03-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Ahlberg, Daniel

Sök vidare i DiVA

Av författaren/redaktören
Ahlberg, Daniel
Av organisationen
Analys och sannolikhetsteori
I samma tidskrift
Annales de l'I.H.P. Probabilites et statistiques
Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 485 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf