Recent papers

L. Köhler-Schindler and J. Steif
A study of distributional complexity measures for Boolean functions
preprint.

Abstract. A number of complexity measures for Boolean functions have previously been introduced. These include
(1) sensitivity, (2) block sensitivity, (3) witness complexity, (4) subcube partition complexity and (5) algorithmic
complexity. Each of these is concerned with ``worst-case'' inputs. It has been shown that there is ``asymptotic separation''
between these complexity measures and very recently, due to the work of Huang, it has been established that they are all
``polynomially related''. In this paper, we study the notion of distributional complexity where the input bits are independent
and one considers all of the above notions in expectation. We obtain a number of results concerning distributional complexity
measures, among others addressing the above concepts of ``asymptotic separation'' and being ``polynomially related'' in this
context. We introduce a new distributional complexity measure, local witness complexity, which only makes sense in the
distributional context and we also study a new version of algorithmic complexity which involves partial information.
Many interesting examples are presented including some related to percolation. The latter connects a number of the recent
developments in percolation theory over the last two decades with the study of complexity measures in theoretical computer science.
L. Landgren and J. Steif
A new framework for identifying most reliable graphs and a correction to the K_{3,3}-theorem
preprint.

Abstract. Given a finite connected multigraph G=(V,E), the all-terminal reliability function R(G,p) is the probability
that G remains connected under percolation with parameter p. We develop new results concerning the question
of which (multi)graphs G maximize R(G,p) for a given number of vertices n, edges m and a given parameter
p---such graphs are called optimally reliable graphs---paying particular attention to uniqueness and to whether the answer
depends upon p.

We generalize the concept of a distillation, and build a framework which we use to identify all optimally reliable
graphs for which m-n is in {1,2,3}. These graphs are uniformly optimal in p. Many of them have been previously
identified, but there are serious problems with these treatments, especially for the case m-n=3. We also obtain some
partial results for m-n is in {4,5}.

For m-n=2, we show that the standard reference by Boesch, Li and Suffel contains a serious flaw; it uses a claim for
which we give a counterexample. Two preceding papers which deal with the same question overlook the same key step.
Our solution is self-contained.

For m-n=3, the optimal graphs were incorrectly identified by Wang in 1994---following a conjecture by
Boesch et al.---in the infinite number of cases where m= 5 mod(9) and m>= 14. This erroneous result,
which concerns subdivisions of K_{3,3}, has been cited extensively and the mistake has not been detected.
Furthermore, while the optimal graphs were correctly identified for other values of m, the proof is incorrect,
as it also uses a claim for which we give a counterexample. Our proof of the rectified statement is self-contained.

Regarding m-n=4, it was recently shown by Romero and Safe that the optimal graph depends upon p for infinitely
many m. We find a new such set of m-values, which gives a different perspective on why this phenomenon occurs.
This leads us to conjecture that there are only finitely many m for which there are uniformly optimal graphs
when m-n=4, but that, for m-n=5, there are again infinitely many uniformly optimal graphs. We hope that
our general results and methods will be useful for continued investigations.
M. Forsström, N. Gantert and J. Steif
Poisson Representable Processes
submitted.

Abstract. Motivated by Alain-Sol Sznitman's interlacement process, we consider the set of {0,1}-valued
processes which can be constructed in an analogous way, namely as a union of sets coming from a Poisson
process on a collection of sets. Our main focus is to determine which processes are representable in this way.
Some of our results are as follows. (1) All positively associated Markov chains and a large class of renewal
processes are so representable. (2) Whether an average of two product measures, with close densities, on n
variables, is representable is related to the zeroes of the polylogarithm functions. (3) Using (2), we show that
a number of tree indexed Markov chains as well as the Ising model on Z^d, d >= 2 for certain parameters are
not so representable. (4) The collection of permutation invariant processes which are representable corresponds
exactly to the set of infinitely divisible random variables on [0,\infty] via a certain transformation. (5) The
supercritical (low temperature) Curie-Weiss model is not representable for large n.
J. Jonasson, J. Steif and O. Zetterqvist
Noise Sensitivity and Stability of Deep Neural Networks for Binary Classification
Stochastic Processes and their applications, 165, (2023), 130-167.

Abstract. A first step is taken towards understanding often observed non-robustness phenomena
of deep neural net (DNN) classifiers. This is done from the perspective of Boolean functions by
asking if certain sequences of Boolean functions represented by common DNN models are noise
sensitive or noise stable, concepts defined in the Boolean function literature. Due to the natural
randomness in DNN models, these concepts are extended to annealed and quenched versions.
Here we sort out the relation between these definitions and investigate the properties of two standard
DNN architectures, the fully connected and convolutional models, when initiated with Gaussian weights.
B. G. Franzen, J. Steif and J. Wästlund
Where to stand when playing darts?,
ALEA. Latin American Journal of Probability and Mathematical Statistics, 18, (2021), no. 2, 1561-1583.

Abstract. This paper analyzes the question of where one should stand when playing darts.
If one stands at distance d>0 and aims at a in R^n, then the dart (modelled by a random
vector X in R^n) hits a random point given by a+dX. Next, given a payoff function
f, one considers \sup_a Ef(a+dX) and asks if this is decreasing in d; i.e., whether it is
better to stand closer rather than farther from the target. Perhaps surprisingly, this is
not always the case and understanding when this does or does not occur is the purpose
of this paper.

We show that if X has a so-called selfdecomposable distribution, then it is always better
to stand closer for any payoff function. This class includes all stable distributions as
well as many more.

On the other hand, if the payoff function is cos(x), then it is always better to stand closer
if and only if the characteristic function |phi_X(t)| is decreasing on [0,\infty). We will then
show that if there are at least two point masses, then it is not always better to stand closer
using cos(x). If there is a single point mass, one can find a different payoff function to
obtain this phenomenon.

Another large class of darts X for which there are bounded continuous payoff functions for
which it is not always better to stand closer are distributions with compact support. This
will be obtained by using the fact that the Fourier transform of such distributions has a zero
in the complex plane. This argument will work whenever there is a complex zero of the
Fourier transform.

Finally, we analyze if the property of it being better to stand closer is closed under
convolution and/or limits.
M. Palö Forsström and J. Steif
Divide and color representations for threshold Gaussian and stable vectors,
Electronic Journal of Probability, Vol. 25, (2020) paper no. 54, 1-45.

Abstract. We study the question of when a {0,1}-valued threshold process associated
to a mean zero Gaussian or a symmetric stable vector corresponds to a divide and color
(DC) process. This means that the process corresponding to fixing a threshold level h and
letting a 1 correspond to the variable being larger than h arises from a random partition
of the index set followed by coloring all elements in each partition element 1 or 0
with probabilities p and 1-p, independently for different partition elements.

While it turns out that all discrete Gaussian free fields yield a DC process when the threshold
is zero, for general $n$-dimensional mean zero, variance one Gaussian vectors with nonnegative
covariances, this is true in general when n=3 but is false for n=4.

The behavior is quite different depending on whether the threshold level h is zero or not and we
show that there is no general monotonicity in h in either direction. We also show that all constant
variance discrete Gaussian free fields with a finite number of variables yield DC processes for large
thresholds.

In the stable case, for the simplest nontrivial symmetric stable vector with three variables, we obtain
a phase transition in the stability exponent alpha at the surprising value of 1/2; if the index of stability
is larger than 1/2, then the process yields a DC process for large h while if the index of stability
is smaller than 1/2, then this is not the case.
M. Palö Forsström and J. Steif
An analysis of the induced linear operators associated to divide and color models,
Journal of Theoretical Probability 34, (2021), 1043-1060.

Abstract. We study the natural linear operators associated to divide and color (DC) models. The degree
of nonuniqueness of the random partition yielding a DC model is directly related to the dimension of
the kernel of these linear operators. We determine exactly the dimension of these kernels as well as
analyze a permutation-invariant version. We also obtain properties of the solution set for certain parameter
values which will be important in (1) showing that large threshold discrete Gaussian free fields are DC
models and in (2) analyzing when the Ising model with a positive external field is a DC model, both in
future work. However, even here, we give an application to the Ising model on a triangle.
M. Palö Forsström and J. Steif
A formula for hidden regular variation behavior for symmetric stable distributions,
Extremes 23 (2020), no. 4, 667-691.

Abstract. We develop a formula for the power-law decay of various sets for symmetric stable random
vectors in terms of how many vectors from the support of the corresponding spectral measure are
needed to enter the set. One sees different decay rates in "different directions", illustrating the
phenomenon of "hidden regular variation". We give several examples and obtain quite varied behavior,
including sets which do not have exact power-law decay.
M. Palö Forsström and J. Steif
A few surprising integrals,
Statistics and Probability Letters, 157, (2020), 108635.

Abstract. Using formulas for certain quantities involving stable vectors, due to I. Molchanov, and in
some cases utilizing the so-called divide and color model, we prove that certain families of integrals
which, ostensibly, depend on a parameter are in fact independent of this parameter.
M. Palö Forsström and J. Steif
Fortuin-Kasteleyn representations for threshold Gaussian and stable vectors ,
(This paper has been replaced by the four papers above. However, there is still some material in this
paper which is not contained in any of the above four papers.)

Abstract. We study the question of when a 0,1-valued threshold process associated to a mean zero
Gaussian or a symmetric stable vector corresponds to a "divide and color (DC) process". This means
that the process corresponding to fixing a threshold level h and letting a 1 correspond to the variable
being larger than h arises from a random partition of the index set followed by coloring all elements
in each partition element 1 or 0 with probabilities p and 1-p, independently for different partition
elements. For example, the Ising model with zero external field (as well as a number of other well
known processes) is a DC process where the random partition corresponds to the famous FK-random
cluster model.

We first determine in general the exact lack of uniqueness of the representing random partition. This
amounts to determining the dimensions of the kernels of a certain family of linear operators.

We obtain various results in both the Gaussian and symmetric stable cases. For example, it turns out that
all discrete Gaussian free fields yield a DC process when the threshold is zero; this follows quite easily
from known facts. For general n-dimensional mean zero, variance one Gaussian vectors with nonnegative
covariances, the zero-threshold process is always a DC process for n=3 but this is false for n=4.

The answers in general are quite different depending on whether the threshold level h is zero or not. We show
that there is no general monotonicity in h in either direction. We also show that all discrete Gaussian free fields
yield DC processes for large thresholds. Moving to n=3, we characterize exactly which mean zero, variance one
Gaussian vectors yield DC processes for large h.

In the stable case, among other results, if we stick to the simplest case of a permutation invariant, symmetric
stable vector with three variables, we obtain a phase transition in the stability exponent \alpha at the surprising
point 1/2; if the index of stability is larger than 1/2, then the process yields a DC process for large h while if
the index of stability is smaller than 1/2, then this is not the case.
Y. Peres, P. Sousi and J. Steif
Mixing time for random walk on supercritical dynamical percolation ,
Probability Theory and Related Fields, 176, (2020), 809-849.

Abstract. We consider dynamical percolation on the d-dimensional discrete torus of side length
n, Z_n^d, where each edge refreshes its status at rate \mu=\mu_n\le 1/2 to be open with
probability p. We study random walk on the torus, where the walker moves at rate 1/(2d)
along each open edge. In earlier work of two of the authors with A. Stauffer, it was shown that
in the subcritical case p < p_c(Z^d), the (annealed) mixing time of the walk is Theta(n^2/mu),
and it was conjectured that in the supercritical case p p_c(Z^d), the mixing time is Theta(n^2+1/mu);
here the implied constants depend only on d and p. We prove a quenched (and hence annealed) version of
this conjecture up to a poly-logarithmic factor under the assumption theta(p)>1/2. Our proof
is based on percolation results (e.g., the Grimmett-Marstrand Theorem) and an analysis of the
volume-biased evolving set process; the key point is that typically, the evolving set has a substantial
intersection with the giant percolation cluster at many times. This allows us to use precise
isoperimetric properties of the cluster (due to G. Pete) to infer rapid growth of the evolving set,
which in turn yields the upper bound on the mixing time.
Y. Peres, P. Sousi and J. Steif
Quenched exit times for random walk on dynamical percolation ,
Markov Processes and Related Fields, 24, (2018), 715-731.

Abstract. We consider random walk on dynamical percolation on the discrete torus Z_n^d. In previous
work, mixing times of this process for p < p_c(Z^d) were obtained in the annealed setting where one
averages over the dynamical percolation environment. Here we study exit times in the quenched setting,
where we condition on a typical dynamical percolation environment. We obtain an upper bound for all p
which for p < p_c matches the known lower bound.
J. Steif and J. Tykesson
Generalized Divide and Color models ,
ALEA. Latin American Journal of Probability and Mathematical Statistics, 16, (2019), 899-955.

Abstract. In this paper, we initiate the study of ``Generalized Divide and Color Models''. A very
special interesting case of this is the ``Divide and Color Model'' (which motivates the name we
use)b introduced and studied by Olle Häggström.

In this generalized model, one starts with a finite or countable set V, a random partition of V
and a parameter p in [0,1]. The corresponding generalized Divide and Color Model is the
{0,1}-valued process indexed by V obtained by independently, for each partition element in
the random partition chosen, with probability p, assigning all the elements of the partition element
the value 1, and with probability 1-p assigning all the elements of the partition element the value 0.

Some of the questions which we study here are the following. Under what situations can different
random partitions give rise to the same color process? What can one say concerning exchangeable
random partitions? What is the set of product measures that a color process stochastically dominates?
For random partitions which are translation invariant, what ergodic properties do the resulting color
processes have?

The motivation for studying these processes is twofold; on the one hand, we believe that this is a very
natural and interesting class of processes that deserves investigation and on the other hand, a number
of quite varied well-studied processes actually fall into this class such as (1) the Ising model, (2) the
fuzzy Potts model, (3) the stationary distributions for the Voter Model, (4) random walk in random
scenery and of course (5) the original Divide and Color Model.
J. Jonasson and J. Steif
Volatility of Boolean functions ,
Stochastic Processes and Their Applications, Volume 126, (2016), 2956-2975.

Abstract. We study the volatility of the output of a Boolean function when the input bits undergo
a natural dynamics. For n = 1,2,...., let f_n:{0,1}^{m_n} map to {0,1} be a Boolean function and
X^{(n)}(t)=(X_1(t),\ldots,X_{m_n}(t))_{t \in [0,infty)} be a vector of i.i.d. stationary continuous
time Markov chains on {0,1} that jump from 0 to 1 with rate p_n \in [0,1] and from 1 to 0 with rate
q_n=1-p_n. Our object of study will be C_n which is the number of state changes of f_n(X^{(n)}(t))
as a function of t during [0,1]. We say that the family {f_n}_{n\ge 1} is volatile if C_n tends to infinity
in distribution as n tends to infty and say that {f_n}_{n\ge 1} is tame if {C_n}_{n\ge 1} is tight. We
study these concepts in and of themselves as well as investigate their relationship with the recent
notions of noise sensitivity and noise stability. In addition, we study the question of lameness which
means that \Pro(C_n =0) tends to 1 as n\to\infty. Finally, we investigate these properties for the majority
function, iterated 3-majority, the AND/OR function on the binary tree and percolation on certain trees at
various levels of the parameter p_n.
T. Cox, Y. Peres and J. Steif
Cutoff for the noisy voter model ,
Annals of Applied Probability, Volume 26, (2016), 917-932.

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 by (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 ) and (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 |S |/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.
D. Ahlberg and J. Steif (with an appendix by Gabor Pete)
Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome? ,
Annales Institut Henri Poincare, Probabilites et Statistiques, 53, (2017), 2135-2161.

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.
A. E. Holroyd, Y. Peres and J. Steif
Wald for non-stopping times: The rewards of impatient prophets,
Electronic Communications in Probability, 19, (2014), no. 78, 9pp.

Let $X_1,X_2,\ldots$ be independent identically distributed nonnegative random variables. Wald's identity
states that the random sum $S_T:=X_1+\cdots+X_T$ has expectation $\E T \cdot \E X_1$ provided $T$
is a stopping time. We prove here that for any $1<\alpha\leq 2$, if $T$ is an arbitrary nonnegative random
variable, then $S_T$ has finite expectation provided that $X_1$ has finite $\alpha$-moment and $T$ has
finite $1/(\alpha-1)$-moment. We also prove a variant in which $T$ is assumed to have a finite exponential
moment. These moment conditions are sharp in the sense that for any i.i.d.\ sequence $X_i$ violating them,
there is a $T$ satisfying the given condition for which $S_T$ (and, in fact, $X_T$) has infinite expectation.
An interpretation of this is given in terms of a prophet being more rewarded than a gambler when a certain
impatience restriction is imposed.
Y. Peres, A. Stauffer and J. Steif
Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times,
Probability Theory and Related Fields, 162, (2015), 487-530.

We study the behavior of random walk on dynamical percolation. In this model, the edges of a graph G
are either open or closed and refresh their status at rate mu while at the same time a random walker moves
on G at rate 1 but only along edges which are open. On the d-dimensional torus with side length n, we
prove that in the subcritical regime, the mixing times for both the full system and the random walker are
n^2/mu up to constants. We also obtain results concerning mean squared displacement and hitting times.
Finally, we show that the usual recurrence transience dichotomy for the lattice Z^d holds for this model as well.
E. Lubetzky and J. Steif
Strong noise sensitivity and random graphs,
Annals of Probability, 43, (2015), 3239-3278.

The noise sensitivity of a Boolean function describes its likelihood to flip under small
perturbations of its input. Introduced in the seminal work of Benjamini, Kalai and
Schramm (1999), it was there shown to be governed by the first level of Fourier
coefficients in the central case of monotone functions at a constant critical probability.

Here we study noise sensitivity and a natural stronger version of it, addressing the effect
of noise given a specific witness in the original input. Our main context is the Erdos-Renyi
random graph, where already the property of containing a given graph is sufficiently rich
to separate these notions. In particular, our analysis implies (strong) noise sensitivity in
settings where the BKS criterion involving the first Fourier level does not apply, e.g., when
the critical value goes to 0 polynomially fast in the number of variables.
S. Blachere, F. den Hollander and J. Steif
A crossover for the bad configurations of random walk in random scenery,
Annals of Probability, 39, (2011), 2018-2041.

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 in [1/2,1] and epsilon in [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 in (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 in [0,1) the crossover value is
unique and equals 4/5. Finally, we suggest an approach to handle the seemingly more difficult
epsilon>0 and p in (1/2,4/5) case, which will be pursued in future work.
C. Garban and J. Steif
Noise sensitivity and percolation,
Probability and statistical physics in two and more dimensions, 49-154, Clay Math. Proc., 15,
Amer. Math. Soc., Providence, RI, 2012.

The present text provides the lecture notes for the course "noise sensitivity and percolation"
held for the 2010 Clay summer school.
J. Steif
A mini course on percolation theory,
Jyväskylä Lectures in Mathematics, 3, 2011.

These are lecture notes based on a mini course on percolation which was given at the Jyväskylä
summer school in mathematics in Jyväskylä, Finland, August 2009. The point of the course was
to try to touch on a number of different topics in percolation in order to give people some feel for
the field. These notes follow fairly closely the lectures given in the summer school. However, some
topics covered in these notes were not covered in the lectures (such as continuity of the percolation
function above the critical value) while other topics covered in detail in the lectures are not proved
in these notes (such as conformal invariance).
E. Broman, C. Garban and J. Steif
Exclusion Sensitivity of Boolean Functions,
Probability Theory and Related Fields, 155, (2013), 621-663.

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.
J. Steif
A survey on dynamical percolation ,
Fractal geometry and stochastics, IV, Birkhauser, 2009, 145-174.

Percolation is one of the simplest and nicest models in probability theory/statistical
mechanics which exhibits critical phenomena. Dynamical percolation is a model where
a simple time dynamics is added to the (ordinary) percolation model. This dynamical
model exhibits very interesting behavior. Our goal in this survey is to give an overview
of the work in dynamical percolation that has been done (and some of which is in the
process of being written up).
A. Bandyopadhyay, J. Steif and A. Timar
On the Cluster Size Distribution for Percolation on Some General Graphs,
Revista Matematica Iberoamericana, 26 (2010), 529-550.

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.
J. Steif and M. Warfheimer
The critical contact process in a randomly evolving environment dies out,
ALEA. Latin American Journal of Probability and Mathematical Statistics, 4 (2008), 337-357.

Bezuidenhout and Grimmett proved that the critical contact process dies out. Here, we
generalize the result to the so called contact process in a random evolving environment (CPREE),
introduced by Erik Broman. This process is a generalization of the contact process where the
recovery rate can vary between two values. The rate which it chooses is determined by a
background process, which evolves independently at different sites. As for the contact process,
we can similarly define a critical value in terms of survival for this process. In this paper we prove
that this definition is independent of how we start the background process, that finite and infinite
survival (meaning nontriviality of the upper invariant measure) are equivalent and finally that the
process dies out at criticality.
Y. Peres, O. Schramm and J. Steif
Dynamical sensitivity of the infinite cluster in critical percolation,
Annales Institut Henri Poincare, Probabilites et Statistiques, 45 (2009), 491-514

In dynamical percolation, the status of every bond is refreshed according to an independent
Poisson clock. For graphs which do not percolate at criticality, the dynamical sensitivity of
this property was analyzed extensively in the last decade. Here we focus on graphs which
percolate at criticality, and investigate the dynamical sensitivity of the infinite cluster. We
first give two examples of bounded degree graphs, one which percolates for all times at
criticality and one which has exceptional times of nonpercolation. We then make a nearly
complete analysis of this question for spherically symmetric trees with spherically symmetric
edge probabilities bounded away from 0 and 1. One interesting regime occurs when the
expected number of vertices at the nth level that connect to the root at a fixed time is of order
n(\log n)^\alpha. R. Lyons (1990) showed that at a fixed time, there is an infinite cluster a.s.
if and only if \alpha >1. We prove that the probability that there is an infinite cluster at all times
is 1 if \alpha > 2, while this probability is 0 if 1<\alpha \le 2. Within the regime where a.s. there
is an infinite cluster at all times, there is yet another type of ``phase transition'' in the behavior
of the process: if the expected number of vertices at the nth level connecting to the root at a fixed
time is of order n^\theta with \theta > 2, then the number of connected components of the set of
times in [0,1] at which the root does not percolate is finite a.s., while if 1<\theta < 2, then the
number of such components is infinite with positive probability.
J. Jonasson and J. Steif
Dynamical models for circle covering: Brownian motion and Poisson updating,
Annals of Probability, 36, (2008), 739-764.
(The published version is a slightly condensed version of what appears here.)

We consider two dynamical variants of the classical problem of random interval coverings
of the unit circle, the latter having been completely solved by L. Shepp. In the first model,
the centers of the intervals perform independent Brownian motions and in the second model,
the positions of the intervals are updated according to independent Poisson processes where
an interval of length $\ell$ is updated at rate $\ell^{-\alpha}$ where $\alpha$ is a parameter.
For the model with Brownian motions, a special case of our results is that if the length of the
$n$th interval is $c/n$, then there are times at which a fixed point is not covered if and only if
$c <2$ and there are times at which the circle is not fully covered if and only if $c <3$. For the
Poisson updating model, we obtain analogous results with $c <\alpha$ and $c <\alpha +1$ instead.
We also compute the Hausdorff dimension of the set of exceptional times for some of these questions.
J. Steif and A. Sudbury
Some results for poisoning in a catalytic model,
Electronic Communications in Probability, 11 (2006), 168-177.

We obtain new results concerning poisoning/nonpoisoning in a catalytic model which has
previously been introduced and studied. We show that poisoning can occur even when the
arrival rate of one gas is smaller than the sum of the arrival rates of the other gases, and that
poisoning does not occur when all gases have equal arrival rates.
T. Liggett, J. Steif and B. Toth
Statistical mechanical systems on complete graphs, infinite exchangeability, finite extensions
and a discrete finite moment problem,
Annals of Probability, 35, (2007), 867-914.

We show that a large collection of statistical mechanical systems with quadratically
represented Hamiltonians on the complete graph can be extended to infinite exchangeable
processes. This includes all ferromagnetic Ising, Potts and Heisenberg models. By
de Finetti's theorem, this is equivalent to showing that these probability measures can be
expressed as averages of product measures. We provide examples showing that
``ferromagnetism'' is not however in itself sufficient and also study in some detail the
Ising model with an additional 3-body interaction. Finally, we study the question of how
much the antiferromagnetic Ising model can be extended. In this direction, we obtain sharp
asymptotic results via a solution to a new moment problem. We also obtain a ``formula'' for
the extension which is valid in many cases.
O. Schramm and J. Steif
Quantitative noise sensitivity and exceptional times for percolation,
Annals of Mathematics, 171, (2010), 619-672.

One goal of this paper is to prove that dynamical critical site percolation on the planar
triangular lattice has exceptional times at which percolation occurs. In doing so, new
quantitative noise sensitivity results for percolation are obtained. The latter is based on a
novel method for controlling the ``level $k$'' Fourier coefficients via the construction of
a randomized algorithm which looks at random bits, outputs the value of a particular
function but looks at any fixed input bit with low probability. We also obtain upper and
lower bounds on the Hausdorff dimension of the set of percolating times. We then study
the problem of exceptional times for certain ``$k$-arm'' events on wedges and cones. As
a corollary of this analysis, we prove, among other things, that there are no times at which
there are two infinite ``white'' clusters, obtain an upper bound on the Hausdorff dimension
of the set of times at which there are both an infinite white cluster and an infinite black cluster
and prove that for dynamical critical bond percolation on the square grid there are no exceptional
times at which $3$ disjoint infinite clusters are present.
F. den Hollander and J. Steif
Random walk in random scenery: A survey of some recent results,
Dynamics and Stochastics: Festschrift in Honor of Michael Keane, IMS Lecture Notes-Monograph
Series, Vol. 48 (2006) 53-65.

In this paper we give a survey of some recent results for random walk in random
scenery (RWRS). On $\Z^d$, $d\geq 1$, we are given a random walk with i.i.d.
increments and a random scenery with i.i.d.\ components. The walk and the scenery
are assumed to be independent. RWRS is the random process where time is indexed
by $\Z$, and at each unit of time both the step taken by the walk and the scenery value
at the site that is visited are registered. We collect various results that classify the
ergodic behavior of RWRS in terms of the characteristics of the underlying random
walk (and discuss extensions to stationary walk increments and stationary scenery
components as well). We describe a number of results for scenery reconstruction and
close by listing some open questions.
E. I. Broman, O. Häggström and J. Steif
Refinements of stochastic domination,
Probability Theory and Related Fields, 136 (2006), 587-603.

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.
E. Mossel, R. O'Donnell, O. Regev, J. Steif and B. Sudakov
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse
Bonami-Beckner inequality,
Israel Journal of Mathematics, 154 (2006), 299-336.

In this paper we study non-interactive correlation distillation (NICD), a generalization of
noise sensitivity previously studied earlier. We extend the model to NICD on trees. In this
model there is a fixed undirected tree with players at some of the nodes. One node is given
a uniformly random string and this string is distributed throughout the network, with the
edges of the tree acting as independent binary symmetric channels. The goal of the players
is to agree on a shared random bit without communicating.

Our new contributions include the following:
(1). In the case of a $k$-leaf star graph (the model considered earlier by Mossel and O'Donnell),
we resolve the open question of whether the success probability must go to zero as $k \to \infty$.
We show that this is indeed the case and provide matching upper and lower bounds on the
asymptotically optimal rate (a slowly-decaying polynomial).
(2). In the case of the $k$-vertex path graph, we show that it is always optimal for all players to
use the same 1-bit function.
(3). In the general case we show that all players should use monotone functions. We also show,
somewhat surprisingly, that for certain trees it is better if not all players use the same function.

Our techniques include the use of the reverse Bonami-Beckner inequality. Although the usual
Bonami-Beckner has been frequently used before, its reverse counterpart seems very little-known;
To demonstrate its strength, we use it to prove a new isoperimetric inequality for the discrete
cube and a new result on the mixing of short random walks on the cube. Another tool that we need
is a tight bound on the probability that a Markov chain stays inside certain sets; we prove a new
theorem generalizing and strengthening previous such bounds. On the probabilistic side, we use
the ``reflection principle'' and the FKG and related inequalities in order to study the problem on
general trees.
T. Liggett and J. Steif
Stochastic Domination: The Contact Process, Ising Models and FKG Measures
Annales Institut Henri Poincare, Probabilites et Statistiques, 42 (2006), 223-243.

We prove for the contact process on $Z^d$, and many other graphs, that the upper invariant
measure dominates a homogeneous product measure with large density if the infection rate
$\lambda$ is sufficiently large. As a consequence, this measure percolates if the corresponding
product measure percolates. We raise the question of whether domination holds in the symmetric
case for all infinite graphs of bounded degree. We study some asymmetric examples which we
feel shed some light on this question. We next obtain necessary and sufficient conditions for
domination of a product measure for ``downward'' FKG measures. As a consequence of this
general result, we show that the plus and minus states for the Ising model on $Z^d$ dominate
the same set of product measures. We show that this latter fact fails completely on the homogenous
3-ary tree. We also provide a different distinction between $Z^d$ and the homogenous 3-ary tree
concerning stochastic domination and Ising models; while it is known that the plus states for
different temperatures on $Z^d$ are never stochastically ordered, on the homogenous 3-ary tree,
almost the complete opposite is the case. Next, we show that on $Z^d$, the set of product measures
which the plus state for the Ising model dominates is strictly increasing in the temperature. Finally,
we obtain a necessary and sufficient condition for a finite number of variables, which are both FKG
and exchangeable, to dominate a given product measure.
F. den Hollander, J. Steif, P. van der Wal
Bad Configurations for Random Walk in Random Scenery and Related Subshifts,
Stochastic processes and their applications, 115, (2005), 1209-1232.

In this paper we consider an arbitrary irreducible random walk on $\Z^d$, $d \geq 1$, with
i.i.d.\ increments, together with an arbitrary i.i.d.\ random scenery. Walk and scenery are
assumed to be independent. Random walk in random scenery (RWRS) is the random process
where time is indexed by $\Z$, and at each unit of time both the step taken by the walk and the
scenery value at the site that is visited are registered. Bad configurations for RWRS are the
discontinuity points of the conditional probability distribution for the configuration at the
origin of time given the configuration at all other times. We show that the set of bad
configurations is non-empty. We give a complete description of this set and compute its
probability under the random scenery measure. Depending on the type of random walk, this
probability may be zero or positive. For simple symmetric random walk we get three
different types of behavior depending on whether $d=1,2$, $d=3,4$ or $d \geq 5$. Our
classification is actually valid for a class of subshifts having a certain determinative property,
of which RWRS is an example. We also consider bad configurations w.r.t.\ a finite time
interval (replacing the origin) and obtain an almost complete generalization of our results.
Remarkably, this extension turns out to be somewhat delicate.
E. Broman and J. Steif
Dynamical Stability of Percolation for Some Interacting Particle Systems and $\epsilon$-Stability,
Annals of Probability, 34, (2006), 539-576.

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.
N. Gantert, M. Löwe and J. Steif
The voter model with anti-voter bonds,
Annales Institut Henri Poincare, Probabilites et Statistiques, 41, (2005), 767-780.

We study the voter model with both positive and negative bonds on a general locally finite
connected infinite graph. We obtain various results concerning ergodicity of the process.
F. den Hollander, M.S. Keane, J. Serafin and J. Steif
Weak Bernoullicity of Random Walk in Random Scenery,
Japanese Journal of Mathematics, 29, (2003), 389-406.

In this paper, we consider an arbitrary irreducible random walk and an arbitrary stationary
and ergodic random scenery on Z^d. We find conditions on their distributions such that the
associated random walk in random scenery is or is not weak Bernoulli. Our results extend
an earlier classification for the special case in which the individual scenery values are assumed
to be independent and identically distributed random variables.
M. Keane and J. Steif
Finitary coding for the 1-D T,T^{-1}-process with drift,
Annals of Probability, 31, (2003), 1979-1985.

We show that there is a finitary isomorphism from a finite state i.i.d. process to the T,T^{-1}-
process associated to 1-d random walk with positive drift. This contrasts with the situation for
simple symmetric random walk in any dimension, where it cannot be a finitary factor of any
i.i.d. process including in d > = 5 where it becomes weak Bernoulli.
R. Lyons and J. Steif
Stationary Determinantal Processes: Phase Multiplicity, Bernoullicity, Entropy, and Domination,
Duke Mathematical Journal, 120, (2003), 515-575.

We study a class of stationary processes indexed by Z^d that are defined via minors of
d-dimensional Toeplitz matrices. We obtain necessary and sufficient conditions for the
existence of a phase transition (phase multiplicity) analogous to that which occurs in
statistical mechanics. The absence of a phase transition is equivalent to the presence of a
strong K property, a particular strengthening of the usual K (Kolmogorov) property. We
show that all of these processes are Bernoulli shifts (isomorphic to i.i.d. processes in the
sense of ergodic theory). We obtain estimates of their entropies and we relate these processes
via stochastic domination to product measures.
I. Benjamini, O. Häggström, Y. Peres and J. Steif
Which properties of a random sequence are dynamically sensitive?,
Annals of Probability, 31, (2003), 1-34.

Consider a sequence of i.i.d. random variables, where each variable is refreshed (i.e., replaced
by an independent variable with the same law) independently, according to a Poisson clock.
At any fixed time t, the resulting sequence has the same law as at time 0, but there can be
exceptional random times at which certain almost sure properties of the time 0 sequence are
violated. We prove that there are no such exceptional times for the law of large numbers and
the law of the iterated logarithm, so these laws are dynamically stable. However, there are
times at which run lengths are exceptionally long, i.e., run tests are dynamically sensitive. We
obtain a multifractal analysis of exceptional times for run lengths and for prediction. In particular,
starting from an i.i.d. sequence of unbiased random bits, the random set of times t where
alpha log_2(n) bits among the first n bits can be predicted from their predecessors, has Hausdorff
dimension 1-alpha a.s. Finally, we consider simple random walk in the lattice Z^d, and prove that
transience is dynamically stable for d >= 5, and dynamically sensitive for d=3,4. Moreover, for
d=3,4, the nonempty random set of exceptional times t where the walk is recurrent, has
Hausdorff dimension (4-d)/2 a.s.
R. Meester and J. Steif
Higher-dimensional subshifts of finite type, factor maps and measures of maximal entropy,
Pacific Mathematical Journal, 200, (2001), 497-510.

We investigate factor maps of higher-dimensional subshifts of finite type. First we give higher-
dimensional versions of well known one-dimensional results, including a characterization of
entropy-preserving factor maps. Next, we investigate what happens to the number of measures
of maximal entropy under factor maps. We show that this number is preserved under almost
invertible maps, but not in general under finite to one factor maps.
J. Steif
The T,T^{-1}-process, finitary codings and weak Bernoulli ,
Israel Journal of Mathematics, 125, (2001), 29-43.

We give an elementary proof that the second coordinate (the scenery process) of the T,T^{-1}-process
associated to any mean zero i.i.d. random walk on Z^d is not a finitary factor of an i.i.d. process. In
particular, this yields an elementary proof that the basic T,T^{-1}-process is not finitarily isomorphic to
a Bernoulli shift (the stronger fact that it is not Bernoulli was proved by Kalikow). This also provides
(using past work of den Hollander and the author) an elementary example, namely the T,T^{-1}-process
in 5 dimensions, of a process which is weak Bernoulli by not a finitary factor of an i.i.d. process. An example
of such a process was given earlier by del Junco and Rahe. The above holds true for arbitrary stationary
recurrent random walks as well. On the other hand, if the random walk is Bernoulli and transient, the
T,T^{-1}-process associated to it is also Bernoulli. Finally, we show that finitary factors of i.i.d. processes
with finite expected coding volume satisfy certain notions of weak Bernoulli in higher dimensions which have
been previously introduced and studied in the literature. In particular, this yields (using past work of van
den Berg and the author) the fact that the Ising model is weak Bernoulli throughout the subcritical regime.
O. Häggström, R. Schonmann and J. Steif
The Ising Model on Diluted Graphs and Strong Amenability,
Annals of Probability, 28, (2000), 1111-1137.

Say that a graph has persistent transition if the Ising model on the graph can exhibit a phase transition
(nonuniqueness of Gibbs measures) in the presence of a nonzero external field. We show that for
nonamenable graphs, for Bernoulli percolation with p close to 1, all the infinite clusters have persistent
transition. On the other hand, we show that for transitive amenable graphs, the infinite clusters for any
stationary percolation do not have persistent transition. This extends a result of Georgii for the cubic
lattice. A geometric consequence of this latter fact is that the infinite clusters are strongly amenable
(i.e., their anchored Cheeger constant is 0). Finally we show that the critical temperature for the Ising
model with no external field on the infinite clusters of Bernoulli percolation with parameter p, on an
arbitrary bounded degree graph, is a continuous function of p.
O. Häggström and J. Steif
Propp-Wilson algorithms and finitary codings for high noise Markov random fields,
Combinatorics, Probability & Computing, 9, (2000), 425-439.

In this paper, we combine two previous works, the first being by the first author and K. Nelander, and the
second by J. van den Berg and the second author, to show (1) that one can carry out a Propp-Wilson exact
simulation for all Markov random fields on Z^d satisfying a certain high noise assumption, and (2) that all
such random fields are a finitary image of a finite state i.i.d. process. (2) is a strengthening of the previously
known fact that such random fields are Bernoulli shifts.
R. Pemantle and J. Steif
Robust Phase Transitions for Heisenberg and Other Models on General Trees,
Annals of Probability, 27, (1999), 876-912.

We study several statistical mechanical models on a general tree. Particular attention is devoted to the
spherical models, where the state space is the d-dimensional unit sphere and the interactions are
proportional to the cosines of the angles between neighboring spins. The phenomenon of interest here
is the classification of phase transition (non-uniqueness of the Gibbs state) according to whether it is
robust. In many cases, including all of the spherical and Potts models, occurrence of robust phase
transition is determined by the geometry (branching number) of the tree in a way that parallels the
situation with independent percolation and usual phase transition for the Ising model. The critical values
for robust phase transition for the spherical and Potts models are also calculated exactly. In some cases,
such as the q >= 3 Potts model, robust phase transition and usual phase transition do not coincide, while
in other cases, such as the spherical models, we conjecture that robust phase transition and usual phase
transition are equivalent. In addition, we show that symmetry breaking is equivalent to the existence of a
phase transition, a fact believed but not known for the rotor model on Z^2.
J. van den Berg and J. Steif
On the existence and non-existence of finitary codings for a class of random fields,
Annals of Probability, 27, (1999), 1501-1522.

We study the existence of finitary codings (also called finitary homomorphisms or finitary factor maps) from a
finite-valued i.i.d. process to certain random fields. For Markov random fields we show, using ideas of Marton
and Shields, that the presence of a phase transition is an obstruction for the existence of the above coding:
this yields a large class of Bernoulli shifts for which no such coding exists. Conversely, we show that for the
stationary distribution of a monotone exponentially ergodic probabilistic cellular automaton such a coding does
exist. The construction of the coding is partially inspired by the Propp-Wilson algorithm for exact simulation.

In particular, combining our results with a theorem of Martinelli and Olivieri, we obtain the fact that for the plus
state for the ferromagnetic Ising model on Z^d, d >= 2, there is such a coding when the interaction parameter
is below its critical value and there is no such coding when the interaction parameter is above its critical value.
J. Jonasson and J. Steif
Amenability and phase transition in the Ising model,
Journal of Theoretical Probability, 12, 1999, 549-559.

We consider the Ising model with external field h and coupling constant J on an infinite connected graph G with
uniformly bounded degree. We prove that if G is nonamenable, then the Ising model exhibits phase transition
for some h \neq 0 and some J<\infty. On the other hand, if G is amenable and quasi-transitive, then phase transition
cannot occur for h \neq 0. In particular, a group is nonamenable if and only if the Ising model on one (all) of its
Cayley graphs exhibits a phase transition for some h \neq 0 and some J<\infty.

Last modified: Thu Aug 22 11:14:12 MET DST 2013