CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Volatility of Boolean functions

Johan Jonasson (Institutionen för matematiska vetenskaper, matematik) ; Jeffrey Steif (Institutionen för matematiska vetenskaper, matematik)

We study the volatility of the output of a Boolean function when the in- put bits undergo a natural dynamics. For n = 1, 2, . . ., let fn : {0, 1}mn → {0, 1} be a Boolean function and X(n)(t) = (X1(t), . . . , Xmn (t))t∈[0,∞) be a vector of i.i.d. stationary continuous time Markov chains on {0, 1} that jumpfrom0to1withratepn ∈[0,1]andfrom1to0withrateqn =1−pn. Our object of study will be Cn which is the number of state changes of fn(X(n)(t)) as a function of t during [0, 1]. We say that the family {fn}n≥1 is volatile if Cn → ∞ in distribution as n → ∞ and say that {fn}n≥1 is tame if {Cn}n≥1 is tight. We study these concepts in and of themselves as well as investigate their relationship with the recent notions of noise sensitiv- ity and noise stability. In addition, we study the question of lameness which means that P(Cn = 0) → 1 as n → ∞. Finally, we investigate these prop- erties for the majority function, iterated 3-majority, the AND/OR function on the binary tree and percolation on certain trees in various regimes.

Nyckelord: Boolean function, noise sensitivity, noise stability

Denna post skapades 2015-12-23.
CPL Pubid: 229074


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)



Chalmers infrastruktur