| 1. |
- Ahlberg, Daniel, 1982, et al.
(author)
-
Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
- 2017
-
In: Annales de linstitut Henri Poincare (B) Probability and Statistics. - 0246-0203 .- 1778-7017. ; 53:4, s. 2135-2161
-
Journal article (peer-reviewed)abstract
- 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.
|
|
| 2. |
- Bandyopadhyay, Antar, 1973, et al.
(author)
-
On the Cluster Size Distribution for Percolation on Some General Graphs
- 2010
-
In: Revista Matematica Iberoamericana. - 0213-2230 .- 2235-0616. ; 26, s. 529-550
-
Journal article (peer-reviewed)abstract
- We show that for any Cayley graph, the probability (at any p) that the cluster of the origin has size n decays at a well-defined exponential rate (possibly 0). For general graphs, we relate this rate being positive in the supercritical regime with the amenability/nonamenability of the underlying graph.
|
|
| 3. |
|
|
| 4. |
- Blachere, S., et al.
(author)
-
A crossover for the bad configurations of random walk in random scenery
- 2011
-
In: Annals of Probability. - : Institute of Mathematical Statistics. - 0091-1798 .- 2168-894X. ; 39:5, s. 2018-2041
-
Journal article (peer-reviewed)abstract
- In this paper, we consider a random walk and a random color scenery on Z. The increments of the walk and the colors of the scenery are assumed to be i.i.d. and to be independent of each other. We are interested in the random process of colors seen by the walk in the course of time. Bad configurations for this random process are the discontinuity points of the conditional probability distribution for the color seen at time zero given the colors seen at all later times. We focus on the case where the random walk has increments 0, +1 or -1 with probability epsilon, (1-epsilon)p and (1-epsilon)(1-p), respectively, with p is an element of [1/2, 1] and epsilon is an element of [0, 1), and where the scenery assigns the color black or white to the sites of Z with probability 1/2 each. We show that, remarkably, the set of bad configurations exhibits a crossover: for epsilon = 0 and p is an element of (1/2, 4/5) all configurations are bad, while for (p, epsilon) in an open neighborhood of (1, 0) all configurations are good. In addition, we show that for epsilon = 0 and p = 1/2 both bad and good configurations exist. We conjecture that for all epsilon is an element of [0, 1) the crossover value is unique and equals 4/5. Finally, we suggest an approach to handle the seemingly more difficult case where epsilon > 0 and p is an element of [1/2, 4/5), which will be pursued in future work.
|
|
| 5. |
- Broman, Erik, 1977, et al.
(author)
-
Dynamical Stability of Percolation for Some Interacting Particle Systems and $\epsilon$--Stability
- 2006
-
In: Annals of Probability. - : Institute of Mathematical Statistics. - 0091-1798 .- 2168-894X. ; 34, s. 539-576
-
Journal article (peer-reviewed)abstract
- In this paper we will investigate dynamic stability of percolation for the stochastic Ising model and the contact process. We also introduce the notion of downwards and upwards $\epsilon$-- stability which will be a key tool for our analysis.
|
|
| 6. |
- Broman, Erik, 1977, et al.
(author)
-
Exclusion sensitivity of Boolean functions
- 2013
-
In: Probability theory and related fields. - : Springer Science and Business Media LLC. - 0178-8051 .- 1432-2064. ; 155:3-4, s. 621-663
-
Journal article (peer-reviewed)abstract
- Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study “exclusion sensitivity” of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d. dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.
|
|
| 7. |
- Broman, Erik, 1977, et al.
(author)
-
Exclusion Sensitivity of Boolean Functions
- 2011
-
Journal article (other academic/artistic)abstract
- Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study ``exclusion sensitivity'' of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is more physical than the classical i.i.d. dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.
|
|
| 8. |
- Broman, Erik, 1977, et al.
(author)
-
Refinements of Stochastic Domination
- 2006
-
In: Probability theory and related fields. - : Springer Science and Business Media LLC. - 0178-8051 .- 1432-2064. ; 136:4, s. 587-603
-
Journal article (peer-reviewed)abstract
- In a recent paper by two of the authors, the concepts of upwards and downwards epsilon-movability were introduced, mainly as a technical tool for studying dynamical percolation of interacting particle systems. In this paper, we further explore these concepts which can be seen as refinements or quantifications of stochastic domination, and we relate them to previously studied concepts such as uniform insertion tolerance and extractability.
|
|
| 9. |
|
|
| 10. |
- Cox, J. T., et al.
(author)
-
Cutoff for the noisy voter model
- 2016
-
In: Annals of Applied Probability. - 1050-5164. ; 26:2, s. 917-932
-
Journal article (peer-reviewed)abstract
- Given a continuous time Markov Chain {q (x, y)} on a finite set S, the associated noisy voter model is the continuous time Markov chain on {0, 1}(S), which evolves in the following way: (1) for each two sites x and y in S, the state at site x changes to the value of the state at site y at rate q (x, y); (2) each site rerandomizes its state at rate 1. We show that if there is a uniform bound on the rates {q (x, y)} and the corresponding stationary distributions are almost uniform, then the mixing time has a sharp cutoff at time log vertical bar S vertical bar/2 with a window of order 1. Lubetzky and Sly proved cutoff with a window of order 1 for the stochastic Ising model on toroids; we obtain the special case of their result for the cycle as a consequence of our result. Finally, we consider the model on a star and demonstrate the surprising phenomenon that the time it takes for the chain started at all ones to become close in total variation to the chain started at all zeros is of smaller order than the mixing time.
|
|
