\section{Why the enclosing intervals become narrow}\label{app:coupling}

We analyse lower and upper calculations on the full graph, with a
fresh independent uniform digit at every vertex in every sweep. By
Appendix~\ref{sec:finite-dependence}, the queried endpoints have the
same distribution as those in the finite local list.

\subsection{The decrease after one sweep}
Write $\Delta_z=B_z-A_z$. Superscripts old and new refer to the start
of a sweep and the value after a coordinate's update. For a
vertex $z$, the shared digit $j_z$ gives
\begin{equation}\label{eq:local-coupling}
\Delta_z^{\rm new}\le
\frac1S\Delta_z^{\rm old}
+\frac{S-1-j_z}{S}\max_{u\to z}\Delta_u^{\rm new}
+\frac{j_z}{S}\max_{z\to u}\Delta_u^{\rm old},
\end{equation}
with an empty maximum equal to zero. The stored interval bounds in the two calculations are identical.

Let $B_h(z)$ be the vertices at undirected distance at most $h$ from $z$. Put
$D=\max_{u\in B_h(z)}\Delta_u^{\rm old}$ and
$a_u=(S-1-j_u)/S$. At $z$, \eqref{eq:local-coupling} gives
\[
\Delta_z^{\rm new}\le(1-a_z)D+
                           a_z\max_{u\to z}\Delta_u^{\rm new}.
\]
Follow a predecessor attaining the maximum, and continue backwards to a
source. This path has at most $h$ vertices; all its vertices and their
successors lie in $B_h(z)$. At the source the predecessor term is zero.
Substitution along the path bounds the new width by
$\bigl(1-\prod_u a_u\bigr)D$.

Write $\Delta_z(s)$ for the width after $s$ sweeps.
Call the pair $(z,s)$ \emph{bad} if, during sweep $s$, the digit at $z$
or any vertex preceding $z$ on a directed path equals $S-1$. Otherwise all factors $a_u$ in the
preceding expansion are at least $1/S$, and there are at most $h$ of
them. Put $\beta=1-S^{-h}$. Consequently,
\begin{equation}\label{eq:local-one-sweep}
\Delta_z(s)\le\kappa_z(s)\max_{u\in B_h(z)}\Delta_u(s-1),
\qquad
\kappa_z(s)=
\begin{cases}
1,&(z,s)\text{ is bad},\\
\beta,&\text{otherwise}.
\end{cases}
\end{equation}

\subsection{Choosing the parameters}

Write $r=2$ for the bound on the number of queried coordinates.
Both $B_h(z)$ and the set consisting of $z$ and its directed-path
predecessors have at most $M$ vertices. Choose
\begin{equation}\label{eq:digit-alphabet}
M=(d+1)^{h+1},\qquad
S=\text{the least power of two at least }4M^2.
\end{equation}
The bad event in \eqref{eq:local-one-sweep} involves only fresh digits
from the current sweep. Its conditional probability is at most
$M/S\le1/(4M)$. With $\beta=1-S^{-h}$, choose the smallest positive
integer $p$ satisfying the rational test
\begin{equation}\label{eq:moment-power}
\beta^p\le\frac1{4M}.
\end{equation}
Consequently,
\[
\E\bigl[\kappa_z(s)^p\mid\text{earlier sweeps}\bigr]
\le\frac1{4M}+\beta^p\le\frac1{2M}.
\]
This estimate uses all directed-path predecessors in defining the bad
event, so it also covers the predecessor choices made in the one-sweep
expansion. No independence between vertices within a sweep is required.

Choose the smallest positive integer $t$ satisfying
\begin{equation}\label{eq:local-radius}
2^{-t}\le\frac{\alpha\delta^p}{r},\qquad \rho=ht+1.
\end{equation}
These choices are computable: $0<\beta<1$, and both tests compare rational
numbers. Retain radius $\rho$ around the queried set $T$, freezing the
outer boundary as in Algorithm~\ref{alg:finite-digits}.

The widths before sweep $s$ are fixed when we condition on earlier
sweeps. Raising \eqref{eq:local-one-sweep} to the power $p$, bounding
the maximum by a sum, and taking expectations gives
\[
\E\Delta_z(s)^p
\le\frac1{2M}\sum_{u\in B_h(z)}\E\Delta_u(s-1)^p.
\]
All initial widths are at most one and $|B_h(z)|\le M$. Induction
gives $\E\Delta_z(s)^p\le2^{-s}$ for every vertex. At sweep $t$,
Markov's inequality gives
$\Prb(\Delta_z(t)>\delta)\le2^{-t}\delta^{-p}\le\alpha/r$.
A union bound over the at most $r$ queried positions proves the width
guarantee.

Each radius-$\rho$ neighborhood has at most
$1+d+\cdots+d^\rho\le(d+1)^{\rho+1}$ vertices. We may therefore use
\begin{equation}\label{eq:local-size}
b=r(d+1)^{\rho+1},\qquad E=S^{bt}
\end{equation}
as bounds on the retained vertices and enumerated digit assignments.
All these choices depend only on $d,h,\delta,\alpha$.