, and

# Phase transitions and noise sensitivity
on the Poisson space
via stopping sets and decision trees

Günter<EMAIL_ADDRESS>[ Giovanni Peccatilabel=e2 [
<EMAIL_ADDRESS>D. Yogeshwaranlabel=e3 [
<EMAIL_ADDRESS>Institute for Stochastics, Karlsruhe Institute of
Technology, Karlsruhe.  Department of Mathematics (DMATH), Luxembourg
University, Luxembourg.  Theoretical Statistics and Mathematics Unit, Indian
Statistical Institute, Bangalore.

###### Abstract

Proofs of sharp phase transition and noise sensitivity in percolation have
been significantly simplified by the use of randomized algorithms, via the
OSSS inequality (proved by O’Donnell, Saks, Schramm and Servedio in [60]) and
the Schramm-Steif inequality for the Fourier-Walsh coefficients of functions
defined on the Boolean hypercube (see [70]). In this article, we prove
intrinsic versions of the OSSS and Schramm-Steif inequalities for functionals
of a general Poisson process, and apply these new estimates to deduce
sufficient conditions — expressed in terms of randomized stopping sets —
yielding sharp phase transitions, quantitative noise sensitivity, exceptional
times and bounds on critical windows for monotonic Boolean Poisson functions.
Our analysis is based on a new general definition of ‘stopping set’, not
requiring any topological property for the underlying measurable space, as
well as on the new concept of a ‘continuous-time decision tree’, for which we
establish several fundamental properties. We apply our findings to the
$k$-percolation of the Poisson Boolean model and to the Poisson-based confetti
percolation with bounded random grains. In these two models, we reduce the
proof of sharp phase transitions for percolation, and of noise sensitivity for
crossing events, to the construction of suitable randomized stopping sets and
the computation of one-arm probabilities at criticality. This enables us to
settle an open problem suggested by Ahlberg, Tassion and Texeira [4] (a
special case of which was conjectured earlier by Ahlberg, Broman, Griffiths
and Morris [2]) on noise sensitivity of crossing events for the planar Poisson
Boolean model with random balls whose radius distribution has finite
$(2+\alpha)$-moments and also show the same for planar confetti percolation
model with bounded random balls. We also prove that critical probability is
$1/2$ for the planar confetti percolation model with bounded, $\pi/2$-rotation
invariant and reflection invariant random grains. Such a result was
conjectured by Benjamini and Schramm [10] in the case of fixed balls and
proved by Müller [56], Hirsch [40] and Ghosh and Roy [31] in the case of
balls, boxes and random boxes, respectively; our results contain all previous
findings as special cases.

60D05,

82B43,

60G55,

60J25,

60H99,

68W20,

Poisson process,

functional inequalities,

stopping sets,

noise sensitivity,

dynamical percolation,

sharp phase-transition,

###### keywords:

[class=MSC2020]

###### keywords:

###### Contents

  1. 1 Introduction
    1. 1.1 Overview and motivation
    2. 1.2 A closer look at our main bounds
    3. 1.3 Overview of applications
    4. 1.4 Organization of the paper
    5. 1.5 Some preliminaries on Poisson processes
  2. I The OSSS Inequality for Poisson functionals
    1. 2 Continuous time decision trees
    2. 3 The OSSS inequality for Poisson functionals
    3. 4 Variants of the OSSS inequality
  3. II Quantitative Noise Sensitivity
    1. 5 Schramm-Steif inequalities on the Poisson space
    2. 6 Quantitative noise sensitivity
      1. 6.1 The Ornstein-Uhlenbeck semigroup
      2. 6.2 Noise sensitivity
      3. 6.3 Noise stability
    3. 7 Exceptional times and critical windows
  4. III Applications to Continuum percolation models
    1. 8 $k$-Percolation in the Poisson Boolean model
    2. 9 Confetti Percolation
    3. 10 Noise sensitivity for the planar Boolean model with unbounded balls
    4. 11 Further applications
    5. A Graph-measurable mappings and stopping sets
    6. B Non-attainable stopping sets

###  1 Introduction

####  1.1 Overview and motivation

Functional inequalities for mappings on the discrete hypercubes
$\\{0,1\\}^{n}$ and $\\{-1,1\\}^{n}$, $n\in\\{1,\ldots,\infty\\}$, (typically
endowed with some product measure) play a pivotal role in many applications,
ranging from the mathematical theory of voting and social choice, to
computational complexity and percolation on lattices; see e.g. [29, 58, 59,
76]. These estimates – examples of which are the discrete Poincaré and
logarithmic Sobolev inequalities (see e.g. [29, Theorem 1.13] and [76, Lemma
8.15]) and Talagrand’s $L^{1}$-$L^{2}$ bound [18, 73] – are analytic in nature
and can be canonically framed in the language of Markov semigroups, see e.g.
[18, 57].

More than a decade ago, two striking estimates — one for the variance of
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and the other for the Fourier-Walsh coefficients
of $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ — were proved by O’Donnell, Saks, Schramm
and Servedio [60, Theorem 3.1] and Schramm and Steif [70, Theorem 1.8],
respectively. The former inequality is known as the OSSS inequality and we
shall refer to the latter as the Schramm-Steif inequality. Both the OSSS and
Schramm-Steif estimates require the existence of a randomized algorithm
determining the function $f$ (although this assumption can be relaxed in the
Schramm-Steif case, see Section 1.2 below), in such a way that the upper
bounds are expressed in terms of revealment probabilities, i.e., of the
probability that a bit/coordinate of the input is revealed by the algorithm.
While the Schramm-Steif inequality was motivated by quantitative noise
sensitivity for discrete percolation models, the OSSS inequality was
established in the context of decision tree complexity. More recently,
references [23, 25, 24] have pioneered the use of the OSSS inequality to
derive simple proofs of sharp phase transitions in percolation.

The aim of this paper is to establish bounds analogous to the OSSS and
Schramm-Steif inequalities for random variables that depend on Poisson
processes defined on abstract measurable spaces, see Theorem 3.2, Theorem 5.1
and Corollary 5.3 below. As demonstrated by the applications discussed in the
forthcoming Section 1.3, our estimates are perfectly tailored for studying
phase transitions and noise sensitivity in models of continuum percolation
(see e.g. [15, 37, 51]), and will allow us to settle some open problems from
[2, 4, 10].

One new theoretical insight developed in our work is that, in the context of
functionals of random point measures, the role of randomized algorithms for
Boolean inputs is naturally played by randomized stopping sets and continuous-
time decision trees (CTDTs). Although the notion of ‘stopping set’ is
classical in stochastic geometry (see e.g. [9, 54, 65, 81, 82]), in the
sections to follow we choose to adopt a more general definition of such an
object, that will allow us to directly work with Borel spaces not necessarily
verifying specific topological requirements. To the best of our knowledge,
such a general theory of stopping sets (which is presented in a mostly self-
contained way in Appendix A and has a clear independent interest) is developed
here for the first time. The notion of CTDT is also new, and will be studied
from scratch in Section 2 and Appendix B.

It is important to observe that the proofs of Theorem 3.2 and Theorem 5.1
below do not rely on semigroup techniques or on discretization schemes, but
are rather based on the use of the Markov property of stopping sets – as
proved in Theorem A.6 – combined with the classical characterization of
Poisson processes as completely independent random measures. In particular,
for now it does not seem possible to deduce our main findings from classical
functional inequalities on the Poisson space, such as those proved in [1, 48,
49, 61, 57, 78]. More to the point, when compared with the tools available for
mappings on Boolean hypercubes, the relevance of our estimates is amplified by
the fact that $L^{1}$-$L^{2}$ inequalities on the Poisson space only hold
under very restrictive assumptions, see [57]. Also, even if $L^{1}$-$L^{2}$
inequalities on the Poisson space were available in full generality, it would
not be straightforward to deduce from them sharp phase-transitions (see the
discussion below (2.12) in [21]). Remarkably, our analysis will also show that
multiple Wiener-Itô integrals and associated chaotic decompositions (see [47,
49, 62]) play a role similar to Fourier-Walsh expansions (associated with
mappings on hypercubes) for establishing quantitative noise sensitivity in
various contexts, see Section 6. Our method of proof should eventually be
contrasted with the original proof of the discrete OSSS inequality given in
[60], which is rather based on martingale estimates reminiscent of the
arguments leading to the discrete Poincaré inequality.

####  1.2 A closer look at our main bounds

In order to motivate the reader, we now provide a more formal discussion of
some of the new estimates proved in this paper. We refer to Section 1.5 for a
rigorous definition of the objects appearing below.

Let $\eta$ be a Poisson process on a Borel space ${\mathbb{X}}$ (i.e.,
${\mathbb{X}}$ is a measurable space with a Borel-measurable bijection to a
Borel subset of $[0,1]$ with a measurable inverse), with a locally finite
intensity measure $\lambda$, and consider a random variable of the form
$f(\eta)$, where $f$ is some measurable mapping and
$\mathbb{E}[f(\eta)^{2}]<\infty$. In this case, the variance of $f(\eta)$ can
be bounded by using the classical Poincaré inequality stated in [49, Theorem
18.7], according to which

$\displaystyle\operatorname{{\mathbb{V}ar}}[f(\eta)]\leq\int\mathbb{E}[|D_{x}f(\eta)|^{2}]\,\lambda(dx),$
(1.1)

where, for $x\in{\mathbb{X}}$, the mapping $D_{x}f$ is the add-one cost
operator given by $D_{x}f(\eta):=f(\eta+\delta_{x})-f(\eta)$, with
$\delta_{x}$ the Dirac mass at $x$, and $\operatorname{{\mathbb{V}ar}}$
indicates the variance. The estimate (1.1) is an infinite-dimensional
counterpart to the well-known Efron-Stein inequality (see e.g. [17, Chapter
3]), stating that, if $F(X)$ is a square-integrable functional of a finite
vector of independent random variables $X=(X_{1},...,X_{n})$, then

$\operatorname{{\mathbb{V}ar}}(F(X))\leq\frac{1}{2}\sum_{i=1}^{n}\mathbb{E}[(F(X)-F(X^{i}))^{2}],$
(1.2)

where $X^{i}$ is the vector obtained from $X$ by re-randomizing the $i$th
coordinate $X_{i}$. Note that, if $f,F$ in the above discussion take values in
$\\{-1,1\\}$, then
$\operatorname{{\mathbb{V}ar}}(f(\eta))=\mathbb{E}[|f(\eta)-f(\eta^{\prime})]]$
and $\operatorname{{\mathbb{V}ar}}(F(X))=\mathbb{E}[|F(X)-F(X^{\prime})|]$,
where $\eta^{\prime}$ and $X^{\prime}$ are independent copies of $\eta$ and
$X$, respectively, and also
$\mathbb{E}[|D_{x}f(\eta)|^{2}]=4\mathbb{P}(f(\eta)\neq f(\eta+\delta_{x}))$
and $\mathbb{E}[(F(X)-F(X^{i}))^{2}]=4\mathbb{P}(F(X)\neq F(X^{i}))$. It is
easily checked that, if $X$ takes vaules in $\\{-1,1\\}^{n}$, then the latter
probability coincides (up to a factor) with the usual notion of influence of
the $i$th coordinate on $F$, as defined e.g. in [29, Section 1.3] (see also
Remark 1.1 below). Albeit fundamentally useful in many situations (see again
[17, Chapter 3], as well as [38] for a representative geometric application),
the estimates (1.1)–(1.2) are in general suboptimal, and not sufficiently
tight for several applications. See [57] (and Example 1 below) for several
illustrations of this point.

Now consider a stopping set $Z(\eta)$. This notion, which is formally defined
in Appendix A, indicates that $Z(\eta)$ is a random subset of ${\mathbb{X}}$,
satisfying some adequate measurability conditions and such that $Z(\eta)$ only
depends on the restricition $\eta_{Z}$ of $\eta$ to $Z(\eta)$. We say that a
mapping $f(\cdot)$ is determined by $Z(\eta)$ if $f(\eta)$ only depends on
$\eta_{Z}$. In Theorem 3.2 and Corollary 5.3 below, we will prove the
following two estimates (1.3) and (1.5), allowing one to control the
fluctuations of a random variable $f(\eta)$ such that $f$ is determined by
$Z$.

  1. (a)

Assume that the measure $\lambda$ is diffuse and that the stopping set
$Z(\eta)$ is the output of a sufficiently regular continuous-time decision
tree (CTDT), that is, of a sequence of increasing stopping sets
$\\{Z_{t}(\eta):t\geq 0\\}$ such that $Z_{t}(\eta)\uparrow Z(\eta)$ (see
Section 2). Then, if the random variable $f(\eta)$ is integrable and $f$ is
determined by $Z(\eta)$,

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]\leq 2\int\mathbb{P}(x\in
Z)\mathbb{E}[|D_{x}f(\eta)|]\,\lambda(dx).$ (1.3)

Relation (1.3) is an infinite-dimensional counterpart to [60, Theorem 3.1],
implying the following bound: if $F(X)$ is an integrable functional of a
vector of independent random variables and $F$ is determined by a randomized
algorithm $T$, then

$\mathbb{E}[|F(X)-F(X^{\prime})|]\leq\sum_{i=1}^{n}\mathbb{P}(i\mbox{ is
revealed by}\,\,T)\,\mathbb{E}[|F(X)-F(X^{i})]],$ (1.4)

where we have used the previously introduced notation, and the event inside
the probability corresponds to the event that the coordinate $i$ is visited by
$T$. In the applications developed in Sections 8 and 9 we will show that (1.3)
and its generalizations can be used to prove sharp thresholds in continuum
percolation models. In Appendix B, we will also show that not every stopping
set $Z(\eta)$ can be represented as the output of a regular CTDT; as discussed
below, the extension of (1.3) to general stopping sets is an open problem.

  2. (b)

Consider a stopping set $Z(\eta)$ (not necessarily generated by a CTDT), and
assume that $f(\eta)$ is square-integrable and $f$ is determined by $Z(\eta)$.
Then, if $u_{k}(\eta)$ denotes the $k$th summand in the Wiener-Itô chaotic
decomposition of $f(\eta)$ ($k=1,2,...$) (see (1.10) for definition),

$\displaystyle\mathbb{E}[u_{k}(\eta)^{2}]\leq
k\left[\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in
Z(\eta))\right]\times\operatorname{{\mathbb{V}ar}}(f(\eta)).$ (1.5)

The bound (1.5) is a counterpart to [60, Theorem A.1] (of which [70, Theorem
1.8] is a special case), yielding the following: if $F(X)$ is a a square-
integrable functional of a vector of independent random variables and $F$ is
determined by a discrete stopping set $S$, then, denoting by $F_{k}$ the $k$th
component in the Hoeffding-ANOVA decomposition of $F$ ($k=1,...,n$) (see e.g.
[71, Chapter 5]),

$\operatorname{{\mathbb{V}ar}}(F_{k}(X))\leq
k\left[\max_{i=1,...,n}\mathbb{P}(i\in
S)\right]\times\operatorname{{\mathbb{V}ar}}(F(X)).$ (1.6)

Observe that, if the random set $S$ is the collection of all coordinates of
$X$ revealed by a randomized algorithm, then $\mathbb{P}(i\in
S)=\mathbb{P}(i\mbox{ is revealed})$, but such an additional feature is not
required for (1.6) to hold. In Sections 8, Section 9 and Section 10, we will
show that (1.5) and its extensions are useful for establishing noise
sensitivity in continuum percolation. The crucial technical step for deriving
the original Schramm-Steif inequality (1.6) is a bound on the conditional
expectations of degenerate $U$-statistics (see [60, formula (12)]). In order
to prove (1.5), we will derive an analogous bound for multiple Wiener-Itô
integrals (Theorem 5.1) which is of independent interest.

######  Remark 1.1.

Let $F:\\{-1,1\\}^{n}\to\\{-1,1\\}$, and let $X=(X_{1},...,X_{n})$ be a
collection of i.i.d. Rademacher random variables with parameter $p$. One
remarkable consequence of [60] (see Corollary 1.2 therein) is the general
bound

${\bf Inf}_{max}(F)\geq\frac{\operatorname{{\mathbb{V}ar}}{F(X)}}{\Delta(T)},$
(1.7)

where

${\bf Inf}_{max}(F):=\max_{i=1,...,n}{\bf
Inf}_{i}(F):=4p(1-p)\max_{i=1,...,n}\mathbb{P}[F(X)\neq F(X^{(i)})],$

$X^{(i)}$ is the element of $\\{-1,1\\}^{n}$ obtained by switching the sign of
the $i$th coordinate of $X$, and $\Delta(T)$ is the average number of
coordinates visited by $T$. As mentioned above, the quantity ${\bf
Inf}_{i}(F)$ is defined as the influence of the $i$th coordinate on $F$. One
can derive an estimate with the same flavour starting from (1.3). Consider
indeed $f(\eta)$ with values in $\\{-1,1\\}$ and determined by the output $Z$
of a CTDT, and set

${\bf Inf}_{max}(f):=2\sup_{x\in{\mathbb{X}}}\,\mathbb{P}(f(\eta)\neq
f(\eta+\delta_{x})).$

Then, one infers from (1.3) that

$2{\bf
Inf}_{max}(f)\geq\frac{\operatorname{{\mathbb{V}ar}}(f(\eta))}{\mathbb{E}[\lambda(Z)]},$
(1.8)

where we have applied a Fubini argument. The full analogy with (1.7) is
obtained from (A.11), yielding the identity
$\mathbb{E}[\lambda(Z)]=\mathbb{E}[\eta(Z)]$, that is, the denominator on the
right-hand side of (1.8) coincides with the average number of Poisson points
that are revealed by the stopping set $Z$.

We will now provide an outline of the applications developed in Sections 8, 9
and 10.

####  1.3 Overview of applications

In Sections 8, 9 and 10, we will develop three applications of our abstract
results to continuum percolations models, namely, to $k$-percolation in the
Poisson Boolean model (see e.g. [13] and the references therein), to confetti
percolation (see [37, 51, 15, 10, 4]) and to the planar Poisson Boolean model
with unbounded grains (see [4]). These are by no means exhaustive, and more
potential applications are described in Section 11.

General considerations. We first observe that the finite-dimensional nature of
the original OSSS and Schramm-Steif inequalities has not been — in general — a
major obstacle for applying them to random geometric models based on infinite-
dimensional inputs. Indeed, using suitable discretization schemes and some
extra technical work, these estimates have been successfully applied to
geometric models based on stationary Euclidean Poisson point processes, see
[2, 3, 25, 24, 26, 31, 46]. This fact notwithstanding, the applications
developed in the present paper indicate that the our intrinsic approach is a
new valuable tool for establishing quantitative noise sensitivity, existence
of exceptional times and sharp phase transition in (possibly dynamical)
continuum percolation models, under minimal assumptions and by using
strategies of proofs that only require one to prove non-degenaracy of some
class of functionals and decay on arm probabilities. Another important point
is that our estimates allow one to prove quantitative noise sensitivity in
percolation models for which discretization techniques would be difficult to
apply. One typical example of this situation is the confetti percolation
discussed in Section 9, whose dynamical nature makes discretization procedures
particularly challenging to implement (see e.g. [31]), and a similar remark
also applies for the Poisson Boolean model with unbounded grains as in Section
10. In general, while the discretization approach has been widely applied to
the detection of sharp thresholds, it has been exploited less intensively in
the proof of noise sensitivity (see [3] for some distinguished examples). We
believe that the our intrinsic approach will also be helpful when dealing with
more general Poissonian percolation models such as those suggested in Section
11 as well as in the study of Poisson-Voronoi tesselations on the hyperbolic
plane [11] or the Poisson cylinder model [75].

Description of the models. The $k$-percolation model arises by placing i.i.d.
bounded grains (shapes) at each point in the support of a stationary Poisson
point process on ${\mathbb{R}}^{d},\,d\geq 2$ with intensity $\gamma$. The
$k$-covered region is the region covered by at least $k$ of these grains and
$k$-percolation refers to existence of an unbounded connected component in the
$k$-covered region. If $k=1$, we obtain the standard Poisson Boolean model.
The confetti percolation model is defined in terms of a space-time Poisson
point process. The Poisson points are independently coloured either in black
or white, with probability $p$ and $1-p$, respectively. The black and white
points carry i.i.d. bounded grains as well and can have different
distributions. A spatial location $x\in{\mathbb{R}}^{d}$ is covered in black
or white depending on the colour of the first grain that falls on $x$. The
black region is the region of black points and confetti percolation refers to
existence of an infinite component in the black region. Apart from
boundedness, we require that the grains are not too thin i.e., contain some
ball with positive probability. We give more details on these two models as
well as some more background literature in the corresponding sections. The
varying parameters in the $k$-percolation model is $\gamma$, whereas it is $p$
in the confetti percolation model.

Overview of results: phase transitions. In both models, we first prove a sharp
phase transition in arbitrary dimensions (Theorems 8.2 and 9.1). This involves
showing exponential decay for the radius of the component containing the
origin in the sub-critical regime and the mean-field lower bound for the
radius in the super-critical regime. The proof uses the Poisson OSSS variance
inequality (1.3) and the necessary CTDTs are constructed via a technical
adaptation of the ideas of Duminil-Copin, Raoufi and Tassion [23] to the
continuum setting.

We now describe some consequences of the sharp phase transition result derived
above. In the $k$-percolation model, we show equality of the usual critical
intensity and of the critical intensities defined in terms of the expected
volume of the component containing the origin and of the non-triviality of
certain crossing probabilities introduced by Gouéré in [34] (see Theorem 8.1).
In the confetti percolation model, we prove that the critical parameter is
$1/2$ in a very general planar confetti percolation model in the general
setting of bounded grains satisfying $\pi/2$-rotation invariance and
invariance under reflection by coordinates (see Theorem 9.3). This result was
conjectured by Benjamini and Schramm [10, Problem 5] for the case of
deterministic balls. It was first proven in the case of deteministic boxes by
Hirsch [40] and later by Müller [56] in the case of deterministic balls and
then by Ghosh and Roy [31] in the case of bounded random boxes.

Overview of results: noise sensitivity. The Schramm-Steif inequality (1.6)
arose in the study of noise sensitivity for lattice percolation models.
Informally noise sensitivity of a sequence of functions $f_{n}$, refers to the
phenomenon that under a small perturbation of the random input, the functions
become asymptotically independent or de-correlated. Apart from the natural
motivation coming from the study of random structures under perturbations,
there are varied reasons to study noise sensitivity coming from statistical
physics and computer science (see [28, Section 1.2], [29, Chapter 12]). By
considering the perturbation as induced by a Markov process, one may naturally
relate noise sensitivity to the study of functions of a dynamically evolving
random input. In percolation theory, these are known as dynamical percolation
models (see [36, 72]) where one studies percolation models such that the
random input is varied dynamically. In the case of Poisson-based models, we
consider the dynamics induced by the spatial birth-death process i.e., the
existing points are deleted after exponential lifetimes and new points are
born independently and stay for exponential lifetimes. The corresponding
perturbation is to delete a small fraction of existing points and compensate
it by adding a small fraction of new points independently. From the Poisson
Schramm-Steif inequality (1.5) and Wiener-Itô chaos decomposition (1.10), we
can obtain easily that a sequence of $\\{0,1\\}$-valued functions $f_{n}$ is
noise sensitive if there exists a corresponding sequence of randomized
stopping sets $Z_{n}$ determining $f_{n}$ such that the supremum of the
revealement probabilities $\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in Z_{n})$
vanishes asymptotically. Quantitative noise sensitivity can be used to prove
existence of exceptional times in dynamical models as well as to give bounds
on the critical window for phase transitions.

In the two continuum percolation models ($k$-percolation in the Poisson
Boolean model and confetti percolation), we take $f_{n}$ to be the indicator
functions that there is a crossing of large boxes (say $[0,\kappa
n]\times[0,n]^{d-1}$ for $\kappa>0$) along the $x$-axis by occupied components
at criticality. We prove that noise sensitivity and exceptional times in
dynamical percolation for the above crossing events follow from the non-
degeneracy of the crossing probabilities and decay of one-arm probabilities
(Theorems 8.3 and 9.5). This helps us to settle a conjecture by Ahlberg,
Broman, Griffiths and Morris [2, Conjecture 9.1] regarding noise sensitivity
of the critical planar Poisson Boolean model with bounded random balls
straightforwardly using the recent one-arm probability estimates in Ahlberg,
Tassion and Texeira [4] and also yields easily noise sensitivity of the
critical planar confetti percolation model where grains are balls with bounded
random radii (see Corollary 8.5 and 9.7). Further, we also prove quantiative
noise sensitivity of the planar Poisson Boolean model with random balls whose
radius distribution satisfies a finite $(2+\alpha)$-moment condition (Theorem
10.1). This answers an open question in Ahlberg, Tassion and Texeira [4]. (As
indicated in [2], a version of this result can in principle be obtained by
combining the BKS randomized algorithm method from [12] with the estimates of
[4] – but it is not clear that our near-optimal moment condition on the random
radii is preserved by this alternative strategy). Less quantitatively, we also
prove noise sensitivity of the critical planar confetti percolation with black
and white particles both having the same $\pi/2$-rotation invariant and
reflection invariant bounded grain distribution (Corollary 9.8).

####  1.4 Organization of the paper

The paper is composed of three parts. Part I contains basic notions about
CTDTs (Section 2), the statement and proof of the OSSS inequality for Poisson
functionals (Section 3), and several useful variants (Section 4). Part II
focusses on the Schramm-Steif inequality (Section 5), its consequences for
quantiative noise sensitivity and noise stability (Section 6) and their
applications to exceptional times and sharp phase transition (Section 7). Part
III presents applications to $k$-percolation (Section 8), confetti percolation
(Section 9), noise sensitivity for the planar Boolean model with unbounded
balls (Section 10) and a discussion of further applications (Section 11).
Appendix A contains a general theory of stopping sets, that is used throughout
the paper, under minimal topological assumptions. Appendix B is devoted to
zero-one laws for CTDTs and non-attainable stopping sets.

The next Subsection 1.5 contains some basic definitions and facts about
Poisson processes. The reader is referred to the monographs [45, 49] for a
comprehensive discussion; see also [47].

####  1.5 Some preliminaries on Poisson processes

Throughout the paper, we let $({\mathbb{X}},{\mathcal{X}})$ denote a Borel
space. We fix an increasing sequence $\\{B_{n}:n\geq 1\\}$ of sets in
$\mathcal{X}$ satisfying $B_{n}\uparrow{\mathbb{X}}$ and define
${\mathcal{X}}_{0}\subset{\mathcal{X}}$ as the system of all sets of the form
$B\cap B_{n}$ for some $B\in{\mathcal{X}}$ and $n\in{\mathbb{N}}$. (This is an
example of localizing ring as defined in [45].) Note that
$\sigma(\mathcal{X}_{0})={\mathcal{X}}$. A measure $\nu$ on
$({\mathbb{X}},{\mathcal{X}})$ which is finite on ${\mathcal{X}}_{0}$ is
called locally finite (note that the property of being locally finite depends
on the choice of the sequence $\\{B_{n}:n\geq 1\\}$).

Write ${\mathbb{N}}_{0}:=\\{0,1,2,...\\}$ and let
${\mathbf{N}}\equiv{\mathbf{N}}({\mathbb{X}})$ be the space of all measures on
${\mathbb{X}}$ which are ${\mathbb{N}}_{0}$-valued on ${\mathcal{X}}_{0}$ and
let ${\mathcal{N}}$ denote the smallest $\sigma$-field such that
$\mu\mapsto\mu(B)$ is measurable for all $B\in{\mathcal{X}}$. A point process
is a random element $\eta$ of ${\mathbf{N}}$, defined over some fixed
probability space $(\Omega,{\mathcal{F}},\mathbb{P})$. The intensity measure
of $\eta$ is the measure $\mathbb{E}[\eta]$ defined by
$\mathbb{E}[\eta](B):=\mathbb{E}[\eta(B)]$, $B\in{\mathcal{X}}$. By our
assumption on ${\mathbb{X}}$ every point process $\eta$ is proper, that is
$\eta=\sum_{n=1}^{\eta(\mathbb{X})}\delta_{Y_{n}}$, where $\delta_{y}$ is the
Dirac mass at $y$, and $\\{Y_{n}:n\geq 1\\}$ is a collection of random
elements with values in $\mathbb{X}$; see [49, Section 6.1] for more details.
Given a measure $\nu$ on ${\mathbb{X}}$ and $B\in\mathcal{X}$, we write
$\nu_{B}$ to indicate the trace measure $A\mapsto\nu(A\cap B)$. For
$\mu\in{\mathbf{N}}$ and $A\in{\mathcal{X}}$, we write $\mu\subset A$ if
$\mu(A^{c})=0$.

Fix a locally finite measure $\lambda$ on ${\mathbb{X}}$. By construction of
${\mathcal{X}}_{0}$, $\lambda$ is automatically $\sigma$-finite. (Sometimes it
is convenient to start with a $\sigma$-finite measure $\lambda$ and to choose
the $B_{n}$ such that $\lambda(B_{n})<\infty$.) A Poisson process with
intensity measure $\lambda$ is a point process $\eta$ enjoying the following
two properties: (i) for every $B\in\mathcal{X}$, the random variable $\eta(B)$
has a Poisson distribution with parameter $\lambda(B)$, and (ii) given
$m\in{\mathbb{N}}$ and disjoint sets $B_{1},...,B_{m}\in\mathcal{X}$, the
random variables $\eta(B_{1}),...,\eta(B_{m})$ are stochastically independent.
Property (ii) is often described as $\eta$ being completely independent or,
equivalently, independently scattered.

It is a well-known fact (see e.g. [49, Chapter 2]) that, if $\lambda$ is non-
atomic, then $\mathbb{P}$-a.s. every point in the support of $\eta$ is charged
with mass 1. In other words this means that
$\mathbb{P}(\eta\in{\mathbf{N}}_{s})=1$, where ${\mathbf{N}}_{s}$ is the set
of all $\mu\in{\mathbf{N}}$ with $\mu(\\{x\\})\leq 1$ for each
$x\in{\mathbb{X}}$. Given $\mu\in{\mathbf{N}}$ and $n\geq 1$, we denote by
$\mu^{(n)}$ the $n$th factorial measure associated with $\mu$, as defined in
[49, Chapter 4]. If $\mu\in{\mathbf{N}}_{s}$ then $\mu^{(n)}$ is the measure
on $({\mathbb{X}}^{n},\mathcal{X}^{n})$ obtained by removing from the support
of $\mu^{n}$ every point $(x_{1},...,x_{n})$ such that $x_{i}=x_{j}$ for some
$i\neq j$ (with $\mu^{(1)}=\mu$). We will often make use of the following
(multivariate) Mecke formula (see [49, Theorem 4.4]). If $\eta$ is a Poisson
process with intensity $\lambda$ then, for all $n\geq 1$ and all measurable
mappings $f\colon{\mathbb{X}}^{n}\times{\mathbf{N}}\to[0,\infty)$,

$\displaystyle\mathbb{E}$
$\displaystyle\left[\int_{{\mathbb{X}}^{n}}f(x_{1},...,x_{n},\eta)\,\eta^{(n)}(dx_{1},...,dx_{n})\right]$
(1.9)
$\displaystyle\qquad\qquad=\mathbb{E}\left[\int_{{\mathbb{X}}^{n}}f(x_{1},...,x_{n},\eta+\delta_{x_{1}}+\cdots+\delta_{x_{n}})\,\lambda^{n}(dx_{1},...,dx_{n})\right],$

where $\mathbb{E}$ denotes expectation with respect to $\mathbb{P}$. A further
crucial fact is that every measurable function
$f\colon{\mathbf{N}}\to{\mathbb{R}}$ such that
$\mathbb{E}[f(\eta)^{2}]<\infty$ admits a unique chaotic decomposition of the
form

$f(\eta)=\sum_{k=0}^{\infty}I_{k}(u_{k}),$ (1.10)

where $I_{0}(u_{0})=u_{0}:=\mathbb{E}[f(\eta)]$, $I_{k}$ indicates a multiple
Wiener-Itô integral of order $k$ with respect to the compensated measure
$\hat{\eta}:=\eta-\lambda$, the kernels $u_{k}\in L^{2}(\lambda^{k})$ ($k\geq
1$) are $\lambda^{k}$-a.e. symmetric, and the series converges in
$L^{2}(\mathbb{P})$. Multiple Wiener-Itô integrals are the exact equivalent of
homogeneous sums in the framework of random variables depending on an
independent Rademacher sequence (or, more generally, of Hoeffding-ANOVA
decompositions for functions of independent random vectors). We refer the
reader to [49, Chapters 12 and 18] and [62, Chapter 5] for more details. For
future use, we record here the classical orthonormality relation, valid for
all $k,m\geq 0$ and all pairs of a.e. symmetric kernels $u\in
L^{2}(\lambda^{k})$, $v\in L^{2}(\lambda^{m})$ (with the obvious
identification $L^{2}(\lambda^{0})={\mathbb{R}}$):

$\mathbb{E}[I_{k}(u)I_{m}(v)]={\mathbf{1}}\\{k=m\\}\,k!\,\langle
u,v\rangle_{L^{2}(\lambda^{k})}.$ (1.11)

Recall from [49, (18.20)] that, if $f:{\mathbf{N}}\to{\mathbb{R}}$ is as in
(1.10), then

$u_{k}(x_{1},\ldots,x_{k}):=\frac{1}{k!}\mathbb{E}[D^{k}_{x_{1},\ldots,x_{k}}f(\eta)],$
(1.12)

where $D^{k}$ is the iterated difference operator defined as
$D^{k}_{x_{1},\ldots,x_{k}}f(\eta):=D_{x_{1}}(D^{k-1}_{x_{2},\ldots,x_{k}}f(\eta))$
with $D_{x}$ being the add-one cost operator defined below (1.1). Applying
(1.10), (1.11) and (1.12), yields the relation

$\mathbb{E}[f(\eta)^{2}]=\sum_{k=0}^{\infty}k!\|u_{k}\|^{2}_{L^{2}(\lambda^{k})}=\mathbb{E}[f(\eta)]^{2}+\sum_{k=1}^{\infty}\int_{{\mathbb{X}}^{k}}\frac{1}{k!}\mathbb{E}[D^{k}_{x_{1},\ldots,x_{k}}f(\eta)]^{2}\lambda(\mathrm{d}x_{1})\ldots\lambda(\mathrm{d}x_{k}).$
(1.13)

Formula (1.13) will be used in Section 5.

##  Part I The OSSS Inequality for Poisson functionals

Throughout this part, we work in the general setting of Section 1.5. We fix a
Poisson process $\eta$ with a locally finite intensity measure $\lambda$.

###  2 Continuous time decision trees

The following key definition relies on the concept of a stopping set,
discussed in Appendix A.

A family $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ of stopping sets is called a
continuous-time decision tree (CTDT) if $Z_{t}\in{\mathcal{X}}_{0}$ for
$t\in{\mathbb{R}}_{+}$, $\mathbb{E}[\lambda(Z_{0})]=0$ and if the following
properties are satisfied:

$\displaystyle Z_{s}$ $\displaystyle\subset Z_{t},\quad s\leq t,$ (2.1)
$\displaystyle Z_{t}$ $\displaystyle=\bigcap_{s>t}Z_{s},\quad
t\in{\mathbb{R}}_{+}.$ (2.2)

If $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT, we then define

$\displaystyle Z_{\infty}$
$\displaystyle:=\bigcup_{t\in{\mathbb{R}}_{+}}Z_{t},$ (2.3) $\displaystyle
Z_{t-}$ $\displaystyle:=\bigcup_{s<t}Z_{s},\quad t\in{\mathbb{R}}_{+},$ (2.4)

as well as $Z_{0-}:=\emptyset$. As monotone unions of stopping sets,
$Z_{\infty}$ and $Z_{t-}$ are also stopping sets; see Theorem A.6. Note that
${\mathbb{Z}}_{\infty}$ is not required to be $\mathcal{X}_{0}$-valued. The
aim of this section is to prove some technical results for CTDTs, laying the
ground for the main OSSS-type estimate stated in Theorem 3.2.

Given a CTDT $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ we define

$\displaystyle t(x,\mu):=\inf\\{t\in{\mathbb{R}}_{+}:x\in Z_{t}(\mu)\\},\quad
x\in{\mathbb{X}},\,\mu\in{\mathbf{N}},$ (2.5)

where $\inf\emptyset:=\infty$. Observe that, by (2.1) and (2.2) we have

$\displaystyle x\in Z_{t(x,\mu)}(\mu)\setminus
Z_{t(x,\mu)-}(\mu),\quad\text{if $t(x,\mu)<\infty$}.$ (2.6)

Furthermore we can replace ${\mathbb{R}}_{+}$ on the right-hand side of (2.5)
by the non-negative rational numbers. Hence we obtain from Proposition A.9
that

$\displaystyle
t(x,\eta)=t(x,\eta+\delta_{x}),\quad\mathbb{P}\text{-a.s.},\,\lambda\text{-a.e.\
$x$}.$ (2.7)

The following result is crucial.

######  Proposition 2.1.

Suppose that $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT and let $\eta$ and
$\eta^{\prime}$ be two independent Poisson processes with the same intensity
measure $\lambda$. Let
$g\colon[0,\infty]\times{\mathbf{N}}\to{\mathbb{R}}_{+}$ be measurable and
$x\in{\mathbb{X}}$. Then

$\displaystyle\mathbb{E}[g(t(x,\eta),\eta_{{\mathbb{X}}\setminus
Z_{t(x,\eta)}(\eta)}+\eta^{\prime}_{Z_{t(x,\eta)}(\eta)})]=\mathbb{E}[g(t(x,\eta),\eta^{\prime})].$

The proof of Proposition 2.1 requires the following (purely deterministic)
lemma.

######  Lemma 2.2.

Suppose that $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT. Then, $\mu\mapsto
Z_{x}(\mu):=Z_{t(x,\mu)}(\mu)$ is a stopping set for each $x\in{\mathbb{X}}$.
Moreover, for each $x\in{\mathbb{X}}$ there exist ${\mathcal{X}}_{0}$-valued
stopping sets $Z_{n}^{\prime}$, $n\in{\mathbb{N}}$, such that
$Z_{n}^{\prime}\uparrow Z_{x}$.

###### Proof.

We first need to settle measurability. It follows from the right-continuity
(2.2) and the graph-measurability of $Z_{t}$ that
$(y,t,\mu)\mapsto{\mathbf{1}}\\{y\in Z_{t}(\mu)\\}$ is measurable. Moreover,
for each $s\in{\mathbb{R}}_{+}$ and all
$(x,\mu)\in{\mathbb{X}}\times{\mathbf{N}}$ we have that $t(x,\mu)\leq s$ if
and only if $x\in Z_{s}(\mu)$. Therefore $(x,\mu)\mapsto t(x,\mu)$ is
measurable, and consequently $(x,y,\mu)\mapsto{\mathbf{1}}\\{y\in
Z_{t(x,\mu)}(\mu)\\}$ is a measurable mapping. Let us now fix
$x\in{\mathbb{X}}$. For $\mu\in{\mathbf{N}}$ we use the shorthand notation
$Z(\mu):=Z_{t(x,\mu)}(\mu)$. To prove that $Z$ is a stopping set, we check
(A.1). Let $\mu,\psi\in{\mathbf{N}}$ such that $\psi(Z(\mu))=0$. We assert
that

$\displaystyle t(x,\mu_{Z(\mu)}+\psi)=t(x,\mu).$ (2.8)

Assume that $t(x,\mu)=\infty$ (implying $Z(\mu)=Z_{\infty}(\mu)$), which is
equivalent to $x\notin Z_{\infty}(\mu)$. By (A.1) this means that $x\notin
Z_{\infty}(\mu_{Z_{\infty}(\mu)}+\psi)$, so that
$t(x,\mu_{Z(\mu)}+\psi)=\infty$. Assume now that $t:=t(x,\mu)<\infty$ and
abbreviate $\nu:=\mu_{Z(\mu)}+\psi$. Since $x\in
Z_{t}(\mu)=Z_{t}(\mu_{Z_{t}(\mu)}+\psi)=Z_{t}(\nu)$ we observe that
$t(x,\nu)\leq t$. Assume now that $t>0$. Then,

$\displaystyle x\notin
Z_{t-}(\mu)=\bigcup_{s<t}Z_{s}(\mu)=\bigcup_{s<t}Z_{s}(\mu_{Z_{t}(\mu)}+\psi)=Z_{t-}(\nu).$

It follows that $t(x,\mu)=t(x,\nu)$, from which one deduces (2.8) and
consequently the following chain of equalities:

$\displaystyle Z(\mu_{Z(\mu)}+\psi)$
$\displaystyle=Z_{t(x,\mu_{Z(\mu)}+\psi)}(\mu_{Z(\mu)}+\psi)=Z_{t(x,\mu)}(\mu_{Z(\mu)}+\psi)$
$\displaystyle=Z_{t(x,\mu)}(\mu_{Z_{t(x,\mu)}(\mu)}+\psi).$

Using (A.1) once again we obtain that

$\displaystyle Z(\mu_{Z(\mu)}+\psi)=Z_{t(x,\mu)}(\mu)=Z(\mu).$

This proves that $Z$ is a stopping set. To prove the second assertion we take
$n\in{\mathbb{N}}$ and define

$\displaystyle t_{n}(x,\mu):=\inf\\{t\in{\mathbb{R}}_{+}:x\in Z_{t\wedge
n}(\mu)\\},\quad x\in{\mathbb{X}},\,\mu\in{\mathbf{N}}.$

Applying the previous result to the CTDT $\\{Z_{t\wedge
n}:t\in{\mathbb{R}}_{+}\\}$ we see that

$\displaystyle Z_{n}^{\prime}(\mu):=Z_{t_{n}(x,\mu)\wedge
n}(\mu),\quad\mu\in{\mathbf{N}},$

defines a stopping set $Z_{n}^{\prime}$ with values in ${\mathcal{X}}_{0}$. By
definition, we have that $t_{n}(x,\mu)=t(x,\mu)$ if $t(x,\mu)\leq n$ and
$t_{n}(x,\mu)=\infty$ otherwise. As a consequence, we obtain that
$t_{n}(x,\mu)\wedge n=t(x,\mu)\wedge n$ and therefore $Z_{n}^{\prime}\uparrow
Z$, as required. ∎

###### Proof of Proposition 2.1.

By Lemma 2.2, $\mu\mapsto Z(\mu):=Z_{t(x,\mu)}(\mu)$ is a stopping set
satisfying the assumptions of Theorem A.6. Using the independence of $\eta$
and $\eta^{\prime}$, one infers that

$\displaystyle\mathbb{E}\big{[}g(t(x,\eta),\eta_{{\mathbb{X}}\setminus
Z(\eta)}+\eta^{\prime}_{Z(\eta)})\big{]}=\int\mathbb{E}[g(t(x,\eta_{Z(\eta)}),\eta_{{\mathbb{X}}\setminus
Z(\eta)}+\mu_{Z(\eta_{Z(\eta)})})]\,\Pi_{\lambda}(d\mu),$ (2.9)

where $\Pi_{\lambda}$ denotes the distribution of $\eta$ and where we have
also used (2.8) and (A.1) with $\psi=0$. By virtue of (A.6), the right-hand
side of (2.9) equals

$\displaystyle\iint\mathbb{E}[g(t(x,\eta_{Z(\eta)}),\nu_{{\mathbb{X}}\setminus
Z(\eta)}+\mu_{Z(\eta_{Z(\eta)})})]$
$\displaystyle\,\Pi_{\lambda}(d\nu)\,\Pi_{\lambda}(d\mu)$
$\displaystyle=\int\mathbb{E}[g(t(x,\eta_{Z(\eta)}),\mu)]\,\Pi_{\lambda}(d\mu),$

where the equality comes from the complete independence property of a Poisson
process (and again (A.2)). By (2.8), the last term in the previous equality
coincides with the right-hand side of the asserted identity. ∎

The next statement is used in the proof of our main estimates.

######  Proposition 2.3.

Suppose that $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT. Let $\eta$ and
$\eta^{\prime}$ be two independent Poisson processes with intensity measure
$\lambda$. Let $m\in{\mathbb{N}}$ and
$g\colon{\mathbf{N}}^{m}\to{\mathbb{R}}_{+}$ be measurable. Then, for all
$t_{1},\ldots,t_{m}\in[0,\infty]$ with $t_{1}<\cdots<t_{m}$,

$\displaystyle\mathbb{E}[g(\eta_{Z_{t_{1}}(\eta)},\ldots,\eta_{Z_{t_{m}}(\eta)},\eta_{{\mathbb{X}}\setminus
Z_{t_{m}}(\eta)})]=\mathbb{E}[g(\eta_{Z_{t_{1}}(\eta)},\ldots,\eta_{Z_{t_{m}}(\eta)},\eta^{\prime}_{{\mathbb{X}}\setminus
Z_{t_{m}}(\eta)})].$ (2.10)

###### Proof.

We apply Theorem A.6 (or equivalently (A.9)) with $Z=Z_{t_{m}}$. By (A.1) we
have for each $i\in\\{1,\ldots,m\\}$ that
$Z_{t_{i}}(\eta)=Z_{t_{i}}(\eta_{Z_{t_{m}}})$. The result follows. ∎

###  3 The OSSS inequality for Poisson functionals

The main result of the section is an OSSS inequality for Poisson functionals,
stated in the forthcoming Theorem 3.2.

We will now list a set of assumptions and notational conventions. We fix a
locally finite measure $\lambda$ on ${\mathbb{X}}$, and assume moreover that
$\lambda$ is diffuse.

  1. (a)

Let $\eta$ and $\eta^{\prime}$ be independent Poisson processes on
${\mathbb{X}}$ with intensity measure $\lambda$.

  2. (b)

Let $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ be a CTDT. As before, set
$Z_{\infty}:=\cup_{t\in{\mathbb{R}}_{+}}Z_{t}$ and write $Z:=Z_{\infty}$. For
$t\in[0,\infty]$, we use the notation

$\displaystyle\zeta_{t}\equiv\zeta_{t}(\eta,\eta^{\prime}):=\eta_{Z(\eta)\setminus
Z_{t}(\eta)}+\eta^{\prime}_{Z_{t}(\eta)}+\eta^{\prime}_{{\mathbb{X}}\setminus
Z(\eta)};$ (3.1)

observe that $\zeta_{0}=\eta_{Z}+\eta^{\prime}_{{\mathbb{X}}\setminus Z}$.

  3. (c)

Consider a mapping $f\colon{\mathbf{N}}\to{\mathbb{R}}$ such that
$\mathbb{E}|f(\eta)|<\infty$ and $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT
determining $f$, meaning that

$\displaystyle f(\mu)=f(\mu_{Z_{\infty}(\mu)}),\quad\mu\in{\mathbf{N}},$ (3.2)

and moreover

$\displaystyle
f(\zeta_{t})\overset{\mathbb{P}}{\longrightarrow}f(\eta^{\prime}),\quad\mbox{as}\,\,t\to\infty.$
(3.3)

  4. (d)

Assume that

$\displaystyle\lambda(Z_{t}(\mu)\setminus
Z_{t-}(\mu))=0,\quad\mu\in{\mathbf{N}},\,\,t\in{\mathbb{R}}_{+}$ (3.4)

and

$\displaystyle\mathbb{P}(\text{$\eta(Z_{t}(\eta)\setminus Z_{t-}(\eta))\leq 1$
for all $t\in{\mathbb{R}}_{+}$})=1.$ (3.5)

######  Remark 3.1.

If $Z$ is ${\mathcal{X}}_{0}$-valued, then assumption (3.3) holds for any
function $f$. Indeed, in this case we have that $\zeta_{t}\to\zeta_{\infty}$
in the discrete topology. For analogous reasons, such an assumption also holds
if $f$ is supported by a set in ${\mathcal{X}}_{0}$.

A CTDT verifying (3.4) is said to be $\lambda$-continuous. In order to
simplify the notation, in the discussion to follow we will sometimes (but not
always) write $Z_{t}$, $Z$, …, instead of $Z_{t}(\eta),Z(\eta)$, and so on.
The next statement is one of the main results of the paper.

######  Theorem 3.2 (OSSS inequality for Poisson functionals).

Let assumptions (a)–(d) above prevail. Then,

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]\leq 2\int\mathbb{P}(x\in
Z(\eta))\mathbb{E}[|D_{x}f(\eta)|]\,\lambda(dx),$ (3.6)

where $D_{x}f(\eta)=f(\eta+\delta_{x})-f(\eta)$ is the previously introduced
add-one cost operator at $x$.

A discrete time version of the above theorem which provides some insights into
the above inequality can be found in the first arxiv version of the paper.

###### Proof.

A direct application of (A.1) yields $Z(\eta_{Z}+\eta^{\prime}_{Z^{c}})=Z$. By
virtue of (3.2),(A.3), (3.3) and $\mathbb{E}[\lambda(Z_{0})]=0$ we have that
$f(\zeta_{0})=f(\eta)$, $\mathbb{P}$-a.s., and also

$\displaystyle
f(\eta)-f(\zeta_{t})\stackrel{{\scriptstyle\mathbb{P}}}{{\longrightarrow}}f(\eta)-f(\eta^{\prime})=f(\zeta_{0})-f(\zeta_{\infty}),\quad
t\to\infty.$ (3.7)

Since the sets $Z_{t}$ are ${\mathcal{X}}_{0}$-valued and $\eta,\eta^{\prime}$
are locally finite, it follows from (2.1) and (2.2) that the function
$t\mapsto\zeta_{t}$ is right-continuous (w.r.t. the discrete metric) and that
it has left-hand limits on $(0,\infty)$, given by

$\displaystyle\zeta_{t-}=\eta_{Z(\eta)\setminus
Z_{t-}(\eta)}+\eta^{\prime}_{Z_{t-}(\eta)}+\eta^{\prime}_{{\mathbb{X}}\setminus
Z(\eta)}.$ (3.8)

Since $\zeta_{t-}\neq\zeta_{t}$ implies that $\eta(Z_{t}(\eta)\setminus
Z_{t-}(\eta))+\eta^{\prime}(Z_{t}(\eta)\setminus Z_{t-}(\eta))>0$ we see that
the set $\\{t>0:\zeta_{t-}\neq\zeta_{t}\\}$ is contained in

$\displaystyle
A:=\\{t(x,\eta):x\in\operatorname{supp}\eta\cup\operatorname{supp}\eta^{\prime},t(x,\eta)<\infty\\},$

where we have used the notation (2.5). The set $A$ is locally finite and
$t\mapsto\zeta_{t}$ is constant on any connected component of
$[0,\infty)\setminus A$. Using (3.7), we infer that
$f(\zeta_{0})-f(\zeta_{\infty})$ is the limit in probability, as $T\to\infty$,
of $f(\zeta_{0})-f(\zeta_{T})=-\sum_{t\leq
T}\big{(}f(\zeta_{t})-f(\zeta_{t-})\big{)}$. Selecting a sequence
$T_{n}\to\infty$ such that the above convergence takes place $\mathbb{P}$-a.s.
and applying the triangle inequality, yields the bound

$\displaystyle\mathbb{E}[|f(\zeta_{0})-f(\zeta_{\infty})|]\leq\mathbb{E}\bigg{[}\sum_{t\in
A}|f(\zeta_{t})-f(\zeta_{t-})|\bigg{]}\leq J+J^{\prime},$ (3.9)

where

$\displaystyle J$
$\displaystyle:=\mathbb{E}\bigg{[}\int{\mathbf{1}}\\{t(x,\eta)<\infty\\}{\mathbf{1}}\\{\eta(Z_{t(x,\eta)}(\eta)\setminus
Z_{t(x,\eta)-}(\eta))=1\\}|f(\zeta_{t(x,\eta)})-f(\zeta_{t(x,\eta)-})|\,\eta(dx)\bigg{]},$
$\displaystyle J^{\prime}$
$\displaystyle:=\mathbb{E}\bigg{[}\int{\mathbf{1}}\\{t(x,\eta)<\infty\\}{\mathbf{1}}\\{\eta(Z_{t(x,\eta)}(\eta)\setminus
Z_{t(x,\eta)-}(\eta))=0\\}|f(\zeta_{t(x,\eta)})-f(\zeta_{t(x,\eta)-})|\,\eta^{\prime}(dx)\bigg{]}$

and where we have used (3.5) in the expression of $J$. By independence of
$\eta$ and $\eta^{\prime}$ and the Mecke equation (1.9),

$\displaystyle J=\int\mathbb{E}[{\mathbf{1}}\\{t(x,\eta_{x})<\infty\\}$
$\displaystyle{\mathbf{1}}\\{\eta_{x}(Z_{t(x,\eta)}(\eta_{x})\setminus
Z_{t(x,\eta)-}(\eta_{x}))=1\\}$
$\displaystyle\times|f(\zeta_{t(x,\eta)}(\eta_{x},\eta^{\prime}))-f(\zeta_{t(x,\eta_{x})-}(\eta_{x},\eta^{\prime}))|]\,\lambda(dx),$

where $\mu_{x}:=\mu+\delta_{x}$ for $\mu\in{\mathbf{N}}$ and
$x\in{\mathbb{X}}$ and where we have used (2.7). Similarly,

$\displaystyle J^{\prime}=\int\mathbb{E}[{\mathbf{1}}\\{t(x,\eta)<\infty,$
$\displaystyle\eta(Z_{t(x,\eta)}(\eta)\setminus Z_{t(x,\eta)-}(\eta))=0\\}$
$\displaystyle\times|f(\zeta_{t(x,\eta)}(\eta,\eta^{\prime}_{x}))-f(\zeta_{t(x,\eta)-}(\eta,\eta^{\prime}_{x}))|]\,\lambda(dx).$

Fix $x\in{\mathbb{X}}$. By (3.4) and the independence of $\eta$ and
$\eta^{\prime}$ we have that, $\mathbb{P}$-a.s.,

$\displaystyle\eta^{\prime}(Z_{t(x,\eta)}(\eta)\setminus
Z_{t(x,\eta)-}(\eta))=\eta^{\prime}(Z_{t(x,\eta)}(\eta_{x})\setminus
Z_{t(x,\eta)-}(\eta_{x}))=0\quad\text{if $t(x,\eta)<\infty$}.$ (3.10)

If $\eta_{x}(Z_{t(x,\eta)}(\eta_{x})\setminus Z_{t(x,\eta)-}(\eta_{x}))=1$
then (2.6) shows that $\eta(Z_{t(x,\eta)}(\eta_{x})\setminus
Z_{t(x,\eta)-}(\eta_{x}))=0$. Therefore we obtain from (3.10) that,
$\mathbb{P}$-a.s.,

$\displaystyle\zeta_{t(x,\eta)-}(\eta_{x},\eta^{\prime})$
$\displaystyle=\zeta_{t(x,\eta)}(\eta_{x},\eta^{\prime})+\delta_{x}\quad\text{if
$t(x,\eta)<\infty$}.$

By (2.6),

$\displaystyle\zeta_{t(x,\eta)}(\eta,\eta^{\prime}_{x})$
$\displaystyle=\zeta_{t(x,\eta)}(\eta,\eta^{\prime})+\delta_{x},$

Furthermore, if $t(x,\eta)<\infty$ we obtain from (3.10) that

$\displaystyle\zeta_{t(x,\eta)-}(\eta,\eta^{\prime}_{x})$
$\displaystyle=\zeta_{t(x,\eta)}(\eta,\eta^{\prime}).$

Therefore,

$\displaystyle\max(J,J^{\prime})$
$\displaystyle\leq\mathbb{E}\bigg{[}\int{\mathbf{1}}\\{t(x,\eta_{x})<\infty\\}|f(\zeta_{t(x,\eta)}(\eta_{x},\eta^{\prime})+\delta_{x})-f(\zeta_{t(x,\eta)}(\eta_{x},\eta^{\prime}))|\,\lambda(dx)\bigg{]}.$

To finish the proof we use the identity

$\displaystyle\mathbb{P}(\zeta_{t(x,\eta)}\in\cdot\mid t(x,\eta))$
$\displaystyle=\mathbb{P}(\eta\in\cdot),\quad\mathbb{P}\text{-a.s.\ on
$\\{t(x,\eta)<\infty\\}$},$ (3.11)

which holds for all $x\in{\mathbb{X}}$. To see this, we fix $x\in{\mathbb{X}}$
and consider a measurable function
$g\colon{\mathbb{R}}_{+}\times{\mathbf{N}}\to{\mathbb{R}}_{+}$. Let
$\eta^{\prime\prime}$ be a copy of $\eta$, independent of
$(\eta,\eta^{\prime})$ and set $T:=t(x,\eta)$. Since $\eta$ is independently
scattered, we have that

$\displaystyle\mathbb{E}[{\mathbf{1}}\\{T<\infty\\}g(T,\zeta_{T})]=\mathbb{E}[{\mathbf{1}}\\{T<\infty\\}g(T,\eta_{Z(\eta)\setminus
Z_{T}(\eta)}+\eta^{\prime}_{Z_{T}(\eta)}+\eta^{\prime\prime}_{{\mathbb{X}}\setminus
Z(\eta)})].$

By Proposition 2.3 the conditional distribution of
$\eta_{{\mathbb{X}}\setminus Z}$ given $\\{\eta_{Z_{t}}):{t\in[0,\infty]}\\}$
is that of $\eta^{\prime\prime}_{{\mathbb{X}}\setminus Z(\eta)}$. By the
continuity properties of a CTDT, $(T,\eta_{Z(\eta)\setminus
Z_{T}(\eta)},Z_{T}(\eta))$ is measurable with respect to
$\sigma\\{\eta_{Z_{t}}:{t\in[0,\infty]}\\}$. As a consequence,

$\displaystyle\mathbb{E}[{\mathbf{1}}\\{T<\infty\\}g(T,\zeta_{T})]=\mathbb{E}[{\mathbf{1}}\\{T<\infty\\}g(T,\eta_{{\mathbb{X}}\setminus
Z_{T}(\eta)}+\eta^{\prime}_{Z_{T}(\eta)})]$

In view of Proposition 2.1 this implies (3.11). From (3.11) we obtain by
conditioning that

$\displaystyle\max(J,J^{\prime})\leq\int\mathbb{P}(t(x,\eta)<\infty)\mathbb{E}[|f(\eta+\delta_{x})-f(\eta)|]\,\lambda(dx).$

Since $t(x,\eta)<\infty$ if and only if $x\in Z_{\infty}$, the asserted
inequality (3.6) now follows from (3.7) and (3.9). ∎

######  Remark 3.3.

Assume that ${\mathbb{X}}$ is a Borel subset of a complete separable metric
space with metric $\rho$ equipped with the Borel $\sigma$-field
${\mathcal{X}}$. Let $\lambda$ be a diffuse measure on ${\mathbb{X}}$ which is
finite on (metrically) bounded Borel sets. Fix $x_{0}\in{\mathbb{X}}$ and let
$Z_{t}:=\\{x\in{\mathbb{X}}:\rho(x_{0},x)\leq t\\}$, $t\geq 0$. Then
$\\{Z_{t}:t\geq 0\\}$ is a CTDT which does not depend on $\mu\in{\mathbf{N}}$.
If, moreover, $\lambda(\partial Z_{t})=0$, for each $t\geq 0$, then it is easy
to see that (3.4) and (3.5) hold. If $f\colon{\mathbf{N}}\to{\mathbb{R}}$
satisfies $\mathbb{E}[|f(\eta)|]<\infty$ and $f(\eta_{{\mathbb{X}}\setminus
Z_{t}}+\eta_{Z^{\prime}_{t}})\overset{\mathbb{P}}{\longrightarrow}f(\eta)$ as
$t\to\infty$ (which is always true if $\lambda({\mathbb{X}})<\infty$), then
Theorem 3.2 implies that

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]\leq
2\int\mathbb{E}[|D_{x}f(\eta)|]\,\lambda(dx).$

In fact, the proof is much simpler in this case.

######  Remark 3.4.

We will prove in Appendix B that there exist stopping sets $Z$ that are not
$\lambda$-attainable, that is, such that $Z\neq\cup_{t\geq 0}Z_{t}$ for any
$\lambda$-continuous CTDT $\\{Z_{t}\\}$. Whether the OSSS inequality (3.6)
continues to hold for non-attainable stopping sets is a challenging problem
that we leave open for future research.

######  Remark 3.5.

It might be desirable to start the CTDT with given non-trivial stopping set
$Z_{0}$. So assume that $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ has all properties
of a CTDT except for $\mathbb{E}[\lambda(Z_{0})]=0$. Let the function $f$
satisfy the assumptions of Theorem 3.2 and let $\eta^{\prime}$ be an
independent copy of $\eta$. We assert that

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]$
$\displaystyle\leq\mathbb{E}[|f(\eta)-f(\eta_{Z\setminus
Z_{0}}+\eta^{\prime}_{Z_{0}})|]$ $\displaystyle\qquad+2\int\mathbb{P}(x\in
Z(\eta)\setminus Z_{0}(\eta))\mathbb{E}[|D_{x}f(\eta)|]\,\lambda(dx).$ (3.12)

To see this, we define $\zeta_{t}$, $t\in[0,\infty]$, by (3.1) and set
$\zeta_{0-}:=\eta_{Z}+\eta_{{\mathbb{X}}\setminus Z}$. Then

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]=\mathbb{E}[|f(\zeta_{0-})-f(\zeta_{\infty})|].\leq\mathbb{E}[|f(\zeta_{0-})-f(\zeta_{0})|]+\mathbb{E}[|f(\zeta_{0})-f(\zeta_{\infty})|].$

Here the second term can be treated as before, while the first term can be
seen to equal $\mathbb{E}[|f(\eta_{Z\setminus
Z_{0}}+\eta^{\prime}_{Z_{0}})-f(\eta)|]$ (Further details on this point are
left to the reader).

The Poincaré inequality is sharp for linear functionals of $\eta$. The
following example shows that the OSSS inequality is sharp also for other
functionals.

######  Example 1.

Assume that ${\mathbb{X}}={\mathbb{R}}^{d}$ and that $\lambda$ is the Lebesgue
measure $\lambda_{d}$. Let $W\subset{\mathbb{R}}^{d}$ be compact and
$x_{0}\in{\mathbb{R}}^{d}$. Define $\tau\colon{\mathbf{N}}\to[0,\infty]$ by

$\displaystyle\tau(\mu):=\inf\\{s\geq 0:\mu(W\cap B(x_{0},s))>0\\},$

where $B(x_{0},t)$ is the ball with radius $t$ centred at $x_{0}$. We assert
that

$\displaystyle Z_{t}(\mu):=B(x_{0},\tau(\mu)\wedge t),\quad
t\in{\mathbb{R}}_{+},\,\mu\in{\mathbf{N}},$

is a CTDT. To see this we first note that, given $\mu\in{\mathbf{N}}$ and
$s\in{\mathbb{R}}_{+}$, that the inequalities $\tau(\mu)>s$ and
$\mu(B(x_{0},s)\cap W)>0$ are equivalent. In particular $\tau$ is measurable
so that $Z_{t}$ is graph-measurable for each $t\in{\mathbb{R}}_{+}$. To check
(A.1) for $Z=Z_{t}$ we need to show that

$\displaystyle\tau(\mu)\wedge t=\tau(\mu_{B(x_{0},\tau(\mu)\wedge
t)}+\psi)\wedge t,\quad\mu\in{\mathbf{N}}$

provided that $\psi(B(x_{0},\tau(\mu)\wedge t))=0$. This can be directly
checked. Define $f\colon{\mathbf{N}}\to{\mathbb{R}}$ by
$f(\mu):={\mathbf{1}}\\{\mu(W)=0\\}$. Standard arguments yield that
$\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ and $f$ satisfy the assumptions of Theorem
3.2. We note that

$\displaystyle f(\mu+\delta_{x})-f(\mu)$
$\displaystyle={\mathbf{1}}\\{\mu(W)=0,x\notin
W\\}-{\mathbf{1}}\\{\mu(W))=0\\}$ (3.13) $\displaystyle=-{\mathbf{1}}\\{x\in
W,\mu(W)=0\\}=-{\mathbf{1}}\\{x\in W\\}f(\mu).$

Further we have $x\in Z_{\infty}(\mu)$ iff $\mu(W\cap
B^{0}(x_{0},\|x-x_{0}\|))=0$, where $B^{0}(x_{0},t)$ is the interior of
$B^{0}(x_{0},t)$. Therefore (3.6) means that

$\displaystyle\operatorname{{\mathbb{V}ar}}[f(\eta)]\leq
e^{-\lambda_{d}(W)}\int_{W}\exp[-\lambda_{d}(W\cap
B(x_{0},\|x-x_{0}\|))]\,dx.$ (3.14)

To compare this with the exact variance
$e^{-\lambda_{d}(W)}\big{(}1-e^{-\lambda_{d}(W)}\big{)}$ of $f(\eta)$ we
assume that $W-x_{0}$ is isotropic, that is invariant under rotations. In
fact, we can then assume $x_{0}=0$ without loss of generality. Let
$I\subset{\mathbb{R}}_{+}$ the a Borel set such that $x\in W$ iff $\|x\|\in
I$. Using polar coordinates, we have for each $x\in{\mathbb{R}}^{d}$ that

$\displaystyle\lambda_{d}(W\cap B(0,\|x\|))=d\kappa_{d}\int{\mathbf{1}}\\{s\in
I,s\leq\|x\|\\}s^{d-1}\,ds=\int{\mathbf{1}}\\{s\leq\|x\|\\}\,\nu(ds)$

where $\kappa_{d}:=\lambda_{d}(B(x,1))$ is the volume of the unit ball and
$\nu$ is the measure on ${\mathbb{R}}_{+}$ given by
$\nu(ds):=d\kappa_{d}{\mathbf{1}}\\{s\in I\\}s^{d-1}\,ds$. Using polar
coordinates once again we see that the right-hand side of (3.14) equals

$\displaystyle e^{-\lambda_{d}(W)}\int
e^{-\nu([0,r])}\,\nu(dr)=e^{-\lambda_{d}(W)}\big{(}1-e^{-\nu({\mathbb{R}}_{+})}\big{)}=e^{-\lambda_{d}(W)}\big{(}1-e^{-\lambda_{d}(W)}\big{)},$

where we have used a well-known formula of Lebesgue–Stieltjes calculus, see
e.g. [49, Proposition A.31]. Hence (3.6) is sharp in this case. In view of
(3.13), one sees immediately that the right-hand side of the Poincaré
inequality (1.1) equals $\lambda_{d}(W)e^{-\lambda_{d}(W)}$, which is seen to
be suboptimal with respect to the exact variance by letting
$\lambda_{d}(W)\to\infty$. It is also interesting to notice that, since
$D_{x}f(\mu)=-{\mathbf{1}}\\{x\in W\\}f(\mu)\leq 0$ and therefore
$D_{y}D_{x}f(\mu)={\mathbf{1}}\\{x,y\in W\\}f(\mu)\geq 0$, then the variance
of $f(\eta)$ can be bounded by using the restricted $L^{1}$-$L^{2}$ inequality
proved in [57, Theorem 1.6]. Such a result yields indeed that

$\operatorname{{\mathbb{V}ar}}[f(\eta)]\leq\frac{1}{2}\int_{W}\frac{\mathbb{E}[(D_{x}f(\eta))^{2}]}{1+\log\frac{1}{\mathbb{E}[|D_{x}f(\eta)|]^{1/2}}}\lambda_{d}(dx)=\left(1\\!-\\!\frac{2}{2\\!+\\!\lambda_{d}(W)}\right)e^{-\lambda_{d}(W)},$

an estimate that also improves – albeit not as sharply – the Poincaré
inequality.

###  4 Variants of the OSSS inequality

In this section, we present some variants and extensions of the OSSS
inequality for Poisson functionals stated in Theorem 3.2. Firstly, in the
spirit of [60, Theorem B.1], we extend Theorem 3.2 to two functions and to the
case of a randomized CTDT (Corollary 4.1 below). The two function version has
recently been used by [41] to derive critical exponent inequalities for random
cluster models on transitive graphs. We will then present a variant of the
OSSS inequality for marked Poisson point processes (see Theorem 4.2) – a
declination of our main findings that will be very useful for the applications
in Part III. For the rest of the section, $\eta$ is a Poisson process on
${\mathbb{X}}$, with a locally finite and diffuse intensity measure $\lambda$.

Let $(\mathbb{Y},\mathcal{Y})$ be a measurable space and suppose that $Z^{y}$
is, for $\mathbb{P}(Y\in\cdot)$-a.e. $y$, a stopping set, such that the
mapping $(\mu,x,y)\mapsto{\mathbf{1}}\\{x\in Z^{y}(\mu)\\}$ is (jointly)
measurable on ${\mathbf{N}}\times{\mathbb{X}}\times{\mathbb{Y}}$. If $Y$ is an
independent $\mathbb{Y}$-valued random element, then $Z^{Y}$ is called a
randomized stopping set. If $\\{Z_{t}^{y}:t\in{\mathbb{R}}_{+}\\}$ is a CTDT
for all $y\in{\mathbb{Y}}$ such that the above measurability properties are
satisfied, then $\\{Z_{t}^{Y}:t\in{\mathbb{R}}_{+}\\}$ is called a randomized
continuous time decision tree (randomized CTDT). In this case, we say that
$\\{Z_{t}^{Y}:t\in{\mathbb{R}}_{+}\\}$ is a randomized CTDT determining
$f\colon{\mathbf{N}}\to{\mathbb{R}}$ if $\\{Z_{t}^{y}:t\in{\mathbb{R}}_{+}\\}$
is a CTDT determining $f$ for all $y\in{\mathbb{Y}}$, where the property of
being a CTDT determining a given function $f$ corresponds to the two
properties (3.2)–(3.3) introduced above.

######  Corollary 4.1.

Let $f\colon{\mathbf{N}}\to[-1,1]$ and $g\colon{\mathbf{N}}\to{\mathbb{R}}$ be
measurable and such that $\mathbb{E}[|g(\eta)|]<\infty$. Let $Y$ be an
independent $\mathbb{Y}$-valued random element. Let
$\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}=\\{Z_{t}^{Y}:t\in{\mathbb{R}}_{+}\\}$ be a
randomized CTDT determining $f$ such that, for $\mathbb{P}(Y\in\cdot)$-a.e.
$y\in{\mathbb{Y}}$, $\\{Z_{t}^{y}\\}$ satisfies (3.4) and (3.5). Let $g$ also
satisfy (3.3). Then,

$\displaystyle|\operatorname{{\mathbb{C}ov}}(f,g)|\leq 2\int\mathbb{P}(x\in
Z(\eta))\mathbb{E}[|D_{x}g(\eta)|]\,\lambda(dx),$ (4.1)

where $Z(\eta):=Z_{\infty}(\eta)=Z^{Y}_{\infty}(\eta)$, and therefore

$\displaystyle\operatorname{{\mathbb{V}ar}}(f)\leq 2\int\mathbb{P}(x\in
Z(\eta))\mathbb{E}[|D_{x}f(\eta)|]\,\lambda(dx).$ (4.2)

###### Proof.

We first observe that the specific form of the two inequalities in the
statement implies that it suffices to prove them for a generic CTDT
determining $f$ and satisfying (3.4) and (3.5); one can then apply the
obtained estimate to $\\{Z_{t}^{y}\\}$, for $\mathbb{P}(Y\in\cdot)$-a.e. $y$,
and take expectations with respect to $Y$. Thus, we will now prove the
statement for a CTDT $\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ determining $f$ and
such that (3.4) and (3.5) are verified. Let $\eta^{\prime}$ be an independent
copy of $\eta$. We will again use the definition of $\zeta_{t}$ given in
(3.1). Since $f(\eta)=f(\zeta_{0})$ as $Z_{t}$ is a CTDT for $f$,
$\zeta_{0}\overset{d}{=}\eta$ and $\zeta_{\infty}=\eta^{\prime}$, we have that

$f(\eta)g(\eta)\overset{d}{=}f(\zeta_{0})g(\zeta_{0}),\,f(\eta)g(\eta^{\prime})=f(\zeta_{0})g(\zeta_{\infty}).$

Thus we obtain that

$|\operatorname{{\mathbb{C}ov}}(f,g)|=|\mathbb{E}[f(\eta)(g(\eta)-g(\eta^{\prime}))]|=|\mathbb{E}(f(\zeta_{0})(g(\zeta_{0})-g(\zeta_{\infty}))]|\leq\mathbb{E}[|g(\zeta_{0})-g(\zeta_{\infty})|],$

where we have used that $|f|\leq 1$ in the last inequality. Observe that
$\mathbb{E}[|g(\zeta_{0})-g(\zeta_{\infty})|]$ is the same as the LHS of (3.9)
with $g$ replacing $f$. Now, the rest of the proof follows the same lines as
that of Theorem 3.2 once it is observed that, after having established (3.9)
in such a proof using the fact that $g$ also satisfies (3.3), the fact that
$\\{Z_{t}\\}$ is a CTDT determining $f$ is never used, and only the stopping
set properties of $Z_{t}$ are exploited. ∎

We stress that – as opposed to the main OSSS inequality (3.6) – relation (4.2)
is derived under the assumption that $|f|\leq 1$, and is consequently not
homogeneous in $f$.

We will now generalize Theorem 3.2 to marked Poisson processes. We let
$({\mathbb{M}},\mathcal{M})$ be another Borel space and consider the product
${\mathbb{X}}\times{\mathbb{M}}$. As in Subsection 1.5 we take
$B_{n}\in{\mathcal{X}}$, $n\in{\mathbb{N}}$, satisfying
$B_{n}\uparrow{\mathbb{X}}$. However, this time we define the localizing
subring of ${\mathcal{X}}\otimes\mathcal{M}$ as the system of all sets of the
form $B\cap(B_{n}\times{\mathbb{M}})$ for some
$B\in{\mathcal{X}}\otimes\mathcal{M}$ and $n\in{\mathbb{N}}$. A measure $\nu$
on $({\mathbb{X}},{\mathcal{X}})$ which is finite on ${\mathcal{X}}_{0}$ is
called locally finite. In that case $\nu(B_{n}\times{\mathbb{M}})<\infty$ for
each $n\in{\mathbb{N}}$.

Let $\lambda$ be a locally finite measure on ${\mathbb{X}}\times{\mathbb{M}}$
such that $\bar{\lambda}:=\lambda(\cdot\times{\mathbb{M}})$ is diffuse and let
$\eta$ be a Poisson process with intensity measure $\lambda$. According to
Remark A.7, in such a framework a stopping set (on ${\mathbb{X}}$) is a graph-
measurable mapping
$Z\colon{\mathbf{N}}({\mathbb{X}}\times{\mathbb{M}})\to{\mathcal{X}}$
satisfying (A.1). A CTDT on ${\mathbb{X}}$ is a family
$\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ of stopping sets on ${\mathbb{X}}$ having
the properties (2.1)–(2.2); we stress once again that, in the present
framework, each $Z_{t}$ is a $\mathcal{X}$-valued mapping defined on
${\mathbf{N}}({\mathbb{X}}\times{\mathbb{M}})$. A CTDT
$\\{Z_{t}:t\in{\mathbb{R}}_{+}\\}$ is said to determine a given measurable
mapping $f\colon{\mathbf{N}}({\mathbb{X}}\times{\mathbb{M}})\to{\mathbb{R}}$
if

$\displaystyle
f(\mu)=f(\mu_{Z(\mu)\times{\mathbb{M}}}),\quad\mu\in{\mathbf{N}}({\mathbb{X}}\times{\mathbb{M}}),$
(4.3)

where $Z:=Z_{\infty}$, and relation (3.3) holds, with $Z_{t}(\eta)$ and
$Z(\eta)=Z_{\infty}(\eta)$ replaced by $Z_{t}(\eta)\times{\mathbb{M}}$ and
$Z_{\infty}(\eta)\times{\mathbb{M}}=Z(\eta)\times{\mathbb{M}}$, respectively.
Let $\bar{\eta}:=\eta(\cdot\times{\mathbb{M}})$. In the next theorem we shall
assume that

$\displaystyle\bar{\lambda}(Z_{t}(\mu)\setminus
Z_{t-}(\mu))=0,\quad\mu\in{\mathbf{N}},\,t\in{\mathbb{R}}_{+}$ (4.4)

and

$\displaystyle\mathbb{P}(\text{$\bar{\eta}(Z_{t}(\eta)\setminus
Z_{t-}(\eta))\leq 1$ for all $t\in{\mathbb{R}}_{+}$})=1.$ (4.5)

######  Theorem 4.2 (OSSS inequality for marked processes).

Let $f\colon{\mathbf{N}}({\mathbb{X}}\times{\mathbb{M}})\to{\mathbb{R}}$ be
measurable such that $\mathbb{E}[|f(\eta)|]<\infty$. Let $Y$ be an independent
$\mathbb{Y}$-valued random element. Let $\\{Z_{t}\\}=\\{Z_{t}^{Y}\\}$ be a
randomized CTDT determining $f$ such that for $\mathbb{P}(Y\in\cdot)$-a.e.
$y\in{\mathbb{Y}}$, $\\{Z_{t}^{y}\\}$ satisfies (4.4) and (4.5). Let
$\eta^{\prime}$ be an independent copy of $\eta$. Then

$\displaystyle\mathbb{E}[|f(\eta)-f(\eta^{\prime})|]\leq 2\int\mathbb{P}(x\in
Z(\eta))\mathbb{E}[|D_{(x,w)}f(\eta)|]\,\lambda(d(x,w)).$ (4.6)

###### Proof.

As with the proof of Corollary 4.1, we will prove the result for a
deterministic CTDT. In particular, we will show that
$\tilde{Z}_{t}=Z_{t}\times{\mathbb{M}},\,t\geq 0,$ is a CTDT on
${\mathbb{X}}\times{\mathbb{M}}$ satisfying the assumptions of Theorem 3.2.
The stopping set properties are immediate, see Remark A.8. Further, it is easy
to check that $\tilde{Z}_{t}$ satisfies (2.1) and (2.2) (as a collection of
set-valued mappings with values in $\mathcal{X}\otimes\mathcal{M}$), since
$Z_{t}$ satisfies the same conditions (as a collection of mappings with values
in $\mathcal{X}$). Further, by the definition of
$\tilde{Z}_{t},\tilde{\lambda},\tilde{\eta}$, (4.4) and (4.5) imply (3.4) and
(3.5) respectively. Also, (3.3) is assumed. Thus, we have that $\tilde{Z}_{t}$
is a CTDT as in Theorem 3.2 and further $\mathbb{P}(x\in
Z(\eta))=\mathbb{P}((x,w)\in\tilde{Z}(\eta))$ for any $w\in{\mathbb{M}}$. This
completes the proof. ∎

##  Part II Quantitative Noise Sensitivity

Throughout this part, we adopt the general framework and notation for Poisson
processes and stopping sets introduced in Section 1.5 and Appendix A,
respectively. In particular, we denote by $\eta$ a Poisson process on
${\mathbb{X}}$ with locally finite (and not necessarily diffuse) intensity
$\lambda$.

###  5 Schramm-Steif inequalities on the Poisson space

The next result is a crucial finding of the paper: it provides an upper bound
on the variance of conditional expectations of multiple integrals, where the
conditioning is with respect to the restriction of $\eta$ to a randomized
stopping set, a notion that has been introduced in Section 4. For the sake of
conciseness, the proof of Theorem 5.1 will only be provided in the case where
$Z$ is non-randomized. The general case follows from an averaging argument
analogous to the one used in the proof of Corollary 4.1 (to simplify the
notation we also suppress the dependence on the independent random element
$Y$). A similar strategy is adopted (sometimes tacitly) elsewhere in Part II —
see e.g. the proof of (5.2) below.

In the subsequent discussion, we will mostly focus on (possibly randomized)
stopping sets $Z$ verifying the assumption that there exists an increasing
sequence of stopping sets $\\{Z_{k}:k\geq 1\\}$ such that

$\mathbb{P}(\eta(Z_{k}(\eta))<\infty)=1,\mbox{ $k\geq 1$, \quad and }\quad
Z=\bigcup_{k\geq 1}Z_{k}.$ (5.1)

We stress that, in the case of randomized stopping sets, we implicitly assume
that the sets $Z_{k}=Z_{k}^{Y}$ are such that the randomization $Y$ is the
same for every $k$. The reason for requiring (5.1) is that, according to
Theorem A.6, such a condition is sufficient for the Markov property (A.9) to
hold. As already done in other parts of the paper, given a (randomized)
stopping set $Z$ we will often write $Z$ for $Z(\eta)$ (resp. $Z^{Y}(\eta)$).

######  Theorem 5.1.

Let $Z$ be a randomized stopping set verifying (5.1). Let $k\in{\mathbb{N}}$
and $u\in L^{2}(\lambda^{k})$ be $\lambda^{k}$-a.e. symmetric. Then,

$\displaystyle\mathbb{E}[\mathbb{E}[I_{k}(u)\mid\eta_{Z}]^{2}]\leq k!\int
u(x_{1},\ldots,x_{k})^{2}\,\mathbb{P}(\\{x_{1},\ldots,x_{k}\\}\cap
Z(\eta)\neq\emptyset)\,\lambda^{k}(\mathrm{d}(x_{1},\ldots,x_{k})),$

where $\eta_{Z}:=\eta_{Z(\eta)}$ denotes the restriction of $\eta$ to
$Z(\eta)$.

###### Proof.

As announced, in the proof we assume that $Z$ is non-randomized. For every
$k\geq 1$, define $\mathcal{S}_{k}$ to be the subset of
$L^{2}(\lambda^{k})\cap L^{1}(\lambda^{k})$ composed of symmetric bounded
kernels $u$, such that the support of $u$ is contained in a set of the type
$A\times\cdots\times A$, with $A\in\mathcal{X}_{0}$. By virtue of the local
finiteness of $\lambda$ and of the fact that
$\sigma({\mathcal{X}}_{0})={\mathcal{X}}$, one has that, for every a.e.
symmetric $u\in L^{2}(\lambda^{k})$, there exists a sequence $\\{u_{n}:n\geq
1\\}\subset\mathcal{S}_{k}$ such that $u_{n}\to u$ in $L^{2}(\lambda^{k})$.
Since both sides of the inequality in the statement are trivially continuous
in $u$ (because of (1.11) and the contractive properties of conditional
expectations), it follows that it is enough to prove the desired estimate for
$u\in\mathcal{S}_{k}$, in which case one has also that

$\displaystyle\int\bigg{(}\int
u(x_{1},\ldots,x_{k})\lambda^{k-i}(\mathrm{d}(x_{i+1},\ldots,x_{k}))\bigg{)}^{2}\,\lambda^{i}(\mathrm{d}(x_{1},\ldots,x_{i}))<\infty,\quad
i\in\\{1,\ldots,k\\}.$ (5.2)

For $k\in{\mathbb{N}}_{0}$, $B\in{\mathcal{X}}$ and $\mu\in{\mathbf{N}}$ we
define

$\displaystyle
I_{k,B,\mu}(u):=\sum^{k}_{i=0}(-1)^{k-i}\binom{k}{i}\mu^{(i)}_{B}\otimes\lambda^{k-i}_{B}(u),$
(5.3)

where $\mu^{(i)}$ is the $i$-th factorial measure of $\mu$ and
$\mu^{(i)}_{B}:=(\mu_{B})^{(i)}$ is the $i$-th factorial measure of the
restriction $\mu_{B}$ of $\mu$ to $B$. (We adopt the standard conventions that
$\mu^{(0)}(c)=\lambda^{0}(c)=c$ for all $c\in{\mathbb{R}}$,
$\mu^{(0)}\otimes\lambda^{k}:=\lambda^{k}$ and
$\mu^{(k)}\otimes\lambda^{0}:=\mu^{(k)}$.) Since $u\in\mathcal{S}_{k}$ we have
from the multivariate Mecke formula (see [49, Section 4.2]) that
$I_{k,B,\mu}(u)$ is well-defined and finite for
$\mathbb{P}(\eta\in\cdot)$-a.e. $\mu\in{\mathbf{N}}$. By [49, Proposition
12.9] we have $\mathbb{P}$-a.s. the pathwise identity

$\displaystyle I_{k}(u)=I_{k,{\mathbb{X}},\eta}(u).$ (5.4)

We wish to exploit the conditional variance formula

$\displaystyle\mathbb{E}\big{[}\mathbb{E}[I_{k}(u)\mid\eta_{Z}]^{2}\big{]}=\mathbb{E}\big{[}I_{k}(u)^{2}\big{]}-\mathbb{E}[\operatorname{{\mathbb{V}ar}}[I_{k}(u)\mid\eta_{Z}]],$
(5.5)

which is a direct consequence of the law of the total expectation. To deal
with the conditional variance of the right-hand side of (5.5), we use Theorem
A.6 together with (5.1) to infer that the conditional distribution of
$I_{k}(u)$ given $\eta_{Z}=\mu$ coincides (for
$\mathbb{P}(\eta_{Z}\in\cdot)$-a.e. $\mu$) with that of

$\displaystyle{{}J}:=\sum^{k}_{i=0}(-1)^{k-i}{\binom{k}{i}}\big{(}(\mu+\eta_{Z(\mu)^{c}})^{(i)}\otimes\lambda^{k-i}\big{)}(u).$

We stress that, since $u\in\mathcal{S}_{k}$, such a quantity is well-defined
for $\mathbb{P}(\eta_{Z}\in\cdot)$-a.e. $\mu$. Writing
$\lambda=\lambda_{Z(\mu)}+\lambda_{Z(\mu)^{c}}$ we deduce from a simple
calculation that

$\displaystyle{{}J}=\sum^{k}_{i=0}\binom{k}{i}I_{i,Z(\mu)^{c},\eta}(I_{k-i,Z(\mu),\mu}(u)),$

where the inner (deterministic) multiple integral refers to the arguments of
$u$ with index in $\\{i+1,\ldots,k\\}$ (with the first $i$ variables fixed)
and the outer (stochastic) integral is performed with respect to the remaining
variables. We observe that, since $u\in\mathcal{S}_{k}$, one has that, for
$\mathbb{P}(\eta_{Z}\in\cdot)$-a.e. $\mu$,

$\int_{({\mathbb{X}}\setminus
Z(\mu))^{i}}\big{(}I_{k-i,Z(\mu),\mu}(u_{(x_{1},\ldots,x_{i})})\big{)}^{2}\,\lambda^{i}(\mathrm{d}(x_{1},\ldots,x_{i}))<\infty,\quad
i=1,...,k,$

where $u_{(x_{1},\ldots,x_{i})}$ denotes the function
$(x_{i+1},\ldots,x_{k})\mapsto u(x_{1},\ldots,x_{k})$. By virtue of (5.2) we
can now apply the orthogonality relations (1.11) with $\eta$ replaced by
$\eta_{Z(\mu)^{c}}$ to obtain for $\mathbb{P}(\eta_{Z}\in\cdot)$-a.e. $\mu$

$\displaystyle\operatorname{{\mathbb{V}ar}}[I_{k}(u)\mid\eta_{Z}=\mu]=\sum^{k}_{i=1}\binom{k}{i}^{2}i!\int_{({\mathbb{X}}\setminus
Z(\mu))^{i}}\big{(}I_{k-i,Z(\mu),\mu}(u_{(x_{1},\ldots,x_{i})})\big{)}^{2}\,\lambda^{i}(\mathrm{d}(x_{1},\ldots,x_{i})).$

Dropping all summands except the $k$-th and integrating w.r.t. the
distribution of $\eta$ we get

$\displaystyle\mathbb{E}[\operatorname{{\mathbb{V}ar}}[I_{k}(u)\mid\eta_{Z}]]\geq
k!\,\mathbb{E}\bigg{[}\int_{({\mathbb{X}}\setminus
Z(\eta))^{k}}u(x_{1},\ldots,x_{k})^{2}\,\lambda^{k}(\mathrm{d}(x_{1},\ldots,x_{k}))\bigg{]}.$

Inserting this into (5.5) we obtain that

$\displaystyle\mathbb{E}\big{[}$
$\displaystyle\mathbb{E}[I_{k}(u)\mid\eta_{Z}]^{2}\big{]}$ $\displaystyle\leq
k!\mathbb{E}\bigg{[}\int
u(x_{1},\ldots,x_{k})^{2}(1-{\mathbf{1}}\\{x_{1}\notin
Z(\eta),\ldots,x_{k}\notin
Z(\eta)\\})\,\lambda^{k}(\mathrm{d}(x_{1},\ldots,x_{k}))\bigg{]}$

and hence the assertion. ∎

By inspection of the proof of Theorem 5.1, one sees that our arguments only
exploit the fact that $Z$ verifies the Markov property (A.9). It is allowed to
choose $Z\equiv{\mathbb{X}}$ in Theorem 5.1. Then the inequality boils down to
an equality, namely to the case $k=m$ and $u=v$ of the isometry property
(1.11).

######  Corollary 5.2.

Consider measurable mappings $f,g:{\mathbf{N}}\to{\mathbb{R}}$ such that
$\mathbb{E}[f(\eta)^{2}],\,\mathbb{E}[g(\eta)^{2}]<\infty$. We denote by
$\\{u_{k}:k=0,1,...\\}$ the sequence of kernels of the Wiener-Itô chaos
expansion of $f(\eta)$ (see (1.10)), and by $\\{v_{k}:k=0,1,...\\}$ the
kernels of the decomposition of $g$. We assume that $f$ is determined by a
randomized stopping set $Z$ verifying (5.1). Then, for all $k\geq 1$, we have
that

$\displaystyle(\mathbb{E}$ $\displaystyle[I_{k}(u_{k})I_{k}(v_{k})])^{2}$
$\displaystyle\leq
k!\,\mathbb{E}[f(\eta)^{2}]\int\mathbb{P}(\\{x_{1},\ldots,x_{k}\\}\cap
Z(\eta)\neq\emptyset)v_{k}^{2}(x_{1},\ldots,x_{k})\,\lambda^{k}(\mathrm{d}(x_{1},\ldots,x_{k})).$
(5.6)

###### Proof of Corollary 5.2.

Fix $k\geq 1$, and recall from (A.2) that $f(\eta)$ is
$\sigma(\eta_{Z})$-measurable. The orthonormality properties of multiple
integrals (1.11) and the Cauchy–Schwarz inequality yield that

$\displaystyle(\mathbb{E}[I_{k}(u_{k})I_{k}(v_{k})])^{2}$
$\displaystyle=(\mathbb{E}[f(\eta)I_{k}(v_{k})])^{2}=(\mathbb{E}[f(\eta)\,\mathbb{E}[I_{k}(v_{k})\mid\eta_{Z}]])^{2}$
$\displaystyle\leq\mathbb{E}[f(\eta)^{2}]\times\mathbb{E}[\mathbb{E}[I_{k}(v_{k})\mid\eta_{Z}]^{2}].$

An application of Theorem 5.1 implies the result. ∎

We will now obtain an equivalent of the Schramm-Steif quantitative noise
sensitivity theorem (see [70, Theorem 1.8]). Several applications of this
result will be illustrated in the subsequent sections.

######  Corollary 5.3 (Schramm-Steif inequality for Poisson functionals).

Consider a measurable and square-integrable $f:{\mathbf{N}}\to{\mathbb{R}}$ as
in (1.10), and assume that $f$ is determined by a randomized stopping set $Z$
verifying (5.1). Then, for all $k\geq 1$,

$\mathbb{E}[I_{k}(u_{k})^{2}]\leq k\delta(Z)\,\mathbb{E}[f(\eta)^{2}],$ (5.7)

where $\delta(Z):=\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in Z(\eta))$.

###### Proof.

Setting $g=f$ in (5.2) and using the union bound for
$\mathbb{P}(\\{x_{1},\ldots,x_{k}\\}\cap Z\neq\emptyset)$, we derive that

$\int\mathbb{P}(\\{x_{1},\ldots,x_{k}\\}\cap
Z(\eta)\neq\emptyset)u_{k}^{2}(x_{1},\ldots,x_{k})\,\lambda^{k}(\mathrm{d}(x_{1},\ldots,\mathrm{d}x_{k}))\leq
k\delta(Z)\|u_{k}\|^{2}_{L^{2}(\lambda^{k})}.$

The proof is completed using the orthonormality relation (1.11) and Corollary
5.2. ∎

To conclude the section, we will now extend the above OSSS-type inequality to
more general functions, albeit with square-root of the revealement
probability. The corollary below was once again motivated by a similar result
in the discrete case, whose proof was shared with us by Hugo Vanneuville. Some
other consequences of the above inequality can be found in the first arxiv
version of the article.

######  Corollary 5.4.

Consider a measurable and square-integrable function
$f:{\mathbf{N}}\to{\mathbb{R}}$ and assume that $f$ is determined by a
randomized stopping set $Z$ verifying (5.1). Then,

$\operatorname{{\mathbb{V}ar}}[f(\eta)]\leq{{}3}\sqrt{\delta(Z)}\int_{{\mathbb{X}}}\mathbb{E}[|D_{x}f(\eta)|^{2}]\lambda(\mathrm{d}x).$

Deriving the above corollary with $\delta(Z)$ instead of $\sqrt{\delta(Z)}$
remains a challenge and would give a $L^{2}$ version of OSSS inequality with
randomized stopping sets instead of randomized CTDTs. In view of Remark 3.4
and being an $L^{2}$ version, this would significantly enlarge the scope of
applications of the OSSS inequality.

###### Proof.

We can assume $\delta(Z)\in(0,1)$. Using (1.11) — (1.13) and Corollary 5.3, we
deduce that that, for all $m\geq 1$,

$\displaystyle\int_{{\mathbb{X}}}\mathbb{E}[|D_{x_{1}}f(\eta)|^{2}]\lambda(\mathrm{d}x_{1})=\sum_{k=1}^{\infty}\int_{{\mathbb{X}}^{k}}\frac{1}{(k-1)!}\mathbb{E}[D^{k}_{x_{1},\ldots,x_{k}}f(\eta)]^{2}\lambda(\mathrm{d}x_{1})\lambda(\mathrm{d}x_{2})\ldots\lambda(\mathrm{d}x_{k})$
$\displaystyle\geq
m\sum_{k=m}^{\infty}\int_{{\mathbb{X}}^{k}}\frac{1}{k!}\mathbb{E}[D^{k}_{x_{1},\ldots,x_{k}}f(\eta)]^{2}\lambda(\mathrm{d}x_{1})\lambda(\mathrm{d}x_{2})\ldots\lambda(\mathrm{d}x_{k})$
$\displaystyle=m\left(\operatorname{{\mathbb{V}ar}}[f(\eta)]-\sum_{k=1}^{m-1}\int_{{\mathbb{X}}^{k}}\frac{1}{k!}\mathbb{E}[D^{k}_{x_{1},\ldots,x_{k}}f(\eta)]^{2}\lambda(\mathrm{d}x_{1})\lambda(\mathrm{d}x_{2})\ldots\lambda(\mathrm{d}x_{k})\right)$
$\displaystyle\geq
m\left(\operatorname{{\mathbb{V}ar}}[f(\eta)]-\delta(Z)\sum_{k=1}^{m-1}k\operatorname{{\mathbb{V}ar}}[f(\eta)]\right)$
$\displaystyle\geq
m\operatorname{{\mathbb{V}ar}}[f(\eta)]\left(1-\frac{m^{2}\delta(Z)}{2}\right).$

Selecting $m=\lceil\delta(Z)^{-1}\rceil$ and exploiting the usual Poincaré
inequality yields the bound

$\operatorname{{\mathbb{V}ar}}[f(\eta)]\leq
2\min\left\\{\frac{1}{2}\,;\,\frac{\sqrt{\delta(Z)}}{\mathbf{1}-\sqrt{\delta(Z)}}\right\\}\int_{{\mathbb{X}}}\mathbb{E}[|D_{x}f(\eta)|^{2}]\lambda(\mathrm{d}x),$

and the conclusion follows from elementary considerations. ∎

###  6 Quantitative noise sensitivity

As indicated before, Corollary 5.3 has direct applications to noise
sensitivity, that one can use to derive further results on exceptional times
and bounds on critical windows. We will develop these themes in this section
and the next. In order to formally define the notion of noise sensitivity, we
need to introduce a collection of resampling procedures for the Poisson point
process $\eta$, that can then be used to define the Ornstein-Uhlenbeck
semigroup.

####  6.1 The Ornstein-Uhlenbeck semigroup

For every $t\geq 0$ we define $\eta^{t}$ to be the Poisson process with
intensity measure $\lambda$ obtained by independently deleting each point in
the support of $\eta$ with probability $1-e^{-t}$, and then adding an
independent Poisson process with intensity measure $(1-e^{-t})\,\lambda$. For
$f\colon{\mathbf{N}}\to{\mathbb{R}}$ such that $\mathbb{E}[|f(\eta)|]<\infty$,
define the operator $T_{t}$ as

$T_{t}f(\eta):=\mathbb{E}[f(\eta^{t})\mid\eta].$ (6.1)

Setting $T_{\infty}F:=\mathbb{E}[f(\eta)]$, one sees immediately that the
operators $P_{s}:=T_{-\log s}$, $s\geq 0$, coincide with those defined in [49,
Section 20.1]. Now assume that $f\colon{\mathbf{N}}\to{\mathbb{R}}$ is such
that $\mathbb{E}[f(\eta)^{2}]<\infty$ and that $f$ admits the chaotic
representation (1.10). In this case, according to Mehler’s formula (see [48,
formula (3.13)] or [47, formula (80)]) one has that, for each $t\geq 0$,

$\displaystyle
T_{t}f(\eta)=\mathbb{E}[f(\eta^{t})\mid\eta]=\sum_{k=0}^{\infty}e^{-kt}I_{k}(u_{k}),$
(6.2)

in such a way that the family of operators $\\{T_{t}:t\geq 0\\}$ (restricted
to $L^{2}(\mathbb{P})$) coincides with the classical Ornstein-Uhlenbeck
semigroup associated with $\eta$; see e.g. [47, Section 7] for a full
discussion.

######  Remark 6.1 (Markov process representation).

In the sections to follow, we will sometimes need to realise the resampled
processes $\\{\eta^{t}:t\geq 0\\}$ as a Markov process with values in
${\mathbf{N}}$. To do so, we recall from [47, Proposition 4 and Section 7]
that the infinitesimal generator $L$ of the semigroup $\\{T_{t}:t\geq 0\\}$ is
explicitly given as

$\displaystyle
Lf(\eta):=\int(f(\eta-\delta_{x})-f(\eta))\,\eta(dx)-\int(f(\eta+\delta_{x})-f(\eta))\,\lambda(dx)$

for all $f:{\bf N}\to{\mathbb{R}}$ verifying suitable integrability
assumptions. This is the generator of a free birth and death process on
${\mathbf{N}}$, with $\mathbb{P}(\eta\in\cdot)$ as its stationary measure. If
$\lambda$ is finite, then it is straightforward to construct a Markov process
$\\{\tilde{\eta}^{t}:t\geq 0\\}$ with generator $L$. Indeed, start with some
arbitrary initial configuration $\mu\in{\mathbf{N}}$ and attach independent
unit rate exponential life times to each point of $\mu$ (multiplicities have
to be taken into account). At the end of its lifetime, the point is removed.
Independently, new points are born with intensity $\lambda({\mathbb{X}})$,
distributed according to the normalized measure $\lambda$, and having
independent exponential life times as well. The arising Markov process
$\\{\tilde{\eta}^{t}:t\geq 0\\}$ is right-continuous and has left-hand limits
(càdlàg) with respect to the discrete topology. If
$\lambda({\mathbb{X}})=\infty$ we can partition ${\mathbb{X}}$ into sets of
finite $\lambda$-measure and paste together independent birth and death
processes. This procedure yields eventually a homogeneous Markov process
$\\{\tilde{\eta}^{t}:t\geq 0\\}$ that has càdlàg paths with respect to the
topology of weak convergence of point measures; we refer the reader to [64,
79] for more details. What is of importance for us is that, in the case
$\tilde{\eta}^{0}=\eta$, one has that
$\mathbb{E}[F(\tilde{\eta}^{t})\mid\tilde{\eta}^{0}]=\mathbb{E}[F(\tilde{\eta}^{t})\mid\eta]=T_{t}f(\eta)$,
as one can verify by a direct computation. From now on, we will refer to the
formula $T_{t}f(\eta)=\mathbb{E}[F(\tilde{\eta}^{t})\mid\eta]$, $t\geq 0$, as
the Markov process representation  of the Ornstein-Uhlenbeck semigroup. When
adopting the Markov process representation of $\\{T_{t}\\}$ we will write
$\tilde{\eta}^{t}=\eta^{t}$, by a slight abuse of notation.

####  6.2 Noise sensitivity

With the above notation at hand, we will now present the central definition of
the section.

######  Definition 6.1.

Let $f_{n}:{\mathbf{N}}\to{\mathbb{R}},\,n\geq 1$ be a sequence of measurable
mappings such that $\mathbb{E}[f_{n}(\eta)^{2}]<\infty$, for each $n$. The
sequence $\\{f_{n}\\}$ is said to be noise sensitive if, for every $t>0$,

$\mathbb{E}[f_{n}(\eta)f_{n}(\eta^{t})]-\mathbb{E}[f_{n}(\eta)]^{2}\to 0,\quad
n\to\infty.$

In order to detect noise sensitivity, it is often useful to exploit the fact,
if $\mathbb{E}[f(\eta)^{2}]<\infty$ and $f$ admits the chaos expansion (1.10),
then (6.2) and (1.11) imply that

$\mathbb{E}[f(\eta)f(\eta^{t})]=\sum_{k=1}^{\infty}e^{-kt}\mathbb{E}[I_{k}(u_{k})^{2}]{{}+\mathbb{E}[f(\eta)]^{2}}.$
(6.3)

Relation (6.3) is the pivotal element in the proof of the next statement.

######  Proposition 6.2.

Let $f_{n}:{\mathbf{N}}\to{\mathbb{R}}$, $n\geq 1$, be a sequence of
measurable mappings such that

$\sup_{n}\mathbb{E}[f_{n}(\eta)^{2}]:=C<\infty,$ (6.4)

and denote by $u^{(n)}_{k}$ the $k$th kernel in the chaotic expansion (1.10)
of $f_{n}(\eta)$.

  1. 1.

The sequence $\\{f_{n}:n\geq 1\\}$ is noise sensitive if and only if

$\lim_{n\to\infty}\mathbb{E}\big{[}I_{k}\big{(}u^{(n)}_{k}\big{)}^{2}\big{]}=0,\quad\,k\in{\mathbb{N}}.$
(6.5)

  2. 2.

For every nonnegative sequence $\\{t_{n}:n\geq 1\\}$, the following double
implication holds:

$\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{t_{n}})]\to
0,\,\,\mbox{as $n\to\infty$,}$ (6.6)

if and only if

$\displaystyle\mathbb{E}[f_{n}(\eta^{t_{n}})\mid\eta]-\mathbb{E}[f_{n}(\eta)]\overset{L^{2}(\mathbb{P})}{\longrightarrow}0,\,\,\mbox{as
$n\to\infty$}.$ (6.7)

###### Proof.

The fact that noise sensitivity implies (6.5) is a direct consequence of the
relation
$\mathbb{E}[f_{n}(\eta)f_{n}(\eta^{t})]-\mathbb{E}[f_{n}(\eta)]^{2}\geq
e^{-kt}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]$, which follows in turn from (6.3).
On the other hand, if (6.5) is in order one can use again (6.3) together with
the bound
$\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]\leq\mathbb{E}[f_{n}(\eta)^{2}]\leq C$
(valid for all $k,n$), and infer noise sensitivity by dominated convergence.
This proves Part 1. Part 2 is deduced from (6.4) and from the two relations

$\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{t_{n}})]=\sum_{k=1}^{\infty}e^{-kt_{n}}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]\geq\sum_{k=1}^{\infty}e^{-2kt_{n}}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]=\operatorname{{\mathbb{V}ar}}[\mathbb{E}[f_{n}(\eta^{t_{n}})\mid\eta],$

and

$\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{t_{n}})]=\mathbb{E}\Big{[}\big{(}f_{n}(\eta)-\mathbb{E}[f_{n}(\eta)]\big{)}\big{(}\mathbb{E}[f_{n}(\eta^{t_{n}})\mid\eta]-\mathbb{E}[f_{n}(\eta)]\big{)}\Big{]}.$

∎

Combining Part 1 of Proposition 6.2 with Corollary 5.3, we deduce the
following criterion for noise sensitivity.

######  Proposition 6.3.

Let $f_{n}:{\mathbf{N}}\to{\mathbb{R}}$, $n\geq 1$, be a sequence of
measurable mappings satisfying the assumptions of Proposition 6.2. Assume that
there exist randomized stopping sets $Z_{n}$, $n\geq 1$, such that, for every
$n$, $Z_{n}$ verifies (5.1) and determines $f_{n}$, and moreover

$\delta_{n}:=\delta(Z_{n}):=\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in
Z_{n})\longrightarrow 0,\quad\mbox{as $n\to\infty$}.$

Then, $\\{f_{n}:n\geq 1\\}$ is noise sensitive.

One can actually prove a more quantitative version of the previous result,
that will be very useful in the forthcoming sections. Indeed, using (6.3) and
Corollary 5.3, one derives the estimate

$\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{t})]\leq{{}C}\,\delta_{n}\frac{e^{-t}}{(1-e^{-t})^{2}},$
(6.8)

from which we deduce that

$\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{t_{n}})]\to
0,\,\,\mbox{as $n\to\infty$.}$ (6.9)

for any nonnegative bounded sequence $\\{t_{n}\\}$ such that
$\delta_{n}=o((1-e^{-t_{n}})^{2})$, as $n\to\infty$.

####  6.3 Noise stability

We now define noise stability, and then prove a statement containing a
criterion for it expressed in terms of chaos expansion (analogous to [29,
Proposition 4.3]), as well as a quantitative noise stability estimate similar
to [29, Proposition 6.1.2].

######  Definition 6.1.

Let $f_{n}:{\mathbf{N}}\to\\{0,1\\}$ be a sequence of measurable mappings. The
sequence $\\{f_{n}\\}$ is said to be noise stable if, for every $t>0$,

$\lim_{t\to 0}\lim_{n\to\infty}\mathbb{P}[f_{n}(\eta)\neq f_{n}(\eta^{t})]=0,$

where $\eta^{t}$ has been defined in Section 6.1.

We recall that, if a sequence of mappings $f_{n}$, $n\geq 1$, takes values in
a bounded set, then the random variables $f_{n}(\eta)$ admit a chaos
decomposition: as before, we will denote by $u_{k}^{(n)}$ the $k$th kernel in
the chaotic decomposition (1.10) of $f_{n}(\eta)$. The following statement
contains the announced criterion for noise stability, as well as an extension
to mappings with values in $\\{-1,1\\}$.

######  Proposition 6.2.

  * (a)

Let $f_{n}:{\mathbf{N}}\to\\{0,1\\}$ be a sequence of measurable mappings.
Then, the sequence $\\{f_{n}\\}$ is noise stable if and only if, for every
$\epsilon>0$, there exists $m$ such that for all $n$,

$\sum_{k=m}^{\infty}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]<\epsilon.$ (6.10)

  * (b)

Let $f_{n}:{\mathbf{N}}\to\\{-1,1\\}$ be a sequence of measurable mappings. If
$\\{t_{n}:n\geq 1\\}\subset\mathbb{R}_{+}$ is a sequence such that
$t_{n}\int\mathbb{E}[|D_{x}f_{n}(\eta)|^{2}]\lambda(\mathrm{d}x)\to 0$ as
$n\to\infty$, then

$\lim_{n\to\infty}\mathbb{P}(f_{n}(\eta)\neq f_{n}(\eta^{t_{n}}))=0.$

###### Proof.

Using the covariance formula (6.3) one infers that

$\displaystyle\mathbb{P}[f_{n}(\eta)\neq f_{n}(\eta^{t})]$
$\displaystyle=\mathbb{E}[f_{n}(\eta)(1-f_{n}(\eta^{t}))]+\mathbb{E}[(1-f_{n}(\eta))f_{n}(\eta^{t})]$
$\displaystyle=2(\mathbb{E}[f_{n}(\eta)^{2}]-\mathbb{E}[f_{n}(\eta)f_{n}(\eta^{t})])$
$\displaystyle=2\sum_{k=1}^{\infty}(1-e^{-kt})\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}],$

which yields immediately Part (a). To prove Part (b), we first observe that,
since each $f_{n}$ takes values in $\\{-1,1\\}$, then

$\sum_{k=0}^{\infty}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]=1,$

that is: for every $n$, the weights
$\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}],\,\,k\geq 0$, constitute a probability
distribution on $\\{0,1,\ldots\\}$. Combining the covariance formula (6.3)
with Jensen’s inequality, we deduce that, for each $t\geq 0$,

$\mathbb{E}[f_{n}(\eta)f_{n}(\eta^{t})]=\sum_{k=0}^{\infty}e^{-kt}\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]\geq\exp\\{-t\sum_{k=0}^{\infty}k\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]\\}.$

Since

$\sum_{k=0}^{\infty}k\mathbb{E}[I_{k}(u^{(n)}_{k})^{2}]=\int\mathbb{E}[|D_{x}f_{n}|^{2}]\lambda(\mathrm{d}x),$

we eventually obtain the lower bound

$\mathbb{E}[f_{n}(\eta)f_{n}(\eta^{t})]\geq\exp\left\\{-t\int\mathbb{E}[|D_{x}f_{n}|^{2}]\lambda(\mathrm{d}x)\right\\},$

from which the desired conclusion follows at once. ∎

From Propositions 6.2 and 6.2 and covariance formula (6.3), it is easy to see
that if $f_{n}$ is noise sensitive and noise stable then $f_{n}$ is
asymptotically degenerate i.e., $\operatorname{{\mathbb{V}ar}}[f_{n}]\to 0$ as
$n\to\infty$.

###  7 Exceptional times and critical windows

Throughout this section, we adopt the Markov process representation of the
Ornstein-Uhlenbeck semigroup $\\{T_{t}\\}$, as put forward in Remark 6.1.

We say that a sequence of Boolean functions $\\{f_{n}:n\geq 1\\}$,
$f_{n}:{\mathbf{N}}\to\\{0,1\\}$ is non-degenerate if, for some
$\gamma_{0}\in(0,1)$,

$\gamma_{0}\leq\mathbb{E}[f_{n}(\eta)]\leq
1-\gamma_{0},\quad\,n\in{\mathbb{N}}.$ (7.1)

We say that a function $f\colon{\mathbf{N}}\to{\mathbb{R}}$ is jump regular
(with respect to $\\{\eta^{t}:t\geq 0\\}$) if the mapping $t\mapsto
f(\eta^{t})$ is almost surely piecewise constant, that is, on any compact
interval such a mapping equals a finite linear combination of indicators of
bounded intervals of the form $[a,b)$. We will abuse notation and denote the
left-hand limit of $t\mapsto f(\eta^{t})$ at $t>0$ by $f(\eta^{t-})$ even
though $\eta^{t-}$ may be not well defined. Observe that if
$\lambda({\mathbb{X}})<\infty$ and $f\colon{\mathbf{N}}\to\\{0,1\\}$, then
$f(\eta^{t})$ is almost surely piecewise constant because of the right-
continuity of $\eta^{t}$ with respect to the discrete topology and this is
sufficient to verify jump-regularity in many applications. Given a sequence of
Boolean jump regular functions $f_{n}\colon{\mathbf{N}}\to\\{0,1\\}$,
$n\in{\mathbb{N}}$, we define the sets of exceptional times as

$S_{n}:=\\{t>0:f_{n}(\eta^{t})\neq f_{n}(\eta^{t-})\\},\quad
n\in{\mathbb{N}}.$

One naturally expects that, if the sequence $\\{f_{n}:n\geq 1\\}$ is noise
sensitive, then $|S_{n}|\to\infty$ in some sense. Such an intuition is
formally confirmed in the next statement, where we show that a non-degenerate
and noise sensitive Boolean function has an infinite set of exceptional times
even in small time intervals. This was proved in the specific case of critical
percolation in [12, Lemma 5.1], but the proof can be adapted in more
generality (see [29, Theorem 1.23]). The proof of the next result follows
closely the strategy developed in the aforementioned references.

######  Theorem 7.1 (Existence of exceptional times).

Let $f_{n}\colon{\mathbf{N}}\to\\{0,1\\}$, $n\in{\mathbb{N}}$, be a sequence
of jump regular and non-degenerate Boolean functions. Further, assume that
there exists a sequence $c_{n}\in(0,1)$, $n\geq 1$, such that, for every
$\beta\in(0,1)$, the sequence $b_{n}=\beta\,c_{n}$, $n\geq 1$, is such that

$\displaystyle\operatorname{{\mathbb{C}ov}}[f_{n}(\eta),f_{n}(\eta^{b_{n}})]\to
0,\,\,\mbox{as $n\to\infty$.}$ (7.2)

Then, $|S_{n}\cap[0,c_{n}]|\overset{\mathbb{P}}{\longrightarrow}\infty$.

###### Proof.

We claim that it suffices to show that for all $0\leq a<b\leq 1$,

$\lim_{n\to\infty}\mathbb{P}(S_{n}\cap[ac_{n},bc_{n}]=\emptyset)=0.$ (7.3)

To see this, assume (7.3) is true, and fix an arbitrary integer $M\geq 1$ and
$\alpha>0$. Partitioning $[0,{{}c_{n}}]$ into intervals of length $1/(2M)$, we
can choose $N$ large enough in order to have that, for all $n\geq N$,

$\mathbb{P}\left(S_{n}\cap\left[0,\frac{c_{n}}{2M}\right]=\emptyset\right)\leq\alpha/2.$

Set
$X_{n}:=\sum_{l=1}^{2M}{\mathbf{1}}\\{S_{n}\cap[\frac{(l-1)c_{n}}{2M},\frac{lc_{n}}{2M}]=\emptyset\\}$
and observe that $\mathbb{E}[X_{n}]\leq\alpha M$ by the homogeneous Markov
property of $\eta^{t}$. Using Markov’s inequality,

$\mathbb{P}({{}|S_{n}\cap[0,c_{n}]|}\leq M)\leq\mathbb{P}(X_{n}\geq
M)\leq\alpha.$

As $M,\alpha$ are arbitrary, the previous estimate completes the proof of the
theorem assuming (7.3). We will now prove (7.3) for arbitrary $0\leq a<b\leq
1$ that we fix until the end of the proof. For $\epsilon\in(0,1)$ and
$n\in{\mathbb{N}}$, we set

$W_{n,\epsilon}=\\{\mu\in{\mathbf{N}}:\mathbb{P}(f_{n}(\eta^{\epsilon})=1\mid\eta=\mu)\in[0,\gamma_{0}{{}/2}]\cup[1-\gamma_{0}{{}/2},1]\\},$

where $\gamma_{0}$ is as in (7.1). Select an arbitrary $\gamma>0$, let
$k\in{\mathbb{N}}$ and define ${{}b_{n}:=(b-a)c_{n}/k}$. By the non-degeneracy
condition and part 2 of Proposition 6.2, one can find a large
$n_{0}\in{\mathbb{N}}$ such that for all $n\geq n_{0}$, $\mathbb{P}(\eta\in
W_{n,b_{n}})\leq\gamma_{0}\gamma$; from now on, we consider that $n\geq
n_{0}$. Now take $t_{0},\ldots,t_{k}$ such that
$ac_{n}=t_{0}<t_{1}\cdots<t_{k}=bc_{n}$ and $t_{i}-t_{i-1}={{}b_{n}}$. For
each $i\in\\{1,\ldots,k\\}$, we have that

$\displaystyle\mathbb{P}(S_{n}\cap(t_{0},t_{i}]=\emptyset)$
$\displaystyle\leq\mathbb{P}\big{(}\eta^{t_{i-1}}\in
W_{n,{{}b_{n}}}\big{)}+\mathbb{P}\big{(}\eta^{t_{i-1}}\notin
W_{n,{{}b_{n}}},S_{n}\cap(t_{0},t_{i}]=\emptyset\big{)}$
$\displaystyle\leq\gamma_{0}\gamma+\mathbb{P}\big{(}S_{n}\cap(t_{0},t_{i-1}]=\emptyset,\eta^{t_{i-1}}\notin
W_{n,{{}b_{n}}},f_{n}(\eta^{t_{i-1}})=f_{n}(\eta^{t_{i}})\big{)},$

where we have used that $f_{n}$ is jump regular. Using the Markov property of
$\eta^{t}$, we obtain that

$\displaystyle\mathbb{P}$ $\displaystyle(S_{n}\cap(t_{0},t_{i}]=\emptyset)$
$\displaystyle\leq\gamma_{0}\gamma+\mathbb{E}\big{[}{\mathbf{1}}\\{S_{n}\cap(t_{0},t_{i-1}]=\emptyset,\eta^{t_{i-1}}\notin
W_{n,{{}b_{n}}}\\}\mathbb{P}(f_{n}(\eta^{t_{i}})=f_{n}(\eta^{t_{i-1}})|\eta^{t_{i-1}})\big{]}.$

By definition of $W_{n,{{}b_{n}}}$ (and since $f_{n}$ is Boolean) we have
that, if $\eta^{t_{i-1}}\notin W_{n,{{}b_{n}}}$,

$\displaystyle\mathbb{P}(f_{n}(\eta^{t_{i}})=f_{n}(\eta^{t_{i-1}})|\eta^{t_{i-1}})\leq
1-\gamma_{0}{{}/2}.$

This yields the bound

$\displaystyle\mathbb{P}(S_{n}\cap(t_{0},t_{i}]=\emptyset)\leq\gamma_{0}\gamma+(1-\gamma_{0}{{}/2})\mathbb{P}(S_{n}\cap(t_{0},t_{i-1}]=\emptyset),$

and an induction argument allows one to infer that

$\displaystyle\mathbb{P}(S_{n}\cap(ac_{n},bc_{n}]=\emptyset)\leq\gamma_{0}\gamma\sum^{k}_{i=0}(1-\gamma_{0}{{}/2})^{i}+(1-\gamma_{0}/2)^{k}\leq\gamma+(1-\gamma_{0}{{}/2})^{k},$

where the second inequality follows from a standard calculation. Letting
$k\to\infty$, we obtain that, for all $n\geq n_{0}$,
$\mathbb{P}(S_{n}\cap(ac_{n},bc_{n}]=\emptyset)\leq\gamma$, and (7.3) is
proved. ∎

Combining Theorem 7.1 with (6.9), one deduces the following easily applicable
corollary.

######  Corollary 7.2.

Let $f_{n}\colon{\mathbf{N}}\to\\{0,1\\},n\geq 1$, be a sequence of jump
regular and non-degenerate mappings, and assume that there exist randomized
stopping sets $Z_{n}$, $n\geq 1$, such that $Z_{n}$ determines $f_{n}(\eta)$
and $Z_{n}$ verifies (5.1) for every $n$, and moreover

$\displaystyle\delta_{n}:=\delta(Z_{n}):=\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in
Z_{n})\longrightarrow 0,\quad\,\mbox{as $n\to\infty$}.$

Then, for any sequence $c_{n}\in(0,1)$ such that
${{}\delta_{n}}=o(c_{n}^{2})$, we have that
$|S_{n}\cap[0,c_{n}]|\overset{\mathbb{P}}{\longrightarrow}\infty$.

Following the ideas in the proof of [30, Theorem 1.10], we use the above
result to bound the critical window for phase-transition of a monotonic
Boolean function. To smoothly formulate the result it is convenient to
introduce for any $\sigma$-finite measure $\nu$ on ${\mathbb{X}}$ a Poisson
process $\eta_{\nu}$ with that intensity measure. We shall use this notation
only for measures $\nu$ that are multiples of the intensity measure $\lambda$.

######  Theorem 7.3 (Bounds on critical window).

Let $f_{n}\colon{\mathbf{N}}\to\\{0,1\\},n\geq 1$, be a sequence of
increasing, jump regular and non-degenerate mappings. Assume that there exist
randomized stopping sets $Z_{n}$, $n\geq 1$, such that $Z_{n}$ determines
$f_{n}(\eta)$ and $Z_{n}$ verifies (5.1) for every $n$, and moreover

$\displaystyle\delta_{n}:=\delta(Z_{n}):=\sup_{x\in{\mathbb{X}}}\mathbb{P}(x\in
Z_{n})\to 0,\quad\mbox{as $n\to\infty$}.$ (7.4)

Then, for any sequence $c_{n}{{}\in(0,1)}$ such that
${{}\delta_{n}}=o(c_{n}^{2})$, we have that
$\mathbb{E}[f_{n}(\eta_{(1+c_{n})\lambda})]\to 1$ and
$\mathbb{E}[f_{n}(\eta_{(1-c_{n})\lambda})]\to 0$, as $n\to\infty$.

We remark that the proof only uses the fact that
$|S_{n}\cap[0,c_{n}]|\overset{\mathbb{P}}{\longrightarrow}\infty$ where
$S_{n}$ is the set of exceptional times.

###### Proof.

Firstly, from Corollary 7.2, we have that

$\displaystyle\mathbb{P}(f_{n}(\eta^{t})=1\,\mbox{for some
$t\in[0,c_{n}]$})\to 1\,\mbox{as $n\to\infty$}.$ (7.5)

For $t\geq 0$, let $\eta^{\prime}_{t}$ be the Poisson process of points born
before time $t$. This process is independent of $\eta$ and has intensity
measure $t\lambda$. Then $\zeta_{t}:=\eta+\eta^{\prime}_{t}$ is a Poisson
process with intensity measure $(1+t)\lambda$. By construction of $\eta^{t}$
and $\zeta_{t}$, we have $\eta^{t}\leq\zeta_{t}\leq\zeta_{c_{n}}$ whenever
$t\leq c_{n}$. By the monotonicity of $f_{n}$ and (7.5) this implies
$\mathbb{E}[f_{n}(\zeta_{c_{n}})]\to 1$ as $n\to\infty$ and hence the first
assertion. Again, from Corollary 7.2, we have that

$\displaystyle\mathbb{P}(f_{n}(\eta^{t})=0\,\mbox{for some
$t\in[0,c_{n}]$})\to 1\,\mbox{as $n\to\infty$}.$ (7.6)

For $t\geq 0$, let $\zeta^{\prime}_{t}$ be the point process of points from
$\eta$ (counting multiplicities) which are still alive at time $t$. Since the
lifetimes of points are exponential, $\zeta^{\prime}_{t}$ is a Poisson process
with intensity measure $e^{-t}\lambda$ and also trivially by construction
$\zeta^{\prime}_{c_{n}}\leq\zeta^{\prime}_{t}\leq\eta^{t}$ whenever $t\leq
c_{n}$. Thus, by the monotonicity of $f_{n}$ and (7.6), we obtain that
$\mathbb{E}[f_{n}(\eta_{e^{-c_{n}}\lambda})]=\mathbb{E}[f_{n}(\zeta^{\prime}_{c_{n}})]\to
0$ as $n\to\infty$. Now, the second assertion follows by first observing that
$1-t\leq e^{-t}$ for $t\geq 0$ and then using the monotonicity of $f_{n}$
along with the thinning property of the Poisson process. ∎

We now prove a strengthening of the above result when the randomized stopping
sets $Z_{n}$ above can be attained by a CTDT as in Theorem 3.2. This proof
proceeds similar to the Friedgut-Kalai sharp threshold theorem (see [29,
Theorem 3.5]). This refinement was pointed out to us by Stephen Muirhead.

######  Theorem 7.4 (Bounds on critical window).

Let $f_{n}\colon{\mathbf{N}}\to\\{0,1\\},n\geq 1$, be as in Theorem 7.3.
Assume for each $n\in{\mathbb{N}}$ that $f_{n}$ is determined by a randomized
stopping set $Z_{n}$, satisfying the assumptions of Theorem 3.2. Assume that
(7.4) holds. Then, for any sequence $c_{n}\in(0,1)$ such that
${{}\delta_{n}}=o(c_{n})$, we have that
$\mathbb{E}[f_{n}(\eta_{(1+c_{n})\lambda})]\to 1$ and
$\mathbb{E}[f_{n}(\eta_{(1-c_{n})\lambda})]\to 0$, as $n\to\infty$.

We shall actually prove a stronger quantitative version than the one stated.

###### Proof.

Set $p_{n}(1+t):=\mathbb{E}[f_{n}(\eta_{(1+t)\lambda})]$ for
$t\in[-1,\infty)$. Let $\epsilon>0$. We will show that, for $n$ large enough,

$\mbox{if }\,\,p_{n}(1)\geq\gamma_{0}\,\mbox{ then }\,p_{n}(1+t_{n})\geq
1-\epsilon\,\mbox{ for
}\,t_{n}=\frac{-\delta_{n}\log(\gamma_{0})}{\epsilon+\delta_{n}\log(\gamma_{0})}.$
(7.7)

This suffices to show that $\mathbb{E}[f_{n}(\eta_{(1+c_{n})\lambda})]\to 1$
for any sequence $c_{n}\in(0,1)$ such that ${{}\delta_{n}}=o(c_{n})$. Applying
the same argument to $1-p_{n}(1-t)$ will yield the second claim in the
theorem. For given $\epsilon>0$ let $n$ be large enough such that $t_{n}\geq
0$ in (7.7). This is possible because $\delta_{n}\to 0$ as $n\to\infty$. Using
the Russo-Margulis formula for Poisson functionals (see [49, Theorem 19.4]),
monotonicity of $f_{n}$ and the Poisson-OSSS inequality (Theorem 3.2), we
derive that for $t\geq 0$,

$\displaystyle\frac{\mathrm{d}p_{n}(1+t)}{\mathrm{d}t}$
$\displaystyle=\int_{{\mathbb{X}}}\mathbb{E}[D_{x}f_{n}(\eta_{(1+t)\lambda})]\lambda(\mathrm{d}x)$
$\displaystyle=\int_{{\mathbb{X}}}\mathbb{E}[|D_{x}f_{n}(\eta_{(1+t)\lambda})|]\lambda(\mathrm{d}x)$
$\displaystyle\geq\frac{1}{(1+t)\delta_{n}}\operatorname{{\mathbb{V}ar}}(f_{n}(\eta_{(1+t)\lambda}))$
$\displaystyle=\frac{1}{(1+t)\delta_{n}}p_{n}(1+t)(1-p_{n}(1+t)).$

Suppose that $p_{n}(1)\geq\gamma_{0}$ and $p_{n}(1+t_{n})<1-\epsilon$ for
$t_{n}$ as defined in (7.7). Since $f_{n}$ is monotonic, we have that
$p_{n}(1+t)<1-\epsilon$ for all $t\leq t_{n}$ and hence using this in the
above differential inequality, we obtain that for all $t\in[0,t_{n}]$,

$\frac{\mathrm{d}\log
p_{n}(1+t)}{\mathrm{d}t}\geq\frac{\epsilon}{(1+t_{n})\delta_{n}}.$

Exploiting the fact that $p_{n}(1+t)\geq p_{n}(1)\geq\gamma_{0}$, one infers
that

$\log
p_{n}(1+t_{n})\geq\log\gamma_{0}+\frac{\epsilon\,t_{n}}{(1+t_{n})\delta_{n}}=0,$

which implies $p_{n}(1+t_{n})\geq 1$ and therefore a contradiction. So, we
have that $p_{n}(1+t_{n})\geq 1-\epsilon$ as required by (7.7). This completes
the proof of (7.7) and hence the theorem as well. ∎

##  Part III Applications to Continuum percolation models

In this part, we fix $d\geq 2,k\geq 1$ and $r>0$. Let $\eta=\\{X_{i}:i\geq
1\\}$ be the stationary Poisson point process in ${\mathbb{R}}^{d}$ of
intensity $\gamma>0$ (identified as usual with its support). We write
${\mathcal{K}}_{r}$ to indicate the space of non-empty compact subsets of
$B_{r}(0)$ equipped with the Hausdorff distance and
${\mathcal{K}}^{b}_{r}:=\\{B_{s}(0):s\in[0,r]\\}$ denote the subset of
${\mathcal{K}}$ consisting of balls centred at the origin. Let $\mathbb{Q}$ be
a probability measure on compact sets of ${\mathbb{R}}^{d}$ such that it
satisfies

$\mathbb{Q}({\mathcal{K}}_{r})=1\,\,\mbox{and}\,\,\mathbb{Q}\\{K:B_{r_{0}}(0)\subset
K\\}>0,$ (8.0)

for two constants $r,r_{0}>0$. The two assumptions of compactly supported and
containing small balls ensure non-triviality of percolation phase transition
in our models. The former is a strong assumption and in the case of unbounded
grains, some of the results could change depending on the distribution of
grain sizes; see [4, 25] for results in the case of balls with unbounded
radii. In Section 10 alone, we shall work with unbounded balls and this
already indicates that the first assumption can be removed with some
additional work under suitable moment assumptions on the size of the grains.

###  8 $k$-Percolation in the Poisson Boolean model

We will now consider the $k$-percolation model. We denote the marked point
process by $\tilde{\eta}=\\{(X_{i},M_{i})\\}_{i\geq 1}$ where $M_{i},i\geq 1$
are i.i.d. compact sets (or also referred to as grains) distributed according
to $\mathbb{Q}$. We shall use symbol $M_{i}$’s for random grains and $K$ for
deterministic grains. The $k$-covered or $k$-occupied region of the Poisson
Boolean model on $\tilde{\eta}$ is defined as

$\mathcal{O}(\gamma):=\mathcal{O}_{k}(\tilde{\eta})=\bigcup_{1\leq
i_{1}<\ldots<i_{k}<\infty}(X_{i_{1}}+M_{i_{1}})\cap\ldots\cap(X_{i_{k}}+M_{i_{k}})$
(8.1)

Apart from being a natural extension of the usual continuum percolation,
$k$-percolation can also be seen as percolation of $(k-1)$-faces in the random
Cěch complex on $\eta$ with i.i.d. grains distributed according to
$\mathbb{Q}$ (see [13, Remark 3.8]).

We have suppressed the dependence on $k,\mathbb{Q}$ in the above definition as
$\mathbb{Q}$ and $k$ will remain fixed but $\gamma$ will vary. If $k=1$, this
is the classical Boolean model. Study of continuum percolation was initiated
by Gilbert [32] where he considered the Poisson Boolean model with fixed radii
balls and much later, it was extended to random radii with unbounded support
by Hall [37]. We refer the reader to the monograph of Meester and Roy [51] as
well as that of Bollobas and Riordan [15] for detailed accounts on continuum
percolation.

We now define the percolation events and the corresponding probabilities. For
connected subsets $A,B,R\subset{\mathbb{R}}^{d}$ such that $A\cup B\subset R$,
we define

$\displaystyle\\{A\stackrel{{\scriptstyle R}}{{\leftrightarrow}}B\\}$
$\displaystyle:=\\{\mbox{there exists a path in $\mathcal{O}(\gamma)\cap R$
from $x$ to $y$ for some $x\in A,y\in B$}\\},$
$\displaystyle\\{A\leftrightarrow B\\}$
$\displaystyle:=\\{A\stackrel{{\scriptstyle{\mathbb{R}}^{d}}}{{\leftrightarrow}}B\\},$
$\displaystyle\\{0\leftrightarrow\infty\\}$ $\displaystyle:=\\{\mbox{there is
an unbounded path from $0$ in $\mathcal{O}(\gamma)$}\\},$
$\displaystyle\theta_{s}(\gamma)$
$\displaystyle:=\mathbb{P}(0\leftrightarrow\partial B_{s}(0)),s>0,$
$\displaystyle\theta(\gamma)$
$\displaystyle:=\mathbb{P}(0\leftrightarrow\infty),$ $\displaystyle
Arm_{s,t}(\gamma)$ $\displaystyle:=\\{B^{\infty}_{s}(0)\leftrightarrow\partial
B^{\infty}_{t}(0)\\},\,\,0<s<t,$ $\displaystyle Cross_{s,t}(\gamma)$
$\displaystyle:=\\{\\{0\\}\times[0,t]^{d-1}\stackrel{{\scriptstyle[0,s]\times[0,t]^{d-1}}}{{\leftrightarrow}}\\{s\\}\times[0,t]^{d-1}\\},\,\,s,t>0,$
(8.2)

where in the fourth and fifth definitions, we have replaced the singleton set
$\\{0\\}$ by $0$ for convenience and $B^{\infty}_{s}(x)=x\oplus[-s,+s]^{d}$ is
the $\ell_{\infty}$-ball of side-length $2s$ at $x$ where $\oplus$ denotes
Minkowski sum of sets. $Arm_{s,t}(\gamma)$ is the usual one-arm event and
$Cross_{\kappa t,t}(\gamma)$ is the crossing event. We say that the origin
$k$-percolates if $0\leftrightarrow\infty$ holds and $\theta(\gamma)$ is the
percolation probability.

We now define the critical intensity for $k$-percolation. Since the event
$\\{0\leftrightarrow\partial B_{n}(0)\\}$ is decreasing in $n$, we have that

$\theta(\gamma)=\lim_{n\to\infty}\theta_{n}(\gamma).$

The critical intensity of the model is defined as

$\gamma_{c}:=\gamma_{c}(\mathbb{Q})=\inf\\{\gamma\geq 0:\theta(\gamma)>0\\}.$
(8.3)

The above definition is justified because $\theta(\gamma)$ is monotonically
increasing in $\gamma$. Further, let $C_{0}$ be the connected component
containing $0$ in $\mathcal{O}(\gamma)$ if $0\in\mathcal{O}(\gamma)$ else
$C_{0}=\emptyset$. We define two other critical intensities related to
percolation of $\mathcal{O}(\gamma)$ :

$\displaystyle\hat{\gamma}_{c}:=\sup\\{\gamma\geq
0:\mathbb{E}[|C_{0}|]<\infty\\},\tilde{\gamma}_{c}:=\inf\\{\gamma\geq
0:\inf_{s>0}\mathbb{P}(B_{s}(0)\leftrightarrow\partial B_{2s}(0))>0\\},$ (8.4)

where $|.|$ denotes the Lebesgue measure of a set. Again, the definitions are
justified by the monotonicity in $\gamma$ of the respective quantities. We
have that $\hat{\gamma}_{c}\leq\gamma_{c}$ (using the first equality in (8.5))
and that $\tilde{\gamma}_{c}\leq\gamma_{c}$ follows via a simple monotonicity
argument. While $\hat{\gamma}_{c}$ is a natural notion of critical intensity,
$\tilde{\gamma}_{c}$ is often very useful in initiating renormalization
arguments and was introduced in [34].

Our first main result is that the three critical intensities are equal.

######  Theorem 8.1 (Equality of critical intensities).

Let $\mathcal{O}(\gamma)$ be the $k$-covered region of the Poisson Boolean
model as defined in (8.1) with grain distribution $\mathbb{Q}$ satisfying
assumptions in (8.0). Then we have that
$\gamma_{c}=\hat{\gamma}_{c}=\tilde{\gamma}_{c}\in(0,\infty)$.

Similar to the Poisson Boolean model, one can associate various other critical
densities using box crossing events, diameter, number of grains in $C_{0}$
(see [51, Sections 3.4 and 3.5]). When $\mathbb{Q}$ is supported on
deterministic bounded balls, equality of some of these critical intensities
are shown in [51, Theorems 3.4 and 3.5] for $k=1$. In [25, Theorem 1.2], this
was extended to the case of unbounded balls with the radius distribution
having finite $5d-3$ moments. The above theorem for $k=1$ also follows
straightforwardly from the results of [80, Theorem 3.1]. Similar to [80,
Theorem 3.1], we prove an exponential decay bound for $\theta_{n}(\gamma)$ to
deduce equality of critical intensities. One of the advantages of our proof is
that it yields a mean-field lower bound in the super-critical regime also
easily.

######  Theorem 8.2 (Sharp threshold for $k$-percolation).

Let $\mathcal{O}(\gamma)$ be the $k$-covered region of the Poisson Boolean
model as defined in (8.1) with grain distribution $\mathbb{Q}$ satisfying
assumptions in (8.0). Then the critical intensity $\gamma_{c}$ defined in
(8.3) is non-degenerate (i.e., $\gamma_{c}\in(0,\infty)$) and the following
statements hold.

  1. (i)

For all $\gamma<\gamma_{c}$, there exists a constant
$\alpha(\gamma)\in(0,\infty)$ such that
$\theta_{s}(\gamma)\leq\exp\\{-\alpha(\gamma)s\\}$ for all $s>0$.

  2. (ii)

For any $b>\gamma_{c}$, there exists a a constant $\alpha(b)\in(0,\infty)$
such that for all $\gamma\in(\gamma_{c},b)$,
$\theta(\gamma)\geq\alpha(b)(\gamma-\gamma_{c})$.

The above theorem for $k=1$ was also proven in [80, Theorem 3.1] generalizing
the result of [51, Lemma 3.3] which was for the case of $\mathbb{Q}$ supported
on balls. Again, for the case of unbounded balls with finite $5d-3$ moments of
the radius distribution, part (ii) was shown to hold in [25, Theorem 1.2].
Further, if the radius distribution has finite exponential moments, part (i)
of the above theorem was shown in [25, Theorem 1.4]. It was also shown in [25,
Theorem 1.5] that radius distribution with slower decay of tails can exhibit a
different behaviour in the subcritical regime.

Traditionally, the proof of sharp phase transition in percolation models have
relied upon adaptation of Menshikov’s arguments [52, 53]. For example, see
Meester and Roy [51, Sections 3.4 and 3.5] for sharp phase transition in
subcritical Poisson Boolean models ($k=1$ in our $k$-percolation model). There
is also an independent proof by Aizenmann and Barsky [6]. Another simpler
proof that emerged in recent years is that of Duminil-Copin and Tassion [20].
This proof is by showing sharp phase transition with respect to a new critical
intensity which is defined by existence of a set containing the origin such
that the expected number of paths exiting the set is strictly bounded above by
$1$. This was adapted to the Poisson Boolean model by Ziesche [80]. Another
proof of sharp phase transition using randomized algorithms was pioneered in
[23] and also applied to continuum models in [24] and [25] via suitable
discretization. Our proof technique based on CTDTs was inspired by these works
and possibly enables a much easier execution of the approach initiated in [23]
for continuum percolation models. Also, observe that the critical intensities
$\gamma_{c}$ are increasing in $k$ and possibly even strictly increasing and
so Theorems 8.1 and 8.2 do not follow from the corresponding results for
$k=1$.

We postpone the proof of Theorem 8.2 to the end of the section and now show
how the proof of Theorem 8.1 follows from Theorem 8.2.

###### Proof of Theorem 8.1.

Observe that by Fubini’s theorem, we have from Theorem 8.2(i) for
$\gamma<\gamma_{c}$

$\mathbb{E}[|C_{0}|]=\int_{{\mathbb{R}}^{d}}\mathbb{P}(0\leftrightarrow
x)\mathrm{d}x\leq\int_{{\mathbb{R}}^{d}}\exp\\{-c_{\gamma}|x|\\}\mathrm{d}x<\infty.$
(8.5)

This with the trivial bound yields that $\hat{\gamma}_{c}=\gamma_{c}$.

For the second part, consider $s>10$ and $l_{s}\in{\mathbb{N}}$, such that
$x_{1},\ldots,x_{l_{s}}\in\partial B_{s}(0)$ with $\partial
B_{s}(0)\subset\cup_{i=1}^{l_{s}}B_{1}(x_{i})$. Note that $l_{s}$ can be
chosen such that $l_{s}\leq cs^{d-1}$ for some $c>0$ not depending on $s$. For
$t>0$, define $A_{t}(x):=\\{x\leftrightarrow\partial
B_{2t}(x)\\}\cap\\{\partial B_{2t}(x)\subset\mathcal{O}(\gamma)\\}$ i.e., $x$
is connected to the boundary of $\partial B_{2t}(x)$ and $\partial B_{2t}(x)$
is contained in a single component. Observe that $A_{t}(x)$ is an increasing
event for all $t>0$ and also by assumption (8.0), we have that
$\mathbb{P}(A_{t}(x))=\mathbb{P}(A_{t}(0))\geq\mathbb{P}(B_{2t}(0)\subset\mathcal{O}(\gamma))>0$
for all $t>0$. Now, using Markov’s inequality, isotropy of the Poisson point
process, monotonicity and positivity of $A_{1/2}(x_{1})$, Harris-FKG
inequality [49, Theorem 20.4] and the bound on $l_{s}$, we can derive that

$\displaystyle\mathbb{P}(B_{s}(0)\leftrightarrow\partial B_{2s}(0))$
$\displaystyle\leq\mathbb{P}(\cup_{i=1}^{l_{s}}\\{B_{1}(x_{i})\leftrightarrow\partial
B_{2s}(0)\\})\leq\sum_{i=1}^{l_{s}}\mathbb{P}(B_{1}(x_{i})\leftrightarrow\partial
B_{2s}(0))$ $\displaystyle\leq
l_{s}\mathbb{P}(B_{1}(x_{1})\leftrightarrow\partial B_{2s}(0))$
$\displaystyle\leq
l_{s}\mathbb{P}(A_{1/2}(x_{1}))^{-1}\mathbb{P}(\\{B_{1}(x_{1})\leftrightarrow\partial
B_{2s}(0)\\}\cap A_{1/2}(x_{1}))$ $\displaystyle\leq
l_{s}\mathbb{P}(A_{1/2}(0))^{-1}\mathbb{P}(x_{1}\leftrightarrow\partial
B_{2s}(0))\leq\mathbb{P}(A_{1/2}(0))^{-1}l_{s}\theta_{s}(\gamma)$
$\displaystyle\leq c\mathbb{P}(A_{1/2}(0))^{-1}s^{d-1}\theta_{s}(\gamma).$

Now using Theorem 8.2(i) again, we obtain that for all $\gamma<\gamma_{c}$

$\limsup_{s\to\infty}\mathbb{P}(B_{s}(0)\leftrightarrow\partial B_{2s}(0))\leq
c\mathbb{P}(A_{1/2}(0))^{-1}\lim_{s\to\infty}s^{d-1}\theta_{s}(\gamma)=0.$

Thus we have that $\gamma_{c}\leq\tilde{\gamma}_{c}$ and combined with the
trivial inequality in the other direction, this completes the proof. ∎

We now give a simple criterion for verifying noise sensitivity, existence of
infinite exceptional times as well as determining the critical window in the
above models.

######  Theorem 8.3 (Noise Sensitivity Criteria).

Let $\mathcal{O}(\gamma)$ be the $k$-covered region of the Poisson Boolean
model as defined in (8.1) with grain distribution $\mathbb{Q}$ satisfying
assumptions in (8.0). Let $\kappa>0$ be given. Let
$f_{n}:=f_{n}(\gamma)=\mathbf{1}\\{Cross_{\kappa n,n}(\gamma)\\}$ where
$Cross_{\kappa n,n}(\gamma)$ is the crossing event defined in (8.2). Assume
that $\\{f_{n}(\gamma_{c})\\}_{n\geq 1}$ is non-degenerate as in (7.1) and
$\mathbb{P}(Arm_{r,s}(\gamma_{c}))\to 0$ as $s\to\infty$. Then we have the
following :

  1. (i)

$\\{f_{n}(\gamma_{c})\\}_{n\geq 1}$ is noise sensitive.

  2. (ii)

$\\{f_{n}(\gamma_{c})\\}_{n\geq 1}$ has an infinite set of exceptional times
in $[0,1]$ i.e., $|S_{n}\cap[0,1]|\overset{\mathbb{P}}{\longrightarrow}\infty$
where the set of exceptional times $S_{n}$ is as defined below (7.1).

  3. (iii)

Further, assume that there exists $c_{arm}>0$ such that for all $s>2r$, the
following holds :

$\mathbb{P}(Arm_{r,s}(\gamma_{c}))\leq Cs^{-c_{arm}}.$

Let $c_{n}=n^{-\frac{c_{arm}}{2}+\epsilon}$ for some $\epsilon>0$. Then, we
have that $\mathbb{E}[f_{n}((1-c_{n})\gamma_{c})]\to 0$ and
$\mathbb{E}[f_{n}((1+c_{n})\gamma_{c})]\to 1.$

Before presenting a corollary of the above to the standard planar Poisson
Boolean model, we make some remarks about the theorem.

######  Remark 8.4.

  1. 1.

Using Theorem 7.4 one can actually prove that the conclusion of Theorem
8.3-(iii) continues to hold for sequences of the type
$c_{n}=n^{-c_{arm}+\epsilon}$, with $\epsilon>0$. In order to obtain such an
improvement, one has to prove that the randomized stopping set $Z_{n}$
determining $f_{n}$, as appearing in the proof, can be attained by a CTDT
satisfying the assumptions in Theorem 4.2. This fact can be checked by a
recursive construction similar to the one performed at the end of the
forthcoming proof of Theorem 8.2. Details are omitted.

  2. 2.

We can use $\theta_{s}(\gamma_{c})\to 0$ as $s\to\infty$ in the proof instead
of $\mathbb{P}(Arm_{r,s}(\gamma_{c}))\to 0$ as $s\to\infty$ and in item (iii),
we can use that $\theta_{s}(\gamma_{c})\leq Cs^{-c_{arm}}.$ We can argue this
as follows : Set $A^{\infty}_{r}(x):=\\{x\leftrightarrow\partial
B^{\infty}_{r}(x)\\}\cap\\{\partial
B^{\infty}_{r}(x)\subset\mathcal{O}(\gamma)\\}$ and note that for all $x$, we
have that $\mathbb{P}(A^{\infty}_{r}(x))=\mathbb{P}(A^{\infty}_{r}(0))>0$.
Since $A_{r}(x)$ and $\\{B^{\infty}_{r}(x)\leftrightarrow L\\}$ are increasing
events, by Harris-FKG inequality for Poisson point process [49, Theorem 20.4],
we derive that

$\displaystyle\mathbb{P}(Arm_{r,s}(\gamma_{c}))$
$\displaystyle\leq\mathbb{P}(A^{\infty}_{r}(0))^{-1}\mathbb{P}(A^{\infty}_{r}(0)\cap\\{B^{\infty}_{r}(0)\leftrightarrow\partial
B^{\infty}_{s}(0)\\})$
$\displaystyle\leq\mathbb{P}(A^{\infty}_{r}(0))^{-1}\mathbb{P}(0\leftrightarrow\partial
B^{\infty}_{s}(0))$
$\displaystyle\leq\mathbb{P}(A^{\infty}_{r}(0))^{-1}\mathbb{P}(0\leftrightarrow\partial
B_{s}(0))$
$\displaystyle\leq\mathbb{P}(A^{\infty}_{r}(0))^{-1}\theta_{s}(\gamma_{c}).$

  3. 3.

The above theorem has reduced the proof of noise sensitivity, exceptional
times and sharp phase transition for crossing events at criticality in the
$k$-percolation model to showing non-degeneracy of the crossing events and
bounds for one-arm probabilities or non-percolation at criticality. Showing
these properties is a seperate percolation theoretic question, often model-
specific and in the planar case, these have been achieved in some models via
RSW-type estimates (see [66, 67, 7, 74, 4, 42, 46]). See Corollary 8.5 below
for a case in which the above estimates are known.

  4. 4.

Another case in which it is known that $\theta_{s}(\gamma_{c})\to 0$ as
$s\to\infty$ is for $k=1$, determinstic balls and large $d$ (see [39, Section
6]).

  5. 5.

It was suggested in [2, Section 8] on how one may use the Schramm-Steif
quantitative noise sensitivity result on the Boolean hypercube and use
discretization to obtain noise sensitivity exponents. As illustrated in the
above theorem, the Poisson analogue of Schramm-Steif inequality (Corollary 5.3
that we apply via Proposition 6.3) helps to achieve these goals by using
stopping sets and without resorting to discretization. Furthermore, this makes
the results more easily applicable and also gives a transparent way to
quantify the noise sensitivity exponents in terms of the exponent $c_{arm}$ in
arm-event probabilities.

For the case of planar Poisson Boolean model (i.e., $k=1,d=2$) with grains
supported on balls centred at origin, the assumptions of the above theorem
follow immediately from [4, Theorems 1.1(ii) and 1.3(i)] and hence we derive
the following corollary easily from Theorem 8.3.

######  Corollary 8.5.

Consider the $1$-covered region $\mathcal{O}_{1}(\tilde{\eta})$ of the Poisson
Boolean model on ${\mathbb{R}}^{2}$ (i.e., $k=1,d=2$ in Theorem 8.3) as
defined in (8.1) with grain distribution $\mathbb{Q}$ supported on
${\mathcal{K}}^{b}_{r}$ and satisfying assumptions in (8.0). Then for
$f_{n}:=f_{n}(\gamma_{c})$ as defined in Theorem 8.3, the conclusions of the
Theorem 8.3 hold.

The above corollary settles [2, Conjecture 9.1] and our Theorem 8.3 gives
percolation theoretic criteria to prove [2, Conjecture 9.2 and Question 1].
See the discussion at the end of Section 1.3 for comparison with approach of
[2].

###### Proof of Theorem 8.3.

We shall assume $\gamma=\gamma_{c}$ and fix a $\kappa>0$ in our proof. Let
$R_{n}=[0,\kappa n]\times[0,n]^{d-1}$ be the rectangle to be crossed. Our
proof is by constructing a randomized stopping set
$\tilde{Z}_{n}:=Z_{n}\times{\mathcal{K}}_{r}\subset
R^{+}_{n}\times{\mathcal{K}}_{r},n\geq 10r$ with $R^{+}_{n}=R_{n}\oplus
B_{r}(0)$ as follows : For every $s\in(0,\kappa n)$, we shall construct a
stopping set $\tilde{Z}_{n}^{s}=Z_{n}^{s}\times{\mathcal{K}}_{r}$ such that
for all $x=(x_{1},\ldots,x_{d})\in R_{n}$,

$\displaystyle\mathbb{P}((x,K)\in\tilde{Z}_{n}^{s})$
$\displaystyle=\mathbb{P}(x\in Z_{n}^{s})$
$\displaystyle\leq\mathbf{1}\\{|s-x_{1}|\leq
r\\}+\mathbb{P}(Arm_{r,|s-x_{1}|}(\gamma_{c}))\mathbf{1}\\{|s-x_{1}|>r\\}$
$\displaystyle\leq\mathbb{P}(Arm_{r,|s-x_{1}|}(\gamma_{c})),$ (8.6)

where the last inequality is by setting the convention that
$Arm_{r,s}(\gamma_{c})=1$ for $s\leq r$. Now, we choose our randomized
stopping set by first choosing $Y$ uniformly at random in $(0,\kappa n)$ and
then setting
$Z_{n}=Z_{n}^{Y},\tilde{Z}_{n}=\tilde{Z}_{n}^{Y}=Z_{n}^{Y}\times{\mathcal{K}}_{r}$.
Thus, we obtain that

$\displaystyle\mathbb{P}((x,K)\in\tilde{Z}_{n})$
$\displaystyle=\mathbb{P}(x\in Z_{n})\leq(\kappa n)^{-1}\int_{0}^{\kappa
n}\mathbb{P}(Arm_{r,|s-x_{1}|}(\gamma_{c}))\mathrm{d}s$ $\displaystyle\leq
2(\kappa n)^{-1}\int_{0}^{\kappa
n}\mathbb{P}(Arm_{r,s}(\gamma_{c}))\mathrm{d}s.$

Thus, we derive that

$\delta_{n}:=\delta(\tilde{Z}_{n})\leq 2(\kappa n)^{-1}\int_{0}^{\kappa
n}\mathbb{P}(Arm_{r,s}(\gamma_{c}))\mathrm{d}s$

and since $\mathbb{P}(Arm_{r,s}(\gamma_{c}))\to 0$ as $s\to\infty$, we have
that $\delta_{n}\to 0$ by l’Hôpital’s rule. Note that $f_{n}$ is jump-regular
as the intensity measure of $\tilde{\eta}\cap((R_{n}\oplus
B_{0}(r))\times{\mathcal{K}}_{r})$ is finite and also $f_{n}$ is monotonic.
Now all the three items in the theorem follow from Proposition 6.3, Corollary
7.2 and Theorem 7.3 respectively.

Thus, we are left with construction of a stopping set $\tilde{Z}_{n}^{s}$ as
above or equivalently $Z_{n}^{s}$ with revealment probability as in (8.6).
Given $s\in(0,\kappa n)$, let $L=\\{s\\}\times[0,n]^{d-1}$ and let $S$ be
union of the connected components of $\mathcal{O}(\tilde{\eta})\cap R_{n}$
that intersect $L$. Note that $S=\emptyset$ if no such components exist.
Define $Z_{n}^{s}:=(S\cup L)\oplus B_{r}(0)$.

Now we show that $Z_{n}^{s}$ is a stopping set in ${\mathbb{R}}^{d}$ as in
Remark A.7. Let $x=(x_{1},\ldots,x_{d})\in{\mathbb{R}}^{d}$. Suppose that
$B_{r}(x)\cap L\neq\emptyset$ (or equivalently $|x_{1}-s|\leq r$), then $x\in
Z_{n}^{s}$. Otherwise, $x\in Z_{n}^{s}$ and $B_{r}(x)\cap L=\emptyset$ i.e.,
$|x_{1}-s|>r$. Then, we have that $B_{r}(x)\cap S\neq\emptyset$ which is
equivalent to $B_{r}(x)\stackrel{{\scriptstyle R_{n}}}{{\leftrightarrow}}L$.
Thus, we derive that

$\mathbf{1}\\{x\in Z_{n}^{s}\\}=\mathbf{1}\\{B_{r}(x)\cap
L\neq\emptyset\\}+\mathbf{1}\\{B_{r}(x)\cap
L=\emptyset\\}\mathbf{1}\\{B_{r}(x)\stackrel{{\scriptstyle
R_{n}}}{{\leftrightarrow}}L\\}.$ (8.7)

The above identity yields graph-measurability of $Z_{n}^{s}$. Observe that $S$
as defined above is actually $S(\tilde{\eta})$ to be more explicit. Set
$S^{\prime}(\tilde{\eta})=S(\tilde{\eta})\oplus B_{r}(0)$. Then
$S(\tilde{\eta})=S(\tilde{\eta}_{S^{\prime}\times{\mathcal{K}}_{r}})$ because
$(x,K)\in(S^{\prime})^{c}\times{\mathcal{K}}_{r}$ implies that $(x+K)\cap
S=\emptyset$. Thus,
$S^{\prime}(\tilde{\eta})=S^{\prime}(\tilde{\eta}_{S^{\prime}\times{\mathcal{K}}_{r}})$.
In the same way, we can also deduce that
$S^{\prime}(\tilde{\eta}_{S^{\prime}\times{\mathcal{K}}_{r}})=S^{\prime}(\tilde{\eta}_{S^{\prime}\times{\mathcal{K}}_{r}}+\psi_{(S^{\prime})^{c}\times{\mathcal{K}}_{r}})$
for any $\psi\in{\mathbf{N}}({\mathbb{R}}^{d}\times{\mathcal{K}}_{r})$. This
verifies (A.1) and shows that $Z_{n}^{s}$ is a stopping set as in Remark A.7.

We obtain from the above arguments and Remark A.8 that
$\tilde{Z}_{n}^{s}=Z_{n}^{s}\times{\mathcal{K}}_{r}$ is a stopping set in
${\mathbb{R}}^{d}\times{\mathcal{K}}_{r}$ as required. Further, it is easy to
see that $\tilde{Z}_{n}^{s}=Z_{n}^{s}\times{\mathcal{K}}_{r}$ determines
$f_{n}$ as well. Now, we will derive bounds on the revealment probability of
$Z_{n}^{s}$. For $x\in R^{d}$ with $B_{r}(x)\cap L=\emptyset$, using (8.7), we
have that

$\mathbb{P}(x\in Z_{n}^{s})\leq\mathbb{P}(B_{r}(x)\cap
S\neq\emptyset)\leq\mathbb{P}(B_{r}(x)\stackrel{{\scriptstyle
R_{n}}}{{\leftrightarrow}}L)\leq\mathbb{P}(Arm_{r,|s-x_{1}|}(\gamma_{c})).$

Thus, we have shown (8.6) and the proof is complete. ∎

We now conclude the section with the proof of Theorem 8.2.

###### Proof of Theorem 8.2.

Let $\mathbb{Q}_{s}:=\delta_{B_{s}(0)}$ denote the probability distribution on
grains supported on a deterministic ball of radius $s$. By the scaling
property of the Poisson process, $k$-percolation in the Poisson Boolean model
with intensity $\gamma$ and grain distribution $\mathbb{Q}_{s}$ is equivalent
to $k$-percolation in the Poisson Boolean model with intensity $1$ and grain
distribution $\mathbb{Q}_{\gamma^{1/d}s}$. Now, using [13, Corollary 1.3] and
the above scaling property, we have that
$\gamma_{c}(\mathbb{Q}_{s})\in(0,\infty)$ for any $s\in(0,\infty)$. Now since
$\mathbb{Q}$ satisfies the assumption (8.0), we have that
$\gamma_{c}(\mathbb{Q})\geq\gamma_{c}(\mathbb{Q}_{r})>0$. Further, let
$\beta=\mathbb{Q}\\{K:B_{r_{0}}(0)\subset K\\}$ and by assumption (8.0),
$\beta>0$. Let $\mathcal{O}^{\prime}$ be the $k$-occupied region defined on a
Poisson point process with intensity $\beta\gamma$ and grain distribution
$\mathbb{Q}_{r_{0}}$. By the Poisson thinning property [49, Theorem 5.8], we
have that $\mathcal{O}^{\prime}\subset\mathcal{O}(\gamma)$ and hence
$\gamma_{c}(\mathbb{Q})\leq\beta\gamma_{c}(\mathbb{Q}_{r_{0}})<\infty$. Thus
$\gamma_{c}(\mathbb{Q})\in[\gamma_{c}(\mathbb{Q}_{r}),\beta\gamma_{c}(\mathbb{Q}_{r_{0}})]\subset(0,\infty)$
and we have shown the non-degeneracy of $\gamma_{c}(\mathbb{Q})$.

Further, $\mathcal{O}_{k}(\tilde{\eta})\subset\mathcal{O}_{1}(\tilde{\eta})$
for all $k\geq 1$ and hence by the exponential decay result for
$\mathcal{O}_{1}(\tilde{\eta})$ in [80, Theorem 3.1], we have that there
exists $a>0$ such that $\theta_{s}(\gamma)$ decays exponentially for
$\gamma<a$. Trivially $a<\gamma_{c}$ and we shall fix such an $a$ in the rest
of the proof.

Assume $n\geq 10r$ and choose $b\in(\gamma_{c},\infty)$. Similar to the the
proof of Theorem 8.3, we will define a randomized stopping set $Z_{n}$ in
${\mathbb{R}}^{d}$ that determines $\mathbf{1}\\{0\leftrightarrow\partial
B_{n}(0)\\}$ such that there exists a constant $C_{a}$ for all
$\gamma\in[a,b]$ satisfying the following bound on revealment probability :

$\delta_{n}=\max_{x\in{\mathbb{R}}^{d}}\mathbb{P}(x\in Z_{n})\leq
C_{a}n^{-1}\int_{0}^{n}\theta_{s}(\gamma)\mathrm{d}s.$ (8.8)

Further, we will show that $Z_{n}$ can be constructed via randomized CTDT as
in Theorem 4.2. Then using Theorem 4.2, monotonicity of
$\mathbf{1}\\{0\leftrightarrow\partial B_{n}(0)]\\}$ and the Russo-Margulis
formula for Poisson functionals (see [49, Theorem 19.4]), we derive that

$\displaystyle\theta_{n}(\gamma)(1-\theta_{n}(\gamma))$
$\displaystyle\leq\gamma\int_{{\mathbb{R}}^{d}\times{\mathcal{K}}_{r}}\mathbb{P}(x\in
Z_{n})\mathbb{E}[D_{(x,K)}\mathbf{1}\\{0\leftrightarrow\partial
B_{n}(0)\\}]\,\mathbb{Q}(dK)\,\mathrm{d}x$
$\displaystyle\leq\gamma\delta_{n}\int_{B_{n+2r}(0)\times{\mathcal{K}}_{r}}\mathbb{E}[D_{(x,K)}\mathbf{1}\\{0\leftrightarrow\partial
B_{n}(0)\\}]\,\mathbb{Q}(dK)\,\mathrm{d}x$
$\displaystyle=\gamma\delta_{n}\frac{\mathrm{d}\theta_{n}(\gamma)}{\mathrm{d}\gamma}=\gamma\delta_{n}\theta^{\prime}_{n}(\gamma).$

Thus, using the bound for $\delta_{n}$, we obtain for $\gamma\in[a,b]$ the
differential inequality ,

$\theta^{\prime}_{n}(\gamma)\geq\frac{n}{C_{a}b\int_{0}^{n}\theta_{s}(\gamma)\mathrm{d}s}\theta_{n}(\gamma)(1-\theta_{n}(\gamma))\geq\frac{n}{C_{a}b\int_{0}^{n}\theta_{s}(\gamma)\mathrm{d}s}\theta_{n}(\gamma)(1-\theta_{1}(b)),$

where we have used that $\theta_{s}(\gamma)$ is increasing in $\gamma$ and
decreasing in $s$. Now using a straightforward variant of [23, Lemma 3.1] (see
also [25, Proof of Theorem 1.2]), we obtain that there exists
$\gamma_{1}\in[a,b]$ such that

  * •

For $\gamma\in[a,\gamma_{1})$,
$\theta_{n}(\gamma)\leq\exp\\{-\alpha(\gamma)n\\}$ for all $n\geq 1$ and some
constants $\alpha(\gamma)\in(0,\infty)$.

  * •

For $\gamma\in[\gamma_{1},b]$, there exists a constant
$\alpha(b)\in(0,\infty)$ such that
$\theta(\gamma)\geq\alpha(b)(\gamma-\gamma_{1})$.

Since $a<\gamma_{c}<b$ by construction and since the previous properties imply
that $\theta(\gamma)=0$ for $\gamma\in(a,\gamma_{1})$ and $\theta(\gamma)>0$
for $\gamma\in(\gamma_{1},b)$ we conclude that, necessarily,
$\gamma_{1}=\gamma_{c}$. Thus, both the claims in the theorem follow.

All that remains to complete the proof is to show that $Z_{n}$ can be
constructed via a randomized CTDT satisfying suitable assumptions. First, we
will describe the randomized stopping set $Z_{n}$, then show that it satisfies
the required revealment probability and finally construct it as a randomized
CTDT satisfying the necessary assumptions.

Fix $s\in(0,n)$. We now define $Z^{s}_{n}$. Let $S$ be the union of connected
components of $\mathcal{O}(\gamma)\cap B_{n}(0)$ that intersect $\partial
B_{s}(0)$. Note that $S=\emptyset$ if there is no connected component of
$\mathcal{O}(\gamma)\cap B_{n}(0)$ that intersects $\partial B_{s}(0)$.
Observe that the event $\\{0\leftrightarrow\partial B_{n}(0)\\}$ is determined