Is Toom's rule robust under local but non-on-site noise? Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular automaton by introducing bit-flip or biased noise. What about more general local, but non-on-site noise. E.g., imagine after each step of the deterministic Toom's rule, flipping each pair of neighboring bits together, with a small constant probability. (This is well-defined since double-bit-flips commute with each other; if we want more general noise like low-probability CNOTs one would have to apply this noise in some kind of brick-layer-type manner.)
Is Toom's rule still stable under such more general noise? I assume there's nothing proven, but maybe there are numerical studies on this?
 A: Toom's CA is robust under such noise. In fact, the class of noise distributions he considers is quite general. For a fixed CA $f$ on $\{0,1\}^{\mathbb{Z}^2}$ and a parameter $0 \leq \epsilon \leq 1$, let $M_\epsilon$ be the set of Borel probability measures $\mu$ on $(\{0,1\}^{\mathbb{Z}^2})^ {\mathbb{N}}$ such that every finite set $V \subset \mathbb{Z}^2 \times \mathbb{N}$ satisfies
$$
\mu(\forall (\vec v, n) \in V : x(n+1)_{\vec v} \neq f(x(n))_{\vec v}) < \epsilon^{|V|}
$$
for a $\mu$-random itinerary $x = (x(n))_{n \in \mathbb{N}} \in (\{0,1\}^{\mathbb{Z}^2})^ {\mathbb{N}}$.
For $y \in \{0,1\}^{\mathbb{Z}^2}$, let $M_\epsilon(y)$ be the subset of those $\mu \in M_\epsilon$ with $\mu(x(0) = y) = 1$ (we fix the initial configuration instead of allowing it to be random).
In Theorem 1 and Example 1 of [1], Toom proves that the north-east-self majority CA satisfies
$$
\lim_{\epsilon \to 0} \sup_{\mu \in M_\epsilon(a^{\mathbb{Z}^2}), (\vec v, n) \in \mathbb{Z}^2 \times \mathbb{N}} \mu(x(n)_{\vec v} \neq a) = 0
$$
for $a = 0$ and $a = 1$.
This means that the itinerary "remembers" its initial state if we store it in every cell, since every spacetime point has the same high probability of being in that state.
Intuitively, the marginals of the noise don't have to be independent or identically distributed at different spacetime points, as long as its error rate on any finite set of spacetime points is dominated by independent $\epsilon$-noise.
In particular, choosing to independently flip adjacent pairs, or even larger local patterns, with a small enough probability on every time step results in a robust CA.
[1] A. Toom. Stable and Attractive Trajectories in Multicomponent Systems. Multicomponent Random Systems, Dekker, 1980, v. 6, pp.549-576. Originally published in Russian. Available at Toom's website.
