# Critical speeding-up in dynamical percolation

Eren Metin Elçi, Timothy M. Garoni  School of Mathematics, Monash University,
Clayton, Victoria 3800, Australia<EMAIL_ADDRESS>
###### Abstract

We study the autocorrelation time of the size of the cluster at the origin in
discrete-time dynamical percolation. We focus on binary trees and high-
dimensional tori, and show in both cases that this autocorrelation time is
linear in the volume in the subcritical regime, but strictly sublinear in the
volume at criticality. This establishes rigorously that the cluster size at
the origin in these models exhibits critical speeding-up. The proofs involve
controlling relevant Fourier coefficients. In the case of binary trees, these
Fourier coefficients are studied explicitly, while for high-dimensional tori
we employ a randomised algorithm argument introduced by Schramm and Steif in
the context of noise sensitivity.

Keywords: Critical speeding-up, percolation, noise sensitivity

##  1 Introduction

Just as models in statistical mechanics typically exhibit divergent spatial
scales near a critical point, stochastic dynamics associated with such models
also tend to display divergent time scales [1]. For example, Markov chains
employed in Monte Carlo algorithms at critical points typically exhibit
relaxation times and stationary autocorrelation times which scale
superlinearly with volume [2]; this well-known phenomenon is referred to as
_critical slowing-down_. By contrast, a less familiar possibility is that time
scales associated with certain observables scale sublinearly with volume at
criticality. This phenomenon of _critical speeding-up_ has been observed
experimentally (see e.g. [3, 4, 5, 6]), and also in Monte Carlo simulations
[7, 8, 9].

In particular, in [7] the heat-bath dynamics of the critical Fortuin-Kasteleyn
random-cluster model was simulated, on 2-dimensional and 3-dimensional tori,
at a variety of cluster fugacities. The autocorrelations of certain
observables were then studied. The sum of squared cluster sizes, which is a
natural estimator for the susceptibility, was studied in detail. It was
observed generically that its stationary autocorrelation function decays on a
time scale strictly sublinear in the volume. Moreover, for a range of cluster
fugacities, sublinear scaling was also observed for its autocorrelation time,
which quantifies the time scale between “effectively independent” samples. In
particular, these behaviours were observed for the case of unit cluster
fugacity, for which the stationary distribution reduces to that of independent
bond percolation. We will refer to this special case of the random-cluster
model heat-bath dynamics as discrete-time dynamical percolation; see section
2.1 for a precise definition.

Independently, closely-related questions were being addressed in the context
of noise sensitivity of Boolean functions defined on the discrete hypercube;
see [10] for an overview. The notion of noise sensitivity was introduced in
[11], and in essence it amounts to the fast decay of autocorrelation functions
in dynamical percolation; for precise definitions see section 3. In
particular, it was shown in [11] that the indicator for a left-right crossing
of a rectangle in critical bond percolation on $\mathbb{Z}^{2}$ is noise
sensitive. A quantitative version of this result, bounding the rate of decay
of these autocorrelations, was then presented in [12]. A key tool employed in
these results was Fourier analysis on the hypercube.

Our main aim in the current work is to study critical speeding-up using the
same framework introduced for noise sensitivity. Whilst the existing noise
sensitivity literature focuses largely on Boolean functions, our focus will
instead be on non-Boolean functions. Specifically, we consider the size of the
cluster containing the origin/root in dynamical percolation on binary trees
and high-dimensional tori. We show in both cases that this autocorrelation
time is linear in the volume in the subcritical regime, but strictly sublinear
in the volume at criticality. In the case of high-dimensional tori, a key tool
in our proof is a theorem due to Schramm and Steif [12] which bounds Fourier
coefficients by considering randomised algorithms.

###  1.1 Outline

The remainder of the article is organised as follows. Section 1.2 lists some
notational conventions. In section 2.1, we explicitly define dynamical
percolation, in both discrete and continuous time, and also recall standard
definitions of the autocorrelation function and autocorrelation time.
Statements of our main results are then presented in section 2.2. Section 3.1
provides explicit spectral representations of the autocorrelation functions
and autocorrelation times, in both discrete-time and continuous time. Section
3.2 then discusses a slight variant of the revealment theorem of [12]. Our
main results are then proved in sections 4 and 5, which cover the case of
binary trees and high-dimensional tori, respectively. Finally, section 6
presents a self-contained proof of the theorem discussed in section 3.2.

###  1.2 Notation

The set of non-negative integers will be denoted by $\mathbb{N}$, and
$\mathbb{Z}_{+}:=\mathbb{N}\setminus 0$. For any $n\in\mathbb{Z}_{+}$ we write
$[n]:=\\{1,2,\ldots,n\\}$. For a finite set $A$ and $k\in\mathbb{N}$ we denote
by $\binom{A}{k}$ the set of all subsets of $A$ of cardinality $k$, and we let
$[A]:=[|A|]$. For vertices $x$ and $y$ in a graph, we will write
$x\leftrightarrow y$ to denote that $x$ and $y$ belong to the same connected
component.

In addition to the standard asymptotic symbols $O$ and $o$ we find it
convenient to write $f=\Omega(g)$ to denote $g=O(f)$ and $f=\omega(g)$ to
denote $g=o(f)$. If both $f=O(g)$ and $f=\Omega(g)$ we will write
$f=\Theta(g)$. We will also use the Vinogradov symbols, so that $f\ll g$ is
equivalent to $f=O(g)$, and $f\gg g$ is equivalent to $g=O(f)$.

##  2 Definitions and results

###  2.1 Dynamical percolation and autocorrelations

Let $S:=\\{-1,1\\}$, and let $B$ be any finite set. For a given $p\in(0,1)$,
let

$\pi_{p}(s):=p\,\mathbf{1}(s=+1)+(1-p)\,\mathbf{1}(s=-1),\qquad s\in S\;,$ (1)

denote the Bernoulli distribution on $S$, and let $\pi_{p,B}$ be the
corresponding product measure on $S^{B}$, so that

$\pi_{p,B}(x):=\prod_{i\in B}\pi_{p}(x_{i})\;,\qquad\text{ for all }x\in
S^{B}\;.$ (2)

We refer to the elements of $B$ as bits, and with respect to $x\in S^{B}$ we
say $i\in B$ is open if $x_{i}=+1$ and closed if $x_{i}=-1$.

Now consider the stochastic matrix on state space $S^{B}$ with entries

$P_{p,B}(x,y):=\frac{1}{|B|}\sum_{i\in B}\pi_{p}(y_{i})\,\prod_{j\in
B\setminus i}\mathbf{1}(y_{j}=x_{j})\;.$ (3)

This is the special case of the discrete-time heat-bath chain for the Fortuin-
Kasteleyn model (see e.g. [13]) on a graph with edge set $B$, when the cluster
fugacity is $q=1$. In the special case $p=1/2$, it reduces to lazy simple
random walk on the hypercube $S^{B}$. The latter also corresponds to the
infinite temperature limit of the discrete-time single-spin heat-bath process
for the Ising model, on a graph with vertex set $B$. For a given choice of $B$
and $p$, let $Z^{p,B}=(Z_{s}^{p,B})_{s\in\mathbb{N}}$ be a stationary Markov
chain with transition matrix $P_{p,B}$. We refer to the process $Z^{p,B}$ as
discrete-time dynamical percolation on $B$ with parameter $p$. We emphasise
that for each $s\in\mathbb{N}$, the state $Z^{p,B}_{s}$ has distribution
$\pi_{p,B}$.

Discrete-time dynamical percolation has an intimate relationship to the
dynamical percolation model first studied in [14]. The latter corresponds to a
countably infinite family of independent continuous-time Markov chains on $S$,
each with generator $\Pi_{p}-I$, where $\Pi_{p}$ is the matrix on $S$ with
entries $\Pi_{p}(s,s^{\prime})=\pi_{p}(s^{\prime})$. It is easily seen that
the subset of chains corresponding to a particular set of bits $B$ is a
continuous time Markov chain on $S^{B}$ with generator
$Q_{p,B}=|B|(P_{p,B}-I)$; in particular, $Q_{p,B}$ is the rate-$|B|$
continuization (see e.g. [15, section 20.1]) of $P_{p,B}$.

We are interested in the autocorrelations of the real-valued processes
$f(Z_{s}^{p,B})$ induced by functions $f:S^{B}\to\mathbb{R}$. The
corresponding _autocorrelation function_ is

$\rho_{p,f}(s):=\frac{\operatorname{cov}(f(Z_{0}^{p,B}),f(Z_{s}^{p,B}))}{\operatorname{var}(f(Z_{0}^{p,B}))},\qquad
s\in\mathbb{N}\;,$ (4)

and _autocorrelation time_ 111This is often referred to as the _integrated_
autocorrelation time [2]. is

$\tau_{p,f}:=\frac{1}{2}\sum_{s\in\mathbb{Z}}\rho_{p,f}(|s|)\;.$ (5)

Analogous quantities can also be defined for continuous-time dynamical
percolation. If $Y^{p,B}=(Y_{t}^{p,B})_{\geq 0}$ is a stationary continuous-
time Markov chain with generator $Q_{p,B}$, then we set

$\tilde{\rho}_{p,f}(t):=\frac{\operatorname{cov}(f(Y_{0}^{p,B}),f(Y_{t}^{p,B}))}{\operatorname{var}(f(Y_{0}^{p,B}))},\qquad
t\in[0,\infty)\;,$ (6)

and

$\tilde{\tau}_{p,f}:=\int_{0}^{\infty}\tilde{\rho}_{p,f_{B}}(t)\,\mathrm{d}t\;.$
(7)

One concrete motivation for interest in $\tau_{p,f}$ is that (see e.g. [16,
equation (9.2.11)])

$\operatorname{var}\left(\frac{1}{T}\sum_{s=0}^{T-1}f(Z_{s}^{p,B})\right)\sim\frac{2\tau_{p,f}}{T}\operatorname{var}(f(Z_{0}^{p,B})),\qquad
T\to\infty\;.$ (8)

Therefore, if one wishes to estimate $\mathbb{E}(f(Z_{0}^{p,B}))$ by
simulating $Z^{p,B}$, the squared error is proportional to $\tau_{p,f}$. By
contrast, the variance of the sample mean of $m$ independent realisations of
$f(Z_{0}^{p,B})$ is simply $\operatorname{var}(f(Z_{0}^{p,B}))/m$. Since each
such independent realisation consists of $|B|$ bit updates, in order to
meaningfully compare estimates from independent samples with those constructed
using the Markov chain $Z^{p,B}$, one should set $T=m|B|$.

Now fix $p$, and consider an increasing sequence of bit sets, $B_{n}$, and a
sequence of functions $f_{n}:S^{B_{n}}\to\mathbb{R}$. It follows that Markov-
chain sampling asymptotically outperforms independent sampling in estimation
of $\mathbb{E}(f_{n}(Z_{0}^{p,B_{n}}))$ iff $\tau_{p,f_{n}}=o(|B_{n}|)$ as
$n\to\infty$. When a sequence of functions displays such behaviour, for a
given value of $p$, we say it exhibits _speeding up_. In section 2.2 we
discuss the autocorrelation time for the cluster size at the origin in
discrete-time dynamical percolation on trees and high-dimensional tori. We
find that while speeding up does not occur in the subcritical regime, it does
occur at criticality. This phenomenon is precisely what we shall mean by
_critical speeding-up_.

The autocorrelations of discrete-time and continuous-time dynamical
percolation are closely related. In fact, it follows immediately from lemma
3.2 below that

$\tau_{p,f}=|B|\,\tilde{\tau}_{p,f}-1/2\;.$ (9)

From equation (9), it follows that a sequence of functions $f_{n}$ displays
speeding up, at parameter $p$, iff the corresponding sequence
$\tilde{\tau}_{p,f_{n}}=o(1)$ as $n\to\infty$. Moreover, the following result,
whose proof is deferred to section 3, implies that the continuous-time and
discrete-time autocorrelation functions have closely related asymptotics, on
non-trivial timescales.

######  Lemma 2.1.

Fix $p\in(0,1)$. Let $B_{n}$ be an increasing sequence of finite sets, and let
$f_{n}:S^{B_{n}}\to\mathbb{R}$ be a sequence of non-constant functions. Then
as $n\to\infty$, for any positive integer sequence $s_{n}$ satisfying
$s_{n}=\omega(1)$ we have

$\rho_{p,f_{n}}(s_{n})=\tilde{\rho}_{p,f_{n}}(s_{n}/|B_{n}|)+o(1)\;.$

There is a direct relationship between the decay of the continuous-time
autocorrelation function, and the notion of noise sensitivity. Fix
$p\in(0,1)$, and let $X^{p,B}$ be a random element of $S^{B}$ with
distribution $\pi_{p,B}$. For given $\epsilon>0$, let $X^{p,B}_{\epsilon}$
denote the following perturbation of $X^{p,B}$: independently for each bit
$i$, with probability $1-\epsilon$ the $i$th bit of $X^{p,B}_{\epsilon}$
agrees with the $i$th bit of $X^{p,B}$, and with probability $\epsilon$ it is
set to a new random value chosen according to $\pi_{p}$, independent of its
previous value, and independent of the values of all other bits. Now consider,
again, an increasing sequence of finite sets $B_{n}$. A sequence of Boolean
functions $f_{n}:S^{B_{n}}\to S$ is called _noise sensitive_ [10] if the
covariance of $f_{n}(X^{p,B_{n}})$ and $f_{n}(X^{p,B_{n}}_{\epsilon})$ goes to
zero as $n\to\infty$ for all $\epsilon>0$. However, it is straightforward to
verify directly that if $\epsilon=1-\rme^{-t}$ then
$(X^{p,B},X^{p,B}_{\epsilon})$ and $(Y^{p,B}_{0},Y^{p,B}_{t})$ have the same
joint distribution. Therefore, the covariance of $f_{n}(X^{p,B_{n}})$ and
$f_{n}(X^{p,B_{n}}_{\epsilon})$ is precisely the covariance of
$f_{n}(Y_{0}^{p,B})$ and $f_{n}(Y_{t}^{p,B})$, and the correlation of
$f_{n}(X^{p,B_{n}})$ and $f_{n}(X^{p,B_{n}}_{\epsilon})$ is precisely
$\tilde{\rho}_{p,f_{n}}(t)$. Provided that
$\operatorname{var}(f_{n}(X^{p,B_{n}}))$ is bounded away from zero, it then
follows that $f_{n}$ is noise sensitive iff $\tilde{\rho}_{p,f_{n}}(t)\to 0$
as $n\to\infty$ for all fixed $t>0$. We remark that although noise sensitivity
is typically only considered in the specific case $p=1/2$, the above
discussion makes sense for any fixed $p\in(0,1)$.

In the case of non-Boolean functions, where the variance is no longer bounded
from above by 1, it is arguably more natural to consider the correlation from
the outset, rather than the covariance. In addition to the question of
speeding up, we will be interested in the question of sublinear
autocorrelation decay, in the sense that there exists $c_{n}=o(|B_{n}|)$ such
that $\rho_{p,f_{n}}(s_{n})=o(1)$ for all $s_{n}=\omega(c_{n})$. We emphasise
that speeding up and autocorrelation decay can occur at strictly different
time scales. A simple example illustrating this is presented below in equation
(15).

###  2.2 Results

Our main results concern autocorrelations of the size of the cluster
containing a fixed vertex, in dynamical percolation on certain trees and high-
dimensional tori. The set of bits, $B$, then corresponds to the edge set of
the tree or torus under consideration, and for $x\in S^{B}$ drawn from
$\pi_{p,B}$, we consider the connected components of the spanning subgraph
defined by the open edges. The size of a such a connected component, or
cluster, is then simply the number of vertices which it contains.

Our result for trees is as follows. By a _binary tree_ , we simply mean a
rooted tree in which each vertex has at most 2 children. We say a binary tree
is _perfect_ if each non-leaf vertex has precisely two children, and all
leaves have the same depth. Recall (see e.g. [17, theorem 1.8]) that the
critical threshold for bond percolation on the infinite-depth perfect binary
tree is $p_{\mathrm{c}}=1/2$.

######  Proposition 2.2.

For $n\in\mathbb{Z}_{+}$, let $(V_{n},B_{n})$ denote the perfect binary tree
of depth $n$. For $p\in(0,1)$, consider discrete-time dynamical percolation on
$(V_{n},B_{n})$, and let $f_{n}$ denote the size of the cluster containing the
root.

  1. (i)

Let $s_{n}$ be a positive integer sequence. If $p\in(0,1)$ and $p\neq 1/2$
then

$\lim_{n\to\infty}\rho_{p,f_{n}}(s_{n})=\begin{cases}1,&\text{ if
}s_{n}=o(|B_{n}|),\\\ 0,&\text{ if }s_{n}=\omega(|B_{n}|).\\\ \end{cases}$

  2. (ii)

Let $s_{n}$ be a positive integer sequence. Then

$\lim_{n\to\infty}\rho_{1/2,f_{n}}(s_{n})=\begin{cases}1,&\text{ if
}s_{n}=o(|B_{n}|/n),\\\ 0,&\text{ if }s_{n}=\omega(|B_{n}|/n).\\\ \end{cases}$

  3. (iii)

As $n\to\infty$

$\dfrac{\tau_{p,f_{n}}}{|B_{n}|}\sim\begin{cases}\dfrac{1-2p}{2p(1-p)}\log\left(\dfrac{1-2p^{2}}{1-2p}\right),&p\in(0,1/2),\vspace{3mm}\\\
6\dfrac{\log(n)}{n},&p=1/2,\vspace{3mm}\\\
\dfrac{2p-1}{(1-p)}\log\left(\dfrac{p}{2p-1}\right),&p\in(1/2,1).\end{cases}$

Part (iii) of proposition 2.2 clearly illustrates the phenomenon of critical
speeding up; the autocorrelation time for the cluster at the root is linear in
the volume for all off-critical $p$, but is strictly sublinear at criticality.

Our other example concerns dynamical percolation on high-dimensional tori. For
integer $d\geq 2$, let $p_{\mathrm{c}}(d)$ denote the critical threshold of
bond percolation on $\mathbb{Z}^{d}$. For integer $L>2$, we denote by
$\mathbb{T}^{d}_{L}$ the $d$-dimensional discrete torus of side length $L$,
whose vertex set we take to be $[-L/2,L/2)^{d}\cap\mathbb{Z}^{d}$.

######  Proposition 2.3.

Let $d,L\in\mathbb{Z}_{+}$ with $L>2$. Consider discrete-time dynamical
percolation on $\mathbb{T}^{d}_{L}$, and let $f_{d,L}$ denote the size of the
cluster connected to the origin. For any fixed but sufficiently large $d$, we
have as $L\to\infty$ that

$\tau_{p,f_{d,L}}=\begin{cases}\Theta(L^{d}),&0<p<p_{\mathrm{c}}(d)\;,\\\
O(L^{d-1/13}),&p=p_{\mathrm{c}}(d)\;,\end{cases}$

and for a positive sequence $t_{L}$ that

$\rho_{p,f_{d,L}}(\left\lceil
t_{L}L^{d}\right\rceil)=\begin{cases}\Theta(1),&t_{L}=o(1),\,p<p_{\mathrm{c}}(d)\;,\\\
o(1),&t_{L}=\omega(L^{-1/13}),\,p=p_{\mathrm{c}}(d)\;.\end{cases}$

We note that the implied constants in the asymptotic statements in proposition
2.3 may in general depend on $p$ and $d$.

##  3 Spectral representations

###  3.1 Autocorrelations

Given $p\in(0,1)$ and a finite set $B$, let $l^{2}(\pi_{p,B})$ denote the
vector space $\mathbb{R}^{S^{B}}$ endowed with the inner product

$\langle f,g\rangle_{p,B}:=\sum_{x\in S^{B}}f(x)g(x)\pi_{p,B}(x),\qquad\text{
for all }f,g\in\mathbb{R}^{S^{B}}\;.$ (10)

Let

$\nu_{p}:=\sqrt{(1-p)/p}\;,$ (11)

and for each $A\subseteq B$, define $\Psi_{A}^{p,B}:S^{B}\to\mathbb{R}$ via

$\Psi_{A}^{p,B}(x)=\prod_{b\in A}\,x_{i}\,\nu_{p}^{x_{i}},\qquad\text{ for all
}x\in S^{B}\;.$ (12)

It can be easily verified that $\\{\Psi_{A}^{p,B}\\}_{A\subseteq B}$ is an
orthonormal basis for $l^{2}(\pi_{p,B})$, and that, for each $A\subseteq B$,
$\Psi_{A}^{p,B}$ is an eigenvector of $P_{p,B}$ with eigenvalue

$\lambda_{A}^{B}:=1-\frac{|A|}{|B|}\;.$ (13)

######  Remark 3.1.

Combining the explicit expression for the eigenvalues from equation (13) with
general spectral results on autocorrelations in [16, equations (9.2.26) and
(9.2.27)] immediately implies that for any $p\in(0,1)$ and any function
$f:S^{B}\to\mathbb{R}$ we have $\tau_{f,p}=O(|B|)$ for large $|B|$. In
particular, dynamical percolation does not suffer from critical slowing down.

Given a non-constant function $f:S^{B}\to\mathbb{R}$, it is convenient to
introduce the random variable $\mathcal{W}_{p,f}$, taking values in $[B]$,
with probability mass function

$\mathbb{P}(\mathcal{W}_{p,f}=k)=\sum_{A\in\binom{B}{k}}\frac{\langle
f,\Psi_{A}^{p,B}\rangle_{p,B}^{2}}{\operatorname{var}(f(Z_{0}^{p,B}))}\;.$
(14)

Autocorrelation functions and autocorrelation times for both the discrete time
process $(Z_{s}^{p,B})_{s\in\mathbb{N}}$ and continuous time process
$(Y_{t}^{p,B})_{t\in[0,\infty)}$ can be conveniently expressed in terms of
$\mathcal{W}_{p,f}$. The following lemma, whose proof we omit, is a simple
consequence of the spectral decomposition of $P_{p,B}$, using the explicit
expressions from equations (12) and (13).

######  Lemma 3.2.

Let $p\in(0,1)$, let $B$ be a finite set, and let $f:S^{B}\to\mathbb{R}$ be a
non-constant function. Then:

  1. (i)

$\rho_{p,f}(s)=\mathbb{E}\left(1-\dfrac{\mathcal{W}_{p,f}}{|B|}\right)^{s}$
for all $s\in\mathbb{N}$

  2. (ii)

$\tau_{p,f}=|B|\,\mathbb{E}(\mathcal{W}_{p,f}^{-1})-1/2$

  3. (iii)

$\tilde{\rho}_{p,f}(t)=\mathbb{E}(\rme^{-t\mathcal{W}_{p,f}})$ for all
$t\in[0,\infty)$

  4. (iv)

$\tilde{\tau}_{p,f}=\mathbb{E}(\mathcal{W}_{p,f}^{-1})$

As a simple example, fix $\gamma\in(0,1)$ and consider
$f:S^{[n]}\to\mathbb{R}$ defined by

$f:=n^{-\gamma/2}\,\Psi_{\\{1\\}}^{p,[n]}+\sqrt{1-n^{-\gamma}}\,\Psi_{[n]}^{p,[n]}\;.$
(15)

If $p=1/2$, then $\Psi_{\\{1\\}}^{p,[n]}$ is referred to as a dictator
function, and $\Psi_{[n]}^{p,[n]}$ is the parity function; see e.g. [18]. For
any $p\in(0,1)$, however, equation (14) yields

$\mathbb{P}(\mathcal{W}_{p,f}=k)=n^{-\gamma}\,\mathbf{1}(k=1)+(1-n^{-\gamma})\,\mathbf{1}(k=n)\;.$
(16)

Lemma 3.2 then implies that $\lim_{n\to\infty}\rho_{p,f}(1)=0$ and
$\tau_{p,f}\sim n^{1-\gamma}$ as $n\to\infty$. In particular, we see in this
example that while the timescale at which $\rho_{p,f}$ decays to zero is of
constant order in $n$, the autocorrelation time diverges as a power law. This
provides a simple example, as mooted at the end of section 2.1, that the
timescales characterising autocorrelation decay and speeding up are not
related in general.

Propositions 2.2 and 2.3 will be proved by establishing appropriate results
for the distribution of $\mathcal{W}_{p,f}$, and then applying lemma 3.2.
Lemma 3.2 also provides a straightforward proof of lemma 2.1.

###### Proof of lemma 2.1.

Let $n\in\mathbb{Z}_{+}$ and $s\in\mathbb{N}$. From lemma 3.2 we have

$\displaystyle\rho_{p,f_{n}}(s)$
$\displaystyle=\sum_{k\in[B_{n}]}\mathbb{P}(\mathcal{W}_{p,f}=k)\left(1-\frac{k}{|B_{n}|}\right)^{s}$
(17)
$\displaystyle=\sum_{k=1}^{|B_{n}|-1}\rme^{-ks/|B_{n}|}\mathbb{P}(\mathcal{W}_{p,f_{n}}=k)\rme^{-s\left(k/|B_{n}|\right)^{2}h\left(k/|B_{n}|\right)}$
(18)

where $h:[0,1)\to[0,\infty)$ is defined via

$h(x):=\frac{-x-\log(1-x)}{x^{2}}=\sum_{l=0}^{\infty}\frac{x^{l}}{l+2}$ (19)

and the simple identity $\rme^{x}(1-x)=\rme^{-x^{2}h(x)}$ has been employed.
This immediately yields the upper bound

$\displaystyle\rho_{p,f_{n}}(s_{n})$
$\displaystyle\leq\sum_{k=1}^{|B_{n}|}\rme^{-ks_{n}/|B_{n}|}\mathbb{P}(\mathcal{W}_{p,f_{n}}=k)$
(20) $\displaystyle=\tilde{\rho}_{p,f_{n}}(s_{n}/|B_{n}|)\;.$ (21)

Now let $c_{n}$ be a positive sequence satisfying $c_{n}=\omega(1)$ and
$c_{n}=o(\sqrt{s_{n}})$, and set $a_{n}:=\lfloor|B_{n}|c_{n}/s_{n}\rfloor$.
Then

$\displaystyle\rho_{p,f_{n}}(s_{n})$
$\displaystyle\geq\sum_{k=1}^{a_{n}}\rme^{-ks_{n}/|B_{n}|}\mathbb{P}(\mathcal{W}_{p,f_{n}}=k)\rme^{-s_{n}\left(k/|B_{n}|\right)^{2}h\left(k/|B_{n}|\right)}$
(22)
$\displaystyle\geq\sum_{k=1}^{a_{n}}\rme^{-ks_{n}/|B_{n}|}\mathbb{P}(\mathcal{W}_{p,f_{n}}=k)\rme^{-(c_{n}/\sqrt{s_{n}})^{2}h\left(c_{n}/s_{n}\right)}$
(23) $\displaystyle=\tilde{\rho}_{p,f_{n}}(s_{n}/|B_{n}|)+o(1)$ (24)

where the second inequality utilised the monotonicity of $h$. The stated
result now follows. ∎

###  3.2 Randomised bit-query algorithms

In this section we discuss a slight variant of [12, theorem 1.8], which
provides an upper bound for $\mathbb{P}(\mathcal{W}_{p,f}=k)$ in terms of
certain properties of a randomised algorithm.

By a “bit querying algorithm”, we picture a procedure which takes as input a
bit string, $x\in S^{B}$, and outputs a subset of bits, $J\subseteq B$, in
such a way that bits are added one-by-one to $J$, and the choice of the next
bit to add can depend on the states in $x$ of the bits already examined. To
make this more precise, we offer the following concrete model.

We define a _query tree_ on $B$ to be a binary tree of depth at least 1, with
its non-leaf vertices labelled from $B$ and its edges labelled from $S$, such
that the following two conditions hold:

  1. (i)

on each root-to-leaf path, each $i\in B$ occurs at most once

  2. (ii)

no vertex has two descendent edges (i.e. edges connecting to descendants) with
the same label

We denote by $\mathcal{Q}_{B}$ the set of all query trees on $B$. By
construction, $\mathcal{Q}_{B}$ is finite. Now let $x\in S^{B}$ and
$t\in\mathcal{Q}_{B}$. If $v\in V(t)$ has label $b_{v}\in B$, then we abuse
notation by writing $x(v):=x(b_{v})$. We define the “query path for $x$ in
$t$” to be the unique path $v_{0},\ldots v_{k}$ in $t$ satisfying:

  1. (i)

$v_{0}$ is the root

  2. (ii)

for each $0\leq i\leq k-1$, the edge $v_{i}v_{i+1}$ has label $x(v_{i})$

  3. (iii)

$v_{k}$ has no descendent edge with label $x(v_{k})$

In words, given $x$, at each step, one looks at the bit in $x$ corresponding
to the current vertex in $t$; if there is an outgoing edge with this label,
traverse it; if not, terminate. Finally, we define $J:\mathcal{Q}_{B}\times
S^{B}\to\mathcal{P}(B)$ so that for each $(t,x)\in\mathcal{Q}_{B}\times
S^{B}$, the image $J(t,x)$ is the set of vertex labels appearing on the query
path for $x$ in $t$.

######  Remark 3.3.

Note that the above definition of a query tree is very closely related to the
notion of a decision tree (see e.g. [18]). However, we emphasise that, unlike
a decision tree, the leaves of a query tree play no special role; in
particular, they are not labelled by the possible output values of any real-
valued function.

We now wish to consider $J$ acting on random elements of $\mathcal{Q}_{B}$ and
$S^{B}$. We begin with some helpful notation. For any $I\subseteq B$ and $x\in
S^{B}$, we denote by $x_{I}$ the restriction of $x$ to $I$; i.e. $x_{I}:I\to
S$ is defined by $x_{I}(i)=x(i)$ for all $i\in I$. Let $\bar{I}:=B\setminus
I$. For any $y\in S^{I}$ and $z\in S^{\bar{I}}$, we define $y\oplus z$ to be
the unique element of $S^{B}$ satisfying

$(y\oplus z)(i)=\begin{cases}y(i),&i\in I,\\\ z(i),&i\in\bar{I}.\end{cases}$
(25)

Finally, if $g:S^{B}\to\mathbb{R}$ then for any $I\subseteq B$ and $y\in
S^{I}$ we define the map $g_{I|y}:S^{B}\to\mathbb{R}$ via

$g_{I|y}(x)=g(y\oplus x_{\bar{I}}),\qquad\text{ for all }x\in S^{B}\;.$ (26)

We are now ready to define the two key quantities that will be used to bound
$\mathbb{P}(\mathcal{W}_{p,f}=k)$.

######  Definition 3.4.

Let $B$ be a finite set, let $\pi$ be a probability measure on $S^{B}$, and
let $\mu$ be a probability measure on $\mathcal{Q}_{B}$. Let $X\sim\pi$ and
$T\sim\mu$ be independent. The _revealment_ of $\mu$ (with respect to $\pi$)
is

$\delta_{\mu,\pi}:=\max_{i\in B}\,\mathbb{P}[J(T,X)\ni i]$ (27)

and for any non-constant $f:S^{B}\to\mathbb{R}$ the _predictability_ of $f$
(with respect to $\mu$ and $\pi$) is

$\epsilon_{\mu,\pi,f}:=\frac{\mathbb{E}[\operatorname{var}_{\pi}(f_{J|X_{J}})]}{\operatorname{var}(f(X))}$
(28)

where $f_{J|X_{J}}$ abbreviates $f_{J(T,X)|X_{J(T,X)}}$, and the notation
$\operatorname{var}_{\pi}(f_{J|X_{J}})$ means that for each fixed realisation
of $(T,X)$, one computes the variance with respect to $\pi$ of the map
$f_{J|X_{J}}:S^{B}\to\mathbb{R}$.

######  Remark 3.5.

We emphasise that since $f_{J|X_{J}}$ is a random map,
$\operatorname{var}_{\pi}(f_{J|X_{J}})$ is a random variable on the space
$(\mathcal{Q}_{B}\times S^{B},\mu\times\pi)$. We also note the bounds
$\delta_{\mu,\pi}>0$, which follows from the requirement that query trees have
depth at least one, and $\epsilon_{\mu,\pi,f}\leq 1$, which is established in
corollary 6.3.

We are now ready to state the following slight variant of the revealment
theorem of [12].

######  Theorem 3.6.

Let $p\in(0,1)$ and let $B$ be a finite set. Let $\pi:=\pi_{p,B}$, and let
$\mu$ be any distribution on $\mathcal{Q}_{B}$. For any non-constant function
$f:S^{B}\to\mathbb{R}$ we have

$\mathbb{P}(\mathcal{W}_{p,f}=k)\leq
2\,\epsilon_{\mu,\pi,f}+2\,\delta_{\mu,\pi}\,k.$

We note that the statement of [12, theorem 1.8] refers specifically to the
case of randomised algorithms which exactly determine $f$, meaning that the
predictability term is identically zero. A generalisation to randomised
algorithms which instead merely approximate $f$ is, however, presented in [12,
equation (2.5)]. Our use of query trees is intended simply to provide a
concrete model for these randomised approximation schemes, where the focus is
shifted away from approximating $f$, to simply constructing a rule determining
the set of queried bits. We also note that [12, theorem 1.8] and [12, equation
(2.5)] only refer to the special case that $p=1/2$, however the generalisation
to arbitrary $p\in(0,1)$ is straightforward. For completeness, we present a
full proof of theorem 3.6 in section 6.

Combining theorem 3.6 with lemma 3.2 provides the following proposition, which
is the main tool applied in section 5. In short, it reduces the problem of
bounding $\tau_{p,f}$ and $\rho_{p,f}(s)$ to the problem of constructing a
distribution $\mu$ on $\mathcal{Q}_{B}$ for which the revealment and
predictability both vanish sufficiently fast as $|B|$ increases.

######  Proposition 3.7.

Let $p\in(0,1)$ and let $B$ be a finite set with $n:=|B|>1$. Let
$\pi:=\pi_{p,B}$, and let $\mu$ be any distribution on $\mathcal{Q}_{B}$. For
any non-constant function $f:S^{B}\to\mathbb{R}$ we have

$\tau_{p,f}\leq
5\,n\,\log(n)\,\epsilon_{\mu,\pi,f}+3\,n\sqrt{\delta_{\mu,\pi}}\;,$ (29)

and

$\rho_{p,f}(\left\lceil n\,t\right\rceil)\leq
2\left(\frac{\epsilon_{\mu,\pi,f}}{t}+\frac{\delta_{\mu,\pi}}{t^{2}}\right)\;,\qquad\text{
for all }t\in(0,\infty)\;.$ (30)

###### Proof.

For any $a_{n}\geq 1$, we have from theorem 3.6 that

$\displaystyle\mathbb{E}(\mathcal{W}_{p,f}^{-1})$ $\displaystyle\leq
2\epsilon_{\mu,\pi,f}\sum_{k=1}^{\lfloor a_{n}\wedge
n\rfloor}\frac{1}{k}+2\delta_{\mu,\pi}(\lfloor a_{n}\rfloor\wedge
n)+\frac{1}{a_{n}}$ (31) $\displaystyle\leq
5\,\log(n)\,\epsilon_{\mu,\pi,f}+2\delta_{\mu,\pi}\,a_{n}+a_{n}^{-1}$ (32)

where in obtaining the second inequality we used the fact (see e.g. [19,
equation (6.60)]) that for all $n\geq 2$

$\sum_{k=1}^{n}\frac{1}{k}\leq\frac{5}{2}\log(n)\;.$ (33)

The first stated result then follows by choosing
$a_{n}=1/\sqrt{\delta_{\mu,\pi}}$ and applying lemma 3.2.

Moreover, theorem 3.6 implies that for all $t\geq 0$

$\displaystyle\mathbb{E}(\rme^{-t\,\mathcal{W}_{p,f}})$ $\displaystyle\leq
2\epsilon_{\mu,\pi,f}\sum_{k=1}^{n}\rme^{-t\,k}+2\delta_{\mu,\pi}\sum_{k=1}^{n}k\,\rme^{-t\,k}$
(34) $\displaystyle\leq
2\epsilon_{\mu,\pi,f}\,\frac{1}{\rme^{t}-1}+2\delta_{\mu,\pi}\,\frac{\rme^{t}}{(\rme^{t}-1)^{2}}$
(35)
$\displaystyle=\frac{2\epsilon_{\mu,\pi,f}}{t}+\frac{2\delta_{\mu,\pi}}{t^{2}}\;.$
(36)

But from lemma 3.2, and the fact that $1-x\leq\rme^{-x}$ for all
$x\in\mathbb{R}$, we have

$\displaystyle\rho_{p,f}(\left\lceil nt\right\rceil)$
$\displaystyle\leq\mathbb{E}\left(1-\frac{\mathcal{W}_{p,f}}{n}\right)^{nt}$
(37) $\displaystyle\leq\mathbb{E}(\rme^{-t\mathcal{W}_{p,f}})$ (38)

which establishes the second stated result. ∎

##  4 Binary Trees

We now prove proposition 2.2. For $n\in\mathbb{Z}_{+}$, let $(V_{n},B_{n})$
denote the perfect binary tree of depth $n$, and let $o$ denote its root. For
$p\in(0,1)$, we consider discrete-time dynamical percolation on
$(V_{n},B_{n})$, and let $f_{n}$ denote the size of the cluster containing
$o$. To simplify notation, we denote variance with respect to $\pi_{p,B_{n}}$
by $\operatorname{var}_{p}(\cdot)$, and set
$\mathcal{W}_{p,n}:=\mathcal{W}_{p,f_{n}}$. Lemma 4.1 presents a simple exact
expression for the distribution of $\mathcal{W}_{p,n}$, valid for all $n$.

######  Lemma 4.1.

Let $n\in\mathbb{Z}_{+}$ and $p\in(0,1)$. For all $k\in[B_{n}]$ we have

$\operatorname{var}_{p}(f_{n})\,\mathbb{P}(\mathcal{W}_{p,n}=k)=\nu_{p}^{2k}\,\sum_{d=1}^{n}\binom{d-1}{k-1}\,2^{d}\,g_{p,n}(d)$

where $g_{p,n}:[n]\to\mathbb{R}$ is given by

$g_{p,n}(d):=\begin{cases}p^{2d}\left[\dfrac{1-(2p)^{n+1-d}}{1-2p}\right]^{2},&\text{
if }p\neq 1/2,\\\ 2^{-2d}\,(n+1-d)^{2},&\text{ if }p=1/2.\end{cases}$

###### Proof.

Fix $n\in\mathbb{Z}_{+}$ and $p\in(0,1)$, and let $A\subseteq B_{n}$ be non-
empty. To simplify notation, we abbreviate $\langle.,.\rangle_{p,B_{n}}$ by
$\langle.,.\rangle$ and set $\Psi_{A}:=\Psi_{A}^{p,B_{n}}$. We begin by
finding an expression for the coefficient $\langle f_{n},\Psi_{A}\rangle$. For
$v\in V_{n}$, let $\mathcal{P}_{v}$ denote the edge set of the unique path in
$(V_{n},B_{n})$ between $o$ and $v$, and let $\delta_{v}$ be the depth of $v$.
Then $v\leftrightarrow o$ iff every $e\in\mathcal{P}_{v}$ is open. Therefore,
for all $x\in S^{B_{n}}$ we have

$f_{n}(x)=\sum_{v\in
V_{n}}\prod_{e\in\mathcal{P}_{v}}\left(\frac{1+x_{e}}{2}\right)\;.$ (39)

It follows that, if $X$ denotes a random element of $B_{n}$ with distribution
$\pi_{p,B_{n}}$, then

$\begin{split}\langle f_{n},\Psi_{A}\rangle&=\mathbb{E}\left(\sum_{v\in
V_{n}}\prod_{e\in\mathcal{P}_{v}}\left(\frac{1+X_{e}}{2}\right)\prod_{g\in
A}X_{g}\,\nu_{p}^{X_{g}}\right)\\\ &=\sum_{v\in
V_{n}}\prod_{e\in\mathcal{P}_{v}\setminus
A}\mathbb{E}\left(\frac{1+X_{e}}{2}\right)\prod_{g\in
A\setminus\mathcal{P}_{v}}\mathbb{E}(X_{g}\,\nu_{p}^{X_{g}})\\\
&\qquad\times\prod_{h\in
A\cap\mathcal{P}_{v}}\left(\frac{\mathbb{E}(X_{h}\,\nu_{p}^{X_{h}})}{2}+\frac{\mathbb{E}(X_{h}^{2}\,\nu_{p}^{X_{h}})}{2}\right)\\\
&=\sum_{v\in V_{n}}\,p^{|\mathcal{P}_{v}\setminus
A|}\,(\sqrt{p(1-p)})^{|A\cap\mathcal{P}_{v}|}\,\mathbf{1}(A\setminus\mathcal{P}_{v}=\emptyset)\\\
&=\nu_{p}^{|A|}\,\sum_{v\in V_{n}}\mathbf{1}(\mathcal{P}_{v}\supseteq
A)\,p^{\delta_{v}}\;,\end{split}$ (40)

where we used the fact that for any $e\in B_{n}$ we have

$\begin{split}\mathbb{E}_{p}(X_{e}\,\nu_{p}^{X_{e}})&=0\;,\\\
\mathbb{E}_{p}(X_{e}^{2}\,\nu_{p}^{X_{e}})&=2\sqrt{p(1-p)}\;.\end{split}$ (41)

Now let

$\mathcal{S}_{n}:=\\{A^{\prime}\subseteq B_{n}\,:\,\exists v\in V_{n}\text{
with }\mathcal{P}_{v}\supseteq A^{\prime}\\}\;,$ (42)

and

$d_{A}:=\max\\{\delta_{v}\,:\,v\in V_{n}\text{ and }\exists u\in V_{n}\text{
with }A\ni uv\\}\;.$ (43)

If $A\not\in\mathcal{S}_{n}$, then equation (40) implies $\langle
f_{n},\Psi_{A}\rangle=0$. Assume instead that $A\in\mathcal{S}_{n}$, and let
$v_{A}\in V_{n}$ be the (unique) deepest endpoint of the edges in $A$. Then
$\mathcal{P}_{w}\supseteq A$ for $w\in V_{n}$ iff
$\mathcal{P}_{w}\supseteq\mathcal{P}_{v_{A}}$. For each $d_{A}+1\leq k\leq n$,
there are $2^{k-d_{A}}$ descendants of $v_{A}$ at depth $k$. Therefore,
equation (40) implies

$\begin{split}\langle
f_{n},\Psi_{A}\rangle&=\mathbf{1}(A\in\mathcal{S}_{n})\,\nu_{p}^{|A|}\,p^{d_{A}}\,\sum_{k=0}^{n-d_{A}}(2p)^{k}\\\
&=\mathbf{1}(A\in\mathcal{S}_{n})\,\begin{cases}\nu_{p}^{|A|}\,p^{d_{A}}\dfrac{1-(2p)^{n-d_{A}+1}}{1-2p},&p\neq
1/2\;,\\\ 2^{-d_{A}}(n-d_{A}+1),&p=1/2\;.\end{cases}\end{split}$ (44)

It then follows from equation (44) that

$\langle
f_{n},\Psi_{A}\rangle^{2}=\nu_{p}^{2|A|}\,g_{p,n}(d_{A})\,\mathbf{1}(A\in\mathcal{S}_{n})\;.$
(45)

Finally, from equation (45) we conclude that for any $k\in[B_{n}]$

$\displaystyle\sum_{A\in\binom{B_{n}}{k}}\,\langle f_{n},\Psi_{A}\rangle^{2}$
$\displaystyle=\sum_{d=1}^{n}\,\sum_{\begin{subarray}{c}v\in V_{n}\\\
\delta_{v}=d\end{subarray}}\,\sum_{\begin{subarray}{c}A\in\mathcal{S}_{n}\\\
|A|=k,\,v_{A}=v\end{subarray}}\,\nu_{p}^{2k}\,g_{p,n}(d)$ (46)
$\displaystyle=\nu_{p}^{2k}\,\sum_{d=1}^{n}\,2^{d}\,\binom{d-1}{k-1}\,g_{p,n}(d)\;.$
(47)

The stated result now follows from equation (14). ∎

Armed with lemma 4.1, we can now prove proposition 2.2.

###### Proof of proposition 2.2..

Asymptotic statements here refer to the limit $n\to\infty$ with $p$ fixed. We
begin by proving part (i). To that end, let $z\in[0,1]$. From lemma 4.1 we
have for any $p\in(0,1)$ that

$\begin{split}\operatorname{var}_{p}(f_{n})\,\mathbb{E}(z^{\mathcal{W}_{p,n}})&=\sum_{k\in[B_{n}]}\,z^{k}\,\nu_{p}^{2k}\,\sum_{d=1}^{n}\,2^{d}\,\binom{d-1}{k-1}\,g_{p,n}(d)\\\
&=\frac{z\,\nu_{p}^{2}}{1+z\,\nu_{p}^{2}}\,\sum_{d=1}^{n}\,2^{d}\,(1+z\,\nu_{p}^{2})^{d}\,g_{p,n}(d)\;.\end{split}$
(48)

For $p\neq 1/2$ it then follows that

$\operatorname{var}_{p}(f_{n})\,\mathbb{E}(z^{\mathcal{W}})=\frac{z\,\nu_{p}^{2}}{(1+z\,\nu_{p}^{2})(1-2p)^{2}}\,\sum_{d=1}^{n}\,[2p^{2}(1+z\,\nu_{p}^{2})]^{d}\,[1-(2p)^{n+1-d}]^{2}\;.$
(49)

Now suppose $z_{n}\in[0,1]$ is a convergent sequence, and set
$z_{\infty}:=\lim_{n\to\infty}z_{n}$. If $p\in(0,1/2)$, so that $(2p)^{n}$ is
exponentially decaying for large $n$, we have

$\lim_{n\to\infty}\,\operatorname{var}_{p}(f_{n})\,\mathbb{E}(z_{n}^{\mathcal{W}_{p,n}})=\frac{z_{\infty}\,\nu_{p}^{2}}{(1+z_{\infty}\,\nu_{p}^{2})(1-2p)^{2}}\frac{2p^{2}(1+z_{\infty}\,\nu_{p}^{2})}{[1-2p^{2}(1+z_{\infty}\,\nu_{p}^{2})]}\;,$
(50)

while if $p\in(1/2,1)$, so that $(2p)^{n}$ is exponentially increasing in $n$,
we have

$\lim_{n\to\infty}\,(2p)^{-2n}\,\operatorname{var}_{p}(f_{n})\,\mathbb{E}(z_{n}^{\mathcal{W}_{p,n}})=\frac{z_{\infty}\,\nu_{p}^{2}}{(1+z_{\infty}\,\nu_{p}^{2})(2p-1)^{2}}\frac{4p^{2}(1+z_{\infty}\,\nu_{p}^{2})}{[1-z_{\infty}\,\nu_{p}^{2}]}\;.$
(51)

In particular, taking $z_{n}=1$ and employing the identity $1+\nu_{p}^{2}=1/p$
yields

$\operatorname{var}_{p}(f_{n})\sim\begin{cases}\dfrac{2p(1-p)}{(1-2p)^{3}},&p\in(0,1/2),\vspace{2mm}\\\
\dfrac{4p^{2}(1-p)}{(2p-1)^{3}}\,(2p)^{2n},&p\in(1/2,1).\end{cases}$ (52)

Taking instead $z_{n}=\rme^{-t_{n}}$ implies $z_{\infty}=1$ when $t_{n}=o(1)$,
and $z_{\infty}=0$ when $t_{n}=\omega(1)$, and so equations (50), (51) and
(52) imply that for $p\neq 1/2$ we have

$\lim_{n\to\infty}\,\mathbb{E}(\rme^{-t_{n}\mathcal{W}_{p,n}})=\begin{cases}1,&t_{n}=o(1),\\\
0,&t_{n}=\omega(1).\end{cases}$ (53)

Now let $s_{n}$ be a positive integer sequence, and set $t_{n}=s_{n}/|B_{n}|$.
If $s_{n}=\omega(|B_{n}|)$ then combining equation (53) with lemmas 2.1 and
3.2 implies

$\lim_{n\to\infty}\,\rho_{p,f_{n}}(s_{n})=0\;.$ (54)

Suppose instead that $s_{n}=o(|B_{n}|)$. If $s_{n}=\omega(1)$, then combining
equation (53) with lemmas 2.1 and 3.2 implies

$\lim_{n\to\infty}\,\rho_{p,f_{n}}(s_{n})=1\;.$ (55)

If $s_{n}$ is instead bounded, then we can bound it above by $s_{n}^{\prime}$
satisfying $s_{n}^{\prime}=\omega(1)$ and $s_{n}^{\prime}=o(|B_{n}|)$. By then
applying equation (55) with $s_{n}$ replaced by $s_{n}^{\prime}$, together
with the fact that $\rho_{p,f_{n}}(s)$ is decreasing in $s$, and bounded above
by 1, we see that in fact equation (55) also holds for bounded $s_{n}$. We
have therefore established part (i).

We now consider part (ii). From equation (48) we have for $z\in[0,1]$ that

$\operatorname{var}_{1/2}(f_{n})\,\mathbb{E}(z^{\mathcal{W}_{1/2,n}})=\frac{z}{2}\,\sum_{j=1}^{n}\,j^{2}\,\left(\frac{1+z}{2}\right)^{n-j}\;.$
(56)

Taking $z=1$ in equation (56) immediately yields

$\operatorname{var}_{1/2}(f_{n})=\frac{n(n+1)(2n+1)}{12}\;,$ (57)

and it then follows that for $z\in[0,1)$

$\mathbb{E}(z^{\mathcal{W}_{1/2,n}})=\frac{12}{(1+n^{-1})(2+n^{-1})}\left(\frac{z}{n(1-z)}-2\frac{z(1+z)}{n^{2}(1-z)^{2}}\right.\\\
\left.+\frac{z(1+z)(3+z)}{n^{3}(1-z)^{3}}\left[1-\left(\frac{1+z}{2}\right)^{n}\right]\right)\;.$
(58)

In particular, if $z=\rme^{-t_{n}}$ with $t_{n}>0$ and $t_{n}\to
c\in(0,+\infty]$, then

$\lim_{n\to\infty}\mathbb{E}(\rme^{-t_{n}\mathcal{W}_{1/2,n}})=0\;.$ (59)

Suppose instead that $t:=t_{n}=o(1)$. It then follows from equation (58) that

$\displaystyle\mathbb{E}(\rme^{-t\mathcal{W}_{1/2,n}})$
$\displaystyle=\frac{12}{(1+n^{-1})(2+n^{-1})}\left[\frac{t}{(\rme^{t}-1)}\frac{1}{nt}-2\frac{t^{2}(\rme^{t}+1)}{(\rme^{t}-1)^{2}}\frac{1}{(nt)^{2}}\right.$
$\displaystyle\left.\quad+\frac{t^{3}(\rme^{t}+1)(3\rme^{t}+1)}{(\rme^{t}-1)^{3}}\frac{1}{(nt)^{3}}\left[1-\left(\frac{1+\rme^{-t}}{2}\right)^{n}\right]\right]$
(60)
$\displaystyle=\frac{12}{(1+n^{-1})(2+n^{-1})}\left(\frac{1}{nt}[1+O(t)]-2\frac{1}{(nt)^{2}}[2-t+O(t^{2})]\right.$
$\displaystyle\left.\quad+\frac{1}{(nt)^{3}}[8-2t+O(t^{2})]\left[1-\left(\frac{1+\rme^{-t}}{2}\right)^{n}\right]\right)\;,$
(61)

where in performing the above Taylor approximation it is helpful to recall
that $t/(\rme^{t}-1)$ is the exponential generating function of the Bernoulli
numbers (see e.g. [19]). If $t=\omega(n^{-1})$ it now follows immediately from
equation (61) that

$\lim_{n\to\infty}\mathbb{E}(\rme^{-t_{n}\,\mathcal{W}_{1/2,n}})=0\;.$ (62)

Conversely, now suppose that $t=o(n^{-1})$. Then

$1-\left(\frac{1+\rme^{-t}}{2}\right)^{n}=\frac{nt}{2}-\frac{(nt)^{2}}{8}-\frac{nt^{2}}{8}+\frac{(nt)^{3}}{48}+O[n^{2}t^{3}\vee(nt)^{4}]\;,$
(63)

and so the last term in equation (61) satisfies, as $n\to\infty$,

$\frac{1}{(nt)^{3}}[8-2t+O(t^{2})]\left[1-\left(\frac{1+\rme^{-t}}{2}\right)^{n}\right]=\frac{4}{(nt)^{2}}-\frac{1}{nt}-\frac{2}{n^{2}t}+\frac{1}{6}+o(1)\;.$
(64)

Combining equation (64) with equation (61) then yields

$\lim_{n\to\infty}\mathbb{E}(\rme^{-t\mathcal{W}_{1/2,n}})=1\;,$ (65)

We have therefore established that

$\lim_{n\to\infty}\,\mathbb{E}(\rme^{-t_{n}\mathcal{W}})=\begin{cases}1,&t_{n}=o(n^{-1})\\\
0,&t_{n}=\omega(n^{-1}).\end{cases}$ (66)

Just as part (i) was shown above to follow from (53), a precisely analogous
argument shows that part (ii) follows from (66).

Finally, we turn attention to part (iii). From lemma 4.1 we have for any
$p\in(0,1)$ that

$\displaystyle\operatorname{var}_{p}(f_{n})\,\mathbb{E}(\mathcal{W}_{p,n}^{-1})$
$\displaystyle=\sum_{d=1}^{n}\,2^{d}\,g_{p}(d)\,\sum_{k=1}^{d}\,\binom{d-1}{k-1}\frac{\nu_{p}^{2k}}{k}$
(67)
$\displaystyle=\sum_{d=1}^{n}\,2^{d}\,g_{p}(d)\,\left(\frac{p^{-d}-1}{d}\right)\;.$
(68)

Suppose $p\neq 1/2$. It follows from equation (68) that

$(1-2p)^{2}\,\operatorname{var}_{p}(f_{n})\,\mathbb{E}(\mathcal{W}_{p,n}^{-1})\\\
=\sum_{d=1}^{n}\,\frac{1}{d}\left[(2p)^{d}+(2p)^{2n+2-d}-2(2p)^{n+1}-(2p^{2})^{d}-(2p)^{2n+2}2^{-d}+2(2p)^{n+1}p^{d}\right]\;.$
(69)

Now observe that for any $x\in(0,1)$ we have

$\sum_{d=1}^{\infty}\frac{x^{d}}{d}=-\log(1-x)\;.$ (70)

Equations (69) and (70) then imply that for $p\in(0,1/2)$ we have

$\lim_{n\to\infty}(1-2p)^{2}\,\operatorname{var}_{p}(f_{n})\,\mathbb{E}(\mathcal{W}_{p,n}^{-1})=\log(1-2p^{2})-\log(1-2p)\;,$
(71)

while for $p\in(1/2,1)$ we have

$\lim_{n\to\infty}(2p)^{-2n-2}(1-2p)^{2}\,\operatorname{var}_{p}(f_{n})\,\mathbb{E}(\mathcal{W}_{p,n}^{-1})=\log\left(\frac{2p}{2p-1}\right)-\log(2)\;.$
(72)

In the critical case, equation (68) yields

$\displaystyle\operatorname{var}_{1/2}(f_{n})\,\mathbb{E}(\mathcal{W}_{1/2,n}^{-1})$
$\displaystyle=\sum_{d=1}^{n}\frac{(n+1-d)^{2}}{d}(1-2^{-d})$ (73)
$\displaystyle=n^{2}\log(n)+O(n^{2})\;.$ (74)

Part (iii) then follows by combining equations (52), (71), and (72), and
equations (57) and (74), with part (ii) of lemma 3.2. ∎

##  5 High-dimensional tori

In this section we will prove proposition 2.3. To that end, let
$d,L\in\mathbb{Z}_{+}$ with $L\geq 3$. For $p\in(0,1)$, we consider discrete-
time dynamical percolation on $\mathbb{T}^{d}_{L}$. Let
$B_{L}:=E(\mathbb{T}^{d}_{L})$. We denote expectation and variance with
respect to $\pi_{p,B_{L}}$ by $\mathbb{E}_{p}$ and $\operatorname{var}_{p}$.
Let $C_{L}$ denote the cluster containing the origin, so that
$f_{d,L}=|C_{L}|$. To simplify notation we set
$\mathcal{W}_{p,L}:=\mathcal{W}_{p,f_{d,L}}$, $\tau_{p,L}:=\tau_{p,f_{d,L}}$,
$\tilde{\rho}_{p,L}:=\tilde{\rho}_{p,f_{d,L}}$ and
$\rho_{p,L}:=\rho_{p,f_{d,L}}$, and for all $A\subseteq B_{L}$ we set
$\Psi_{A}:=\Psi_{A}^{p,B_{L}}$. To avoid conflict with the subscripts required
when applying theorem 3.6, we shall also henceforth abbreviate $f:=f_{d,L}$.

It will be helpful on occasion to relate bond percolation on
$\mathbb{T}^{d}_{L}$ to bond percolation on $\mathbb{Z}^{d}$. We shall denote
the probability measure and expectation with respect to the latter by
$\mathbb{P}_{p,\mathbb{Z}^{d}}$ and $\mathbb{E}_{p,\mathbb{Z}^{d}}$. We view
$\mathbb{Z}^{d}$ as a graph in which vertices of Euclidean distance 1 are
adjacent, and we make no notational distinction between this graph and its
vertex set. For bond percolation on $\mathbb{Z}^{d}$ we shall denote the
cluster containing the origin by $C_{\mathbb{Z}^{d}}$.

###### Proof of proposition 2.3.

Asymptotic statements here refer to the limit $L\to\infty$, for fixed values
of $p$ and $d$, and implied constants may in general depend on $p$ and $d$. We
first consider the subcritical case, and therefore fix
$p\in(0,p_{\mathrm{c}})$. Let $e\in B_{L}$ denote the edge from the origin to
the unit vector $(1,0,\ldots,0)$ on the positive $x$ axis. Then from equation
(14) we have

$\mathbb{E}(\mathcal{W}_{p,L}^{-1})=\sum_{k\in[B_{L}]}\,\frac{1}{k}\,\sum_{A\in\binom{B_{L}}{k}}\,\frac{\langle
f,\Psi_{A}\rangle^{2}}{\operatorname{var}_{p}(f)}\geq\frac{\langle
f,\Psi_{e}\rangle^{2}}{\operatorname{var}_{p}(f)}\;,$ (75)

and for any $t\geq 0$

$\mathbb{E}(\rme^{-t\,\mathcal{W}_{p,L}})=\sum_{k\in[B_{L}]}\,\rme^{-t\,k}\,\sum_{A\in\binom{B_{L}}{k}}\,\frac{\langle
f,\Psi_{A}\rangle^{2}}{\operatorname{var}_{p}(f)}\geq\frac{\langle
f,\Psi_{e}\rangle^{2}}{\operatorname{var}_{p}(f)}\,\rme^{-t}\;.$ (76)

We begin by lower bounding $\langle f,\Psi_{e}\rangle^{2}$. Employing the
notation of equation (25), with $I=\\{e\\}$, we have

$\displaystyle\langle f,\Psi_{e}\rangle$ $\displaystyle=\sum_{\omega\in
S^{B_{L}\setminus e}}\,\pi_{p,B_{L}\setminus e}(\omega)\,\sum_{a\in
S^{e}}\pi_{p}(a)\,a\,\nu_{p}^{a}\,f(a\oplus\omega)$ (77)
$\displaystyle=\sum_{\omega\in S^{B_{L}\setminus e}}\,\pi_{p,B_{L}\setminus
e}(\omega)\,\sum_{a\in S^{e}}\sqrt{p(1-p)}\,a\,\,f(a\oplus\omega)$ (78)
$\displaystyle=\sqrt{p(1-p)}\sum_{\omega\in S^{B_{L}\setminus
e}}\,\pi_{p,B_{L}\setminus
e}(\omega)\,\left[f(\omega^{e})-f(\omega_{e})\right]$ (79)

where for $\omega\in S^{B_{L}\setminus e}$ we define $\omega^{e},\omega_{e}\in
S^{B_{L}}$ so that $\omega^{e}(e)=+1$ and $\omega_{e}(e)=-1$, while
$\omega^{e}(e^{\prime})=\omega_{e}(e^{\prime})=\omega(e^{\prime})$ for all
$e^{\prime}\in B_{L}\setminus e$.

Now define

$\mathcal{N}:=\\{\omega\in S^{B_{L}\setminus
e}\;:\;\omega(e^{\prime})=-1\text{ for all }e^{\prime}\in E\setminus e\text{
such that $0$ is an endpoint of $e^{\prime}$}\\}\;.$ (80)

Observe that for all $\omega\in S^{B_{L}\setminus e}$ we have
$f(\omega^{e})\geq f(\omega_{e})$, while if $\omega\in\mathcal{N}$ we have
$f(\omega^{e})\geq 2$ and $f(\omega_{e})=1$. Also observe that
$\pi_{p,B_{L}}(\mathcal{N})=(1-p)^{2d-1}$. It follows that

$\langle f,\Psi_{e}\rangle\geq\sqrt{p(1-p)}\,(1-p)^{2d-1}\;.$ (81)

We can also find a constant order upper bound for $\operatorname{var}_{p}(f)$,
as follows. We begin with

$\operatorname{var}_{p}(f)\leq\mathbb{E}_{p}(|C_{L}|^{2})\;.$ (82)

But it follows from [20, proposition 2.1] that

$\mathbb{E}_{p}(|C_{L}|^{2})\leq\mathbb{E}_{p,\mathbb{Z}^{d}}(|C_{\mathbb{Z}^{d}}|^{2})\;,$
(83)

and the behaviour of $|C_{\mathbb{Z}^{d}}|$ when $p<p_{\mathrm{c}}$ is well
understood. In particular, it is known (see e.g. [21, theorem 6.75]) that for
all $p<p_{\mathrm{c}}$, there exists $\lambda_{p}>0$ such that for all $n\geq
1$

$\mathbb{P}_{p,\mathbb{Z}^{d}}(|C_{\mathbb{Z}^{d}}|\geq
n)\leq\rme^{-\lambda_{p}n}\;.$ (84)

Consequently,

$\mathbb{E}_{p,\mathbb{Z}^{d}}(|C_{\mathbb{Z}^{d}}|^{2})\leq\sum_{n=1}^{\infty}n^{2}\,\rme^{-\lambda_{p}n}\leq\frac{\rme^{\lambda_{p}}(\rme^{\lambda_{p}}+1)}{(\rme^{\lambda_{p}}-1)^{3}}<\infty\;.$
(85)

It then follows from equations (81), (82), (83) and (85) that for all
$0<p<p_{\mathrm{c}}$ we have

$\frac{\langle f,\Psi_{e}\rangle^{2}}{\operatorname{var}_{p}(f)}\geq
p(1-p)^{4d-1}\,\frac{(\rme^{\lambda_{p}}-1)^{3}}{\rme^{\lambda_{p}}(\rme^{\lambda_{p}}+1)}>0\;.$
(86)

Combining equations (75) and (86) with lemma 3.2 then implies that
$\tau_{p,L}=\Omega(|B_{L}|)$, so we conclude from remark 3.1 that in fact
$\tau_{p,L}=\Theta(|B_{L}|)$. Similarly, if $s_{L}$ is an integer sequence
with $s_{L}=o(|B_{L}|)$, then combining equations (76) and (86) with lemma 3.2
implies $\tilde{\rho}_{p,L}(s_{L}/|B_{L}|)=\Omega(1)$. For $s_{L}$ satisfying
$s_{L}=o(|B_{L}|)$ and $s_{L}=\omega(1)$ we can then conclude from lemma 2.1
that $\rho_{p,L}(s_{L})=\Omega(1)$, and monotonicity then implies that in fact
$\rho_{p,L}(s_{L})=\Omega(1)$ for any $s_{L}=o(|B_{L}|)$. But
$\rho_{p,L}(s)\leq 1$ for any $s\in\mathbb{N}$, and so in fact
$\rho_{p,L}(s_{L})=\Theta(1)$.

We now turn attention to the critical case of $p=p_{\mathrm{c}}$. Our strategy
is to describe a distribution on $\mathcal{Q}_{B_{L}}$, and then apply theorem
3.6. For concreteness, we impose the lexicographic ordering on the vertices of
$\mathbb{Z}^{d}$. For $r\in\mathbb{Z}_{+}$, we denote the cube in
$\mathbb{Z}^{d}$ of radius $r$ centred at $v\in\mathbb{Z}^{d}$ by

$\mathbb{B}^{d}_{r}(v):=\\{y\in\mathbb{Z}^{d}:\|y-v\|_{\infty}\leq r\\}\;,$
(87)

where $\|\cdot\|_{\infty}$ denotes the sup norm on $\mathbb{R}^{d}$. We
abbreviate $\mathbb{B}^{d}_{r}:=\mathbb{B}^{d}_{r}(0)$. We fix
$\kappa\in(0,1)$, and define the sequences $a:=\left\lfloor
L^{\kappa}\right\rfloor$ and $b:=\left\lfloor L^{\kappa/3}\right\rfloor$. For
$r\in[a]$, we consider the subgraph of $\mathbb{Z}^{d}$ induced by
$\mathbb{B}^{d}_{r}$, and let $E_{r}$ denote its edge set. In what follows, we
will assume $L$ is sufficiently large that $a<L/2$, which then guarantees
$\mathbb{B}^{d}_{r}$ is a proper subset of $V(\mathbb{T}^{d}_{L})$.

We construct a query tree as follows. Let $r\in[a]$ and $x\in S^{B_{L}}$, and
consider the subgraph $\mathcal{G}_{r}$ of $\mathbb{B}^{d}_{r}$ corresponding
to $x_{E_{r}}\in S^{E_{r}}$. Beginning at the smallest vertex on the boundary
$\partial\mathbb{B}^{d}_{r}$, perform breadth-first search on
$\mathcal{G}_{r}$. Naive breadth-first search would in principle require as
input the full adjacency list of $\mathcal{G}_{r}$, which would require
querying in advance each edge in $E_{r}$. We instead query just the necessary
edges on the fly as follows. From vertex $v$, query each edge $uv\in E_{r}$
which has not been previously queried, then mark $uv$ as queried. If
$x_{uv}=1$, add $u$ to the adjacency list of $v$ and vice versa. Once the
breadth-first search from a given point in $\partial\mathbb{B}^{d}_{r}$ has
terminated, start a new breadth-first search from the next smallest vertex in
$\partial\mathbb{B}^{d}_{r}$ which has not previously been visited by a
breadth-first search. When this process terminates, the set of edges which
have been queried consists precisely of those edges in $E_{r}$ which have at
least one endpoint belonging to a component in $\mathcal{G}_{r}$ that is
connected to $\partial\mathbb{B}^{d}_{r}$. Let $J_{1}$ denote the set of these
edges.

At the conclusion of the above process it will be known whether or not
$0\leftrightarrow\partial\mathbb{B}^{d}_{r}$; in particular,
$0\leftrightarrow\partial\mathbb{B}^{d}_{r}$ holds iff $J_{1}$ contains an
edge incident to the origin which is open. If
$0\leftrightarrow\partial\mathbb{B}^{d}_{r}$, then the above breadth-first
search procedure is recommenced from the vertices on
$\partial\mathbb{B}^{d}_{r}$ which are connected to $0$, but now with respect
to all edges in $\mathbb{T}^{d}_{L}$. Therefore, if
$0\leftrightarrow\partial\mathbb{B}^{d}_{r}$, then the component of $x$
containing $0$ will be determined exactly. The set of edges queried in this
second step is precisely all those edges in $B_{L}\setminus E_{r}$ which have
at least one endpoint in the component of $x$ containing $0$. We denote this
set by $J_{2}$. If $0\not\leftrightarrow\partial\mathbb{B}^{d}_{r}$, then
$J_{2}=\emptyset$. The total set of edges queried in the above two-stage
process is therefore $J=J_{1}\cup J_{2}$. Note that each edge in $B_{L}$ is
queried at most once. For any fixed $r\in[a]$, the above procedure defines a
deterministic query tree on $B_{L}$, which we denote by $t_{r}$.

Now let $\mathcal{R}$ be a uniformly random element of $[a]$, and let
$\mathcal{T}:=t_{\mathcal{R}}$. Denote the distribution of $\mathcal{T}$ by
$\mu$, and let $X$ be independent of $\mathcal{T}$ with distribution
$\pi:=\pi_{p_{\mathrm{c}},B_{L}}$. We will bound the predictability and
revealment corresponding to $\mu$ and $\pi$. We begin by considering the
predictability. By construction, on the event
$0\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}}$, the set of queried
bits, $J$, is sufficiently large that $f_{J|X_{J}}$ is a constant function of
the bits in $B_{L}\setminus J$, so that
$\operatorname{var}_{\pi}(f_{J|X_{J}})=0$. While on
$0\not\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}}$, the set of queried
bits, $J=J_{1}$, contains a cut-set of closed edges in $E_{\mathcal{R}}$ which
separates the union of the components connected to
$\partial\mathbb{B}^{d}_{\mathcal{R}}$, from a set
$V_{0}\subset\mathbb{B}^{d}_{\mathcal{R}}$ containing the origin. Therefore,
on $0\not\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}}$, regardless of
the values taken by $X$ on $B_{L}\setminus J$ we have
$f_{J|X_{J}}<|\mathbb{B}^{d}_{\mathcal{R}}|=\mathcal{R}^{d}$, and so
$\operatorname{var}_{\pi}(f_{J|X_{J}})\leq\mathcal{R}^{2d}$. It follows that

$\displaystyle\mathbb{E}\left(\operatorname{var}_{\pi}(f_{J|X_{J}})\right)$
$\displaystyle=\mathbb{E}\left(\operatorname{var}_{\pi}(f_{J|X_{J}})\mathbf{1}(0\not\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}})\right)$
(88)
$\displaystyle\leq\sum_{r\in[a]}\,\mathbb{E}\left(r^{2d}\,\mathbf{1}(0\not\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}})\mathbf{1}(\mathcal{R}=r)\right)$
(89) $\displaystyle\leq\sum_{r\in[a]}\,r^{2d}\,\mathbb{P}(\mathcal{R}=r)$ (90)
$\displaystyle\leq\frac{1}{a}\int_{0}^{a+1}t^{2d}\,\mathrm{d}t$ (91)
$\displaystyle\ll L^{2\,d\,\kappa}\;.$ (92)

To lower bound $\operatorname{var}(f(X))$, we begin by noting that Chebyshev’s
inequality implies that

$\operatorname{var}(f(X))\geq\chi^{2}\,\mathbb{P}[f(X)\geq 2\,\chi]\;,$ (93)

where $\chi:=\mathbb{E}(f(X))$. But [22, corollary 2.2], which builds upon
results in [23, 24], implies that for sufficiently large $d$ we have

$\chi\gg L^{d/3}\;,$ (94)

and

$\mathbb{P}[f(X)\geq 2\,\chi]\gg L^{-d/6}\;.$ (95)

Combining equations (94) and (95) with equation (93) then yields

$\operatorname{var}(f(X))\gg L^{d/2}\;.$ (96)

We therefore conclude from equations (92) and (96) that

$\epsilon_{\mu,\pi,f}\ll L^{2d\kappa-d/2}\;.$ (97)

Taking $\kappa<1/4$ implies that $\epsilon_{\mu,\pi,f}=o(1)$.

We now bound the revealment, and begin by considering $J_{1}$. For
$u\in\mathbb{B}^{d}_{a}$, define

$\displaystyle\mathcal{A}_{u}$ $\displaystyle:=\\{r\in[a]:\|u\|_{\infty}\leq
r<\|u\|_{\infty}+b\\}\;,$ (98)

and write $\bar{\mathcal{A}_{u}}:=[a]\setminus\mathcal{A}_{u}$. By
construction, $\mathbb{P}(J_{1}\ni uv)=0$ for all $uv\in
E(\mathbb{T}^{d}_{L})\setminus E_{a}$, and so we instead suppose that $uv\in
E_{a}$. Then

$\displaystyle\mathbb{P}(J_{1}\ni uv)$ $\displaystyle=\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\in\mathcal{A}_{u}\cup\mathcal{A}_{v})+\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\not\in\mathcal{A}_{u}\cup\mathcal{A}_{v})$ (99)
$\displaystyle\leq\mathbb{P}(\mathcal{R}\in\mathcal{A}_{u})+\mathbb{P}(\mathcal{R}\in\mathcal{A}_{v})+\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\in\bar{\mathcal{A}_{u}},\mathcal{R}\in\bar{\mathcal{A}_{v}})$
(100) $\displaystyle\ll L^{-2\kappa/3}+\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\in\bar{\mathcal{A}_{u}},\mathcal{R}\in\bar{\mathcal{A}_{v}})\;.$
(101)

But since, by construction, $\mathcal{R}<\|u\|_{\infty}$ implies $J_{1}\not\ni
uv$, we have

$\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\in\bar{\mathcal{A}_{u}},\mathcal{R}\in\bar{\mathcal{A}_{v}})=\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\geq\|u\|_{\infty}+b,\mathcal{R}\geq\|v\|_{\infty}+b)\;.$ (102)

And since $J_{1}\ni uv$ occurs only if at least one of the events
$u\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}}$ and
$v\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}}$ occur, it then follows
by the union bound that

$\displaystyle\mathbb{P}(J_{1}\ni
uv,\mathcal{R}\in\bar{\mathcal{A}_{u}},\mathcal{R}\in\bar{\mathcal{A}_{v}})$
$\displaystyle\leq
2\max_{w\in\mathbb{B}^{d}_{a}}\,\mathbb{P}(w\leftrightarrow\partial\mathbb{B}^{d}_{\mathcal{R}},\mathcal{R}\geq\|w\|_{\infty}+b)$
(103)
$\displaystyle=2\max_{w\in\mathbb{B}_{a}^{d}}\,\sum_{r=\|w\|_{\infty}+b}^{a}\,\mathbb{P}(w\leftrightarrow\partial\mathbb{B}^{d}_{r})\,\mathbb{P}(\mathcal{R}=r)\;.$
(104)

Let $w\in\mathbb{B}^{d}_{a}$. If $r\geq\|w\|_{\infty}+b$, then
$w\in\mathbb{B}^{d}_{r-b}(0)$, and so
$\mathbb{B}^{d}_{b}(w)\subseteq\mathbb{B}^{d}_{r}(0)$, which implies

$\displaystyle\mathbb{P}(w\leftrightarrow\partial\mathbb{B}^{d}_{r}(0))$
$\displaystyle\leq\mathbb{P}(w\leftrightarrow\partial\mathbb{B}^{d}_{b}(w))$
(105)
$\displaystyle=\mathbb{P}(0\leftrightarrow\partial\mathbb{B}^{d}_{b}(0))$
(106) $\displaystyle\ll\frac{1}{b^{2}}\;,$ (107)

where the second line follows by translational invariance, and the final step
follows from [25, theorem 1] provided $d$ is sufficiently large. Applying the
bound from equation (107) to equation (104), we then conclude from equation
(101) that for all $uv\in B_{L}$ we have

$\mathbb{P}(J_{1}\ni uv)\ll L^{-2\kappa/3}\;.$ (108)

We now consider $J_{2}$. An edge can belong to $J_{2}$ only if it is outside
$\mathbb{B}^{d}_{\mathcal{R}}$ and if at least one of its endpoints is
connected to the origin. It follows that for any $uv\in B_{L}$ we have

$\displaystyle\mathbb{P}(J_{2}\ni uv)$
$\displaystyle\leq\mathbb{P}(\mathcal{R}\leq b)+\mathbb{P}(J_{2}\ni
uv,\mathcal{R}>b)$ (109) $\displaystyle\ll
L^{-2\kappa/3}+\mathbb{P}(\mathcal{R}<\|u\|_{\infty}\vee\|v\|_{\infty},\\{u\leftrightarrow
0\\}\cup\\{v\leftrightarrow 0\\},\mathcal{R}>b)$ (110) $\displaystyle\ll
L^{-2\kappa/3}+\mathbb{P}(b<\mathcal{R}\leq\|u\|_{\infty},u\leftrightarrow
0)+\mathbb{P}(b<\mathcal{R}\leq\|v\|_{\infty},v\leftrightarrow 0)$ (111)
$\displaystyle\ll
L^{-2\kappa/3}+\max_{w\in\mathbb{T}^{d}_{L}}\,\mathbb{P}(b<\mathcal{R}\leq\|w\|_{\infty},w\leftrightarrow
0)$ (112) $\displaystyle\ll
L^{-2\kappa/3}+\max_{\begin{subarray}{c}w\in\mathbb{T}^{d}_{L}\\\
\|w\|_{\infty}>b\end{subarray}}\,\mathbb{P}(w\leftrightarrow 0)$ (113)
$\displaystyle\ll L^{-2\kappa/3}+b^{-(d-2)}+L^{-2d/3}$ (114)

where the final step makes use of [26, corollary 1.4], and is valid for all
sufficiently large $d$. We conclude that for all sufficiently large $d$,

$\mathbb{P}(J_{2}\ni uv)\ll L^{-2\kappa/3}\;.$ (115)

Therefore, since $J=J_{1}\cup J_{2}$, combining equations (108) and (115) we
obtain

$\delta_{\mu,\pi}\ll L^{-2\kappa/3}\;.$ (116)

Finally, combining equations (97) and (116) with equation (29) of proposition
3.7 then implies that for any $\xi>0$

$\frac{\tau_{p_{\mathrm{c}},f}}{L^{d}}\ll
L^{2d\kappa+\xi-d/2}+L^{-\kappa/3}\;.$ (117)

Choosing $\kappa=3(d-2\xi)/2(6d+1)$ and $\xi=(d-2)/26$ then yields

$\frac{\tau_{p_{\mathrm{c}},f}}{L^{d}}\ll L^{-1/13}\;,$ (118)

as required. Similarly, combining equations (97) and (116) with equation (30)
of proposition 3.7, and choosing $\kappa=3d/2(1+6d)$, shows that for all $t>0$
we have

$\rho_{p_{\mathrm{c}},L}(\left\lceil
tL^{d}\right\rceil)\ll\frac{L^{-1/13}}{t}+\left(\frac{L^{-1/13}}{t}\right)^{2}\;.$
(119)

We then conclude for any $t=t_{L}=\omega(L^{-1/13})$ that

$\lim_{L\to\infty}\rho_{p_{\mathrm{c}},L}(\left\lceil
tL^{d}\right\rceil)=0\;.$ (120)

∎

##  6 Proof of the revealment-predictability theorem

For completeness, we now provide a self-contained proof of theorem 3.6. In
fact, with no extra effort, we consider the slightly more general situation in
which $\pi$ is an arbitrary positive product measure on $S^{B}$. The proof
follows closely the arguments presented in [12, section 2].

###### Proof of theorem 3.6.

Let $B$ be a finite set. For each $i\in B$, let $\pi_{i}:S\to(0,1)$ be a
positive probability measure on $S$, and let $\pi$ be the corresponding
product measure on $S^{B}$, defined by

$\pi(x):=\prod_{i\in B}\pi_{i}(x_{i})\;,\qquad\text{ for all }x\in S^{B}\;.$
(121)

Let $\nu_{i}=\sqrt{\pi_{i}(-1)/\pi_{i}(+1)}$, and define
$\psi_{i}:S\to\mathbb{R}$ so that $\psi_{i}(s)=s\nu_{i}^{s}$ for $s\in S$.
Then, for each $A\subseteq B$ define ${\Psi_{A}:S^{B}\to\mathbb{R}}$ via

$\Psi_{A}(x)=\prod_{i\in A}\psi_{i}(x_{i}),\qquad\text{ for all }x\in
S^{B}\;.$ (122)

It can be easily verified that $\\{\Psi_{A}\\}_{A\subseteq B}$ is an
orthonormal basis for $l^{2}(\pi)$. In what follows, all inner products and
lengths are taken with respect to the inner product on $l^{2}(\pi)$.

Let $\mu$ be any probability measure on $\mathcal{Q}_{B}$. Let $X$ and $T$ be
independent, with $X$ having distribution $\pi$, and $T$ having distribution
$\mu$. We abbreviate $J(T,X)$ by $J$. Recalling the definitions in section
3.2, note that if $g,h:S^{B}\to\mathbb{R}$, then $\langle
g_{J|X_{J}},h_{J|X_{J}}\rangle$ is a random variable on the space
$(\mathcal{Q}_{B}\times S^{B},\mu\times\pi)$. We have the following useful
lemma, whose proof we defer until the end of this section.

######  Lemma 6.1.

For any $g,h:S^{B}\to\mathbb{R}$ we have $\mathbb{E}\,[\langle
g_{J|X_{J}},h_{J|X_{J}}\rangle]=\langle g,h\rangle$.

Now let $f:S^{B}\to\mathbb{R}$. To simplify notation, we set
$\delta:=\delta_{\mu,\pi}$ and $\epsilon:=\epsilon_{\mu,\pi,f}$. Our central
task is to establish the following inequality

$\sum_{A\in\binom{B}{k}}\langle f,\Psi_{A}\rangle^{2}\leq
2\,\mathbb{E}\left[\operatorname{var}_{\pi}(f_{J|X_{J}})\right]+2\,k\,\operatorname{var}(f(X))\,\delta\;.$
(123)

First note that both sides of the above inequality are invariant upon
replacing $f$ by $f-\langle f,\Phi_{\emptyset}\rangle$. It therefore suffices
to establish equation (123) under the assumption that $\langle
f,\Phi_{\emptyset}\rangle=0$. Under this assumption we have
$\|f\|^{2}=\operatorname{var}(f(X))$.

Fix $k\in[B]$, and define $g:S^{B}\to\mathbb{R}$ via

$g:=\sum_{A\in\binom{B}{k}}\langle f,\Psi_{A}\rangle\,\Psi_{A}\;,$ (124)

and note that

$\langle f,g\rangle=\sum_{A\in\binom{B}{k}}\langle
f,\Psi_{A}\rangle^{2}=\|g\|^{2}\;.$ (125)

Equation (123) holds trivially if $g=0$, so assume $g\neq 0$.

From lemma 6.1 we have

$\displaystyle\|g\|^{2}$ $\displaystyle=\mathbb{E}\langle
g_{J|X_{J}},f_{J|X_{J}}\rangle$ (126) $\displaystyle=\mathbb{E}\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle+\mathbb{E}\langle
g_{J|X_{J}},f_{J|X_{J}}-\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle\Psi_{\emptyset}\rangle$ (127)
$\displaystyle\leq\mathbb{E}\langle g_{J|X_{J}},\Psi_{\emptyset}\rangle\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle+\mathbb{E}\,\|g_{J|X_{J}}\|\,\|f_{J|X_{J}}-\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle\Psi_{\emptyset}\|$ (128)
$\displaystyle\leq\sqrt{\mathbb{E}[\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]\,\mathbb{E}[\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]}$ (129)
$\displaystyle\qquad+\sqrt{\mathbb{E}\,[\|g_{J|X_{J}}\|^{2}]\,\mathbb{E}[\|f_{J|X_{J}}-\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle\Psi_{\emptyset}\|^{2}]}$ (130)

where the penultimate step follows from the Cauchy-Schwarz inequality applied
to $\langle\cdot,\cdot\rangle$, and the final step follows from the Cauchy-
Schwarz inequality applied to $\mathbb{E}(\cdot)$.

For any $h:S^{B}\to\mathbb{R}$, one has $\|h-\langle
h,\Psi_{\emptyset}\rangle\Psi_{\emptyset}\|^{2}=\operatorname{var}_{\pi}(h)$,
and lemma 6.1 implies

$\mathbb{E}\|h_{J|X_{J}}\|^{2}=\|h\|^{2}\;.$ (131)

Applying these observations to equation (130) yields

$\|g\|^{2}\leq\sqrt{\mathbb{E}[\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]\,\mathbb{E}[\langle
f_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]}+\|g\|\,\sqrt{\mathbb{E}[\operatorname{var}_{\pi}(f_{J|X_{J}})]}\;.$
(132)

Now observe that for any $h:S^{B}\to\mathbb{R}$

$\langle
h,\Psi_{\emptyset}\rangle^{2}\leq\|h\|^{2}-\sum_{A\in\binom{B}{k}}\langle
h,\Psi_{A}\rangle^{2}\leq\|h\|^{2}\;.$ (133)

Applying equations (131) and (133) with $h=f_{J|X_{J}}$, and recalling
$\|f\|^{2}=\operatorname{var}(f(X))$, then results in

$\|g\|^{2}\leq\sqrt{\operatorname{var}(f(X))\,\mathbb{E}[\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]}+\|g\|\,\sqrt{\mathbb{E}[\operatorname{var}_{\pi}(f_{J|X_{J}})]}\;,$
(134)

and dividing by $\|g\|$ and squaring222Making use of $(a+b)^{2}\leq
2(a^{2}+b^{2})$ yields

$\|g\|^{2}\leq 2\operatorname{var}(f(X))\,\frac{\mathbb{E}[\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]}{\|g\|^{2}}+2\,\mathbb{E}[\operatorname{var}_{\pi}(f_{J|X_{J}})]\;.$
(135)

It remains only to bound $\mathbb{E}[\langle
g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}]$. Applying equations (131) and (133)
now to $h=g_{J|X_{J}}$ we obtain

$\displaystyle\mathbb{E}\langle g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}$
$\displaystyle\leq\|g\|^{2}-\sum_{A\in\binom{B}{k}}\mathbb{E}\langle
g_{J|X_{J}},\Psi_{A}\rangle^{2}$ (136)
$\displaystyle=\sum_{A\in\binom{B}{k}}\mathbb{E}[\langle
g,\Psi_{A}\rangle^{2}-\langle g_{J|X_{J}},\Psi_{A}\rangle^{2}]\;.$ (137)

One can easily verify that for any $A,I\subseteq B$ and $y\in S^{B}$ we have

$(\Psi_{A})_{I|y_{I}}=\Psi_{A\cap I}(y)\Psi_{A\setminus I}\;,$ (138)

and it follows, for any $h:S^{B}\to\mathbb{R}$, that

$h_{I|y_{I}}=\sum_{C\subseteq B}\langle h,\Psi_{C}\rangle\Psi_{C\cap
I}(y)\Psi_{C\setminus I}\;.$ (139)

Consequently, for any $A\subseteq B$

$\langle g_{I|y_{I}},\Psi_{A}\rangle=\sum_{C\in\binom{B}{k}}\langle
g,\Psi_{C}\rangle\Psi_{C\cap I}(y)\langle\Psi_{C\setminus
I},\Psi_{A}\rangle\;.$ (140)

In particular, if $|A|=k$ we obtain

$\langle g_{I|y_{I}},\Psi_{A}\rangle=\langle g,\Psi_{A}\rangle\mathbf{1}(A\cap
I=\emptyset)\;,$ (141)

and therefore

$\displaystyle\mathbb{E}[\langle g,\Psi_{A}\rangle^{2}-\langle
g_{J|X_{J}},\Psi_{A}\rangle^{2}]$ $\displaystyle=\langle
g,\Psi_{A}\rangle^{2}\,\mathbb{P}(A\cap J\neq\emptyset)$ (142)
$\displaystyle\leq\langle g,\Psi_{A}\rangle^{2}\,\sum_{i\in A}\mathbb{P}(J\ni
i)$ (143) $\displaystyle\leq\langle g,\Psi_{A}\rangle^{2}\,k\,\delta\;.$ (144)

Combining equations (144) and (137) yields

$\mathbb{E}\langle g_{J|X_{J}},\Psi_{\emptyset}\rangle^{2}\leq
k\,\delta\,\sum_{A\in\binom{B}{k}}\langle
g,\Psi_{A}\rangle^{2}=k\,\delta\,\|g\|^{2}\;,$ (145)

and equation (123) then follows upon combining equation (145) with equations
(135) and (125). If $f$ is non-constant, one can then divide both sides of
equation (123) by $\operatorname{var}(f(X))$, and specialising to the case
$\pi=\pi_{p,B}$ for some $p\in(0,1)$ then yields the statement of theorem 3.6.
∎

######  Remark 6.2.

A comparison of equation (123) with [12, equation (2.5)] shows that where the
latter contains a factor $\|f\|^{2}$, the former contains the slightly
improved factor $\operatorname{var}(f(X))$. This minor difference is a simple
consequence of the argument applied immediately below (123).

It remains now only to prove lemma 6.1.

###### Proof of lemma 6.1.

Let $t\in\mathcal{Q}_{B}$ and $I\subseteq B$. From the definition of query
paths, if for some $y\in S^{I}$ and $z\in S^{\bar{I}}$ we have $J(t,y\oplus
z)=I$, then in fact $J(t,y\oplus z^{\prime})=I$ for all $z^{\prime}\in
S^{\bar{I}}$. It follows that if

$\Sigma_{t}^{I}:=\\{y\in S^{I}\,:\,\exists x\in S^{B}\text{ with
}x_{I}=y,J(t,x)=I\\}\;,$ (146)

then

$\displaystyle\mathbb{E}\,[\langle g_{J|X_{J}},h_{J|X_{J}}\rangle]$
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\sum_{z\in
S^{\bar{I}}}\mathbb{P}(T=t,X_{I}=y,X_{\bar{I}}=z)\,\langle
g_{I|y},h_{I|y}\rangle$ (147)
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\mathbb{P}(T=t,X_{I}=y)\,\langle
g_{I|y},h_{I|y}\rangle$ (148)
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\mathbb{P}(T=t,X_{I}=y)\,\sum_{x^{\prime}\in
S^{B}}\pi(x^{\prime})g_{I|y}(x^{\prime})h_{I|y}(x^{\prime})$ (149)
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\mathbb{P}(T=t,X_{I}=y)\,$
$\displaystyle\qquad\times\sum_{y^{\prime}\in S^{I}}\sum_{z^{\prime}\in
S^{\bar{I}}}\mathbb{P}(X_{I}=y^{\prime},X_{\bar{I}}=z^{\prime})g_{I|y}(y^{\prime}\oplus
z^{\prime})h_{I|y}(y^{\prime}\oplus z^{\prime})$ (150)
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\mathbb{P}(T=t,X_{I}=y)\,$
$\displaystyle\qquad\times\sum_{y^{\prime}\in S^{I}}\sum_{z^{\prime}\in
S^{\bar{I}}}\mathbb{P}(X_{I}=y^{\prime},X_{\bar{I}}=z^{\prime})g(y\oplus
z^{\prime})h(y\oplus z^{\prime})$ (151)
$\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{I\subseteq
B}\sum_{y\in\Sigma_{t}^{I}}\sum_{z\in
S^{\bar{I}}}\mathbb{P}(T=t,X_{I}=y)\,\mathbb{P}(X_{\bar{I}}=z)g(y\oplus
z)h(y\oplus z)$ (152) $\displaystyle=\sum_{t\in\mathcal{Q}_{B}}\sum_{x\in
S^{B}}\mathbb{P}(T=t,X=x)\,g(x)h(x)$ (153) $\displaystyle=\sum_{x\in
S^{B}}\pi(x)\,g(x)h(x)$ (154) $\displaystyle=\langle g,h\rangle\;.$ (155)

∎

######  Corollary 6.3.

Let $p\in(0,1)$ and let $B$ be a finite set. Let $\pi:=\pi_{p,B}$, and let
$\mu$ be any distribution on $\mathcal{Q}_{B}$. For any non-constant function
$f:S^{B}\to\mathbb{R}$ we have $\epsilon_{\mu,\pi,f}\leq 1$.

###### Proof.

Suppose $\mathbb{E}(f)=0$, so that $\langle
f,f\rangle=\operatorname{var}(f(X))$. Since

$\operatorname{var}_{\pi}(f_{J|X_{J}})=\sum_{\begin{subarray}{c}A\subseteq[n]\\\
A\neq\emptyset\end{subarray}}\,\langle
f_{J|X_{J}},\Psi_{A}\rangle^{2}\leq\langle f_{J|X_{J}},f_{J|X_{J}}\rangle\;,$
(156)

it follows from lemma 6.1 that

$\displaystyle\mathbb{E}[\operatorname{var}_{\pi}(f_{J|X_{J}})]\leq\operatorname{var}(f(X))\;.$
(157)

Since both sides of equation (157) are unchanged upon adding a constant to
$f$, the assumption of mean zero can be relaxed, and the stated result
follows. ∎

The authors thank Andrea Collevecchio and Greg Markowsky for many useful
conversations during the early stages of this work, and also Bob Griffiths for
useful comments on an earlier draft. This research was supported by the
Australian Research Council Centre of Excellence for Mathematical and
Statistical Frontiers (Project no. CE140100049), and the Australian Research
Council’s Discovery Projects funding scheme (Project No.s DP140100559,
DP180100613 and DP230102209).

## References

## References

  * [1] P C Hohenberg and B I Halperin.  Theory of dynamic critical phenomena.  Reviews of Modern Physics, 49:435–479, 1977.
  * [2] Alan D. Sokal.  Monte carlo methods in statistical mechanics: Foundations and new algorithms.  In P. Cartier C. de Witt-Morette and A. Folacci, editors, Functional Integration: Basics and Applications, pages 131–192. Plenum Press, New York, 1997.
  * [3] Hacéne Boukari, Matthew E. Briggs, J. N. Shaumeyer, and Gammon Robert W.  Critical Speeding Up Observed.  Physical Review Letters, 65:2654–2657, 1990.
  * [4] Christoph P Grams, Martin Valldor, Markus Garst, and Joachim Hemberger.  Critical speeding-up in the magnetoelectric response of spin-ice near its monopole liquid-gas transition.  Nature communications, 5:4853, 2014.
  * [5] Marco Tavora, Achim Rosch, and Aditi Mitra.  Quench dynamics of one-dimensional interacting bosons in a disordered potential: Elastic dephasing and critical speeding-up of thermalization.  Physical Review Letters, 113:010601, 2014.
  * [6] A. Patz, T. Li, L. Luo, X. Yang, S. Bud’ko, P. C. Canfield, I. E. Perakis, and J. Wang.  Critical speeding up of nonequilibrium electronic relaxation near nematic phase transition in unstrained $Ba(Fe_{1-x}Co_{x})_{2}As_{2}$.  Physical Review B, 95:165122, 2017.
  * [7] Youjin Deng, Timothy M Garoni, and Alan D Sokal.  Critical speeding-up in the local dynamics of the random-cluster model.  Physical Review Letters, 98:230602, 2007.
  * [8] Y Deng, T M Garoni, and A. D. Sokal.  Dynamic Critical Behavior of the Worm Algorithm for the Ising Model.  Physical Review Letters, 99:110601, 2007.
  * [9] Eren Metin Elçi and Martin Weigel.  Efficient simulation of the random-cluster model.  Physical Review E, 88:033303, 2013.
  * [10] Christophe Garban and Jeffrey E. Steif.  Noise Sensitivity of Boolean Functions and Percolation.  Cambridge University Press, Cambridge, 2015.
  * [11] Itai Benjamini, Gil Kalai, and Oded Schramm.  Noise sensitivity of Boolean functions and applications to percolation.  Publications Mathématiques de l’IHÉS, 90:5–43, 1999.
  * [12] Oded Schramm and Jeffrey E. Steif.  Quantitative noise sensitivity and exceptional times for percolation.  Annals of Mathematics, 171:619–672, 2010.
  * [13] Geoffrey Grimmett.  The Random-Cluster Model.  Springer, New York, 2009.
  * [14] O. Häggströmm and Y. Peres and J. E. Steif.  Dynamical percolation.  Ann. Inst. Henri Poincaré, Probab. et Stat, 33:497–528, 1997\.
  * [15] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, 2017.
  * [16] Neal Madras and Gordon Slade.  The Self-Avoiding Walk.  Birkhäuser, Berlin, 1996.
  * [17] Russell Lyons and Yuval Peres.  Probability on Trees and Networks.  Cambridge University Press, Cambridge, 2016.
  * [18] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, Cambridge, 2014.
  * [19] Ronald Graham, Donald Knuth, and Oren Patashnik.  Concrete Mathematics.  Addison–Wesley, Westford, Massachusetts, 1994.
  * [20] Markus Heydenreich and Remco Van Der Hofstad.  Random graph asymptotics on high-dimensional tori.  Communications in Mathematical Physics, 270:335–358, 2007.
  * [21] G. Grimmett.  Percolation.  Springer, New York, 2nd edition, 1999.
  * [22] Markus Heydenreich and Remco van der Hofstad.  Random graph asymptotics on high-dimensional tori ii: volume, diameter and mixing time.  Probability theory and related fields, 149:397–415, 2011.
  * [23] Christian Borgs, Jennifer T Chayes, Remco van der Hofstad, Gordon Slade, and Joel Spencer.  Random subgraphs of finite graphs: I. The scaling window under the triangle condition.  Random Structures & Algorithms, 27:137–184, 2005.
  * [24] Christian Borgs, Jennifer T Chayes, Remco van der Hofstad, Gordon Slade, and Joel Spencer.  Random subgraphs of finite graphs: II. The lace expansion and the triangle condition.  Annals of Probability, 33:1886–1944, 2005.
  * [25] Gady Kozma and Asaf Nachmias.  Arm exponents in high dimensional percolation.  Journal of the American Mathematical Society, 24:375–409, 2011\.
  * [26] Tom Hutchcroft, Emmanuel Michta, and Gordon Slade.  High-dimensional near-critical percolation and the torus plateau.  Annals of Probability, 51:580–625, 2023.