\section{Local calculations on order-restriction DAGs}\label{sec:oracle}

We construct the routines in Lemmas~\ref{lem:local-routines}
and~\ref{lem:anchor-selection} for a single order-restriction DAG. Both use lists of intervals enclosing the
queried coordinates. A pair of disjoint intervals certifies an order, and a list
of intervals can certify how much probability lies on each side of a
candidate anchor interval.

\subsection{A coordinate update with finitely many choices}

Let $D$ be an order-restriction DAG with canonical interval endpoints
$\ell_z,r_z$. Write $G$ for its underlying graph. For a current assignment $Y$, the interval permitted at coordinate $z$ has endpoints
\[
L_z=\max\bigl(\{\ell_z\}\cup\{Y_u:u\to z\}\bigr),\qquad
U_z=\min\bigl(\{r_z\}\cup\{Y_u:z\to u\}\bigr).
\]
Fix a power of two $S$. For a digit $j\in\{0,\ldots,S-1\}$, update
\begin{equation}\label{eq:digit-update}
Y_z\gets\frac{Y_z+(S-1-j)L_z+jU_z}{S}.
\end{equation}
The coefficients are nonnegative and sum to one. Thus an assignment
satisfying the interval bounds and arc inequalities weakly continues to
do so after an update, including when $L_z=U_z$.

Choosing the digit uniformly preserves the uniform distribution on the
feasible region. Start from a uniform feasible assignment and condition
on all coordinates other than $z$. Then $Y_z$ is uniform
on $(L_z,U_z)$. Its normalized position
$r=(Y_z-L_z)/(U_z-L_z)$ is sent to
\[
r'=\frac{r+j}{S}.
\]
For a fixed digit, this is uniform on the corresponding one of the $S$
equal subintervals. Averaging over the digits makes $r'$ uniform on
$(0,1)$ again.

\subsection{The enclosing-interval guarantee}

In Algorithm~\ref{alg:finite-digits}, call the vertices at distance
$\rho$ from $T$ the \emph{boundary}, and those at smaller distance the
\emph{interior}. A \emph{sweep} is one repetition of the updates over
the interior vertices. If there are $b'$ interior vertices, the list has
\begin{equation}\label{eq:digit-count}
N=S^{b't}
\end{equation}
entries, counting repetitions. Each interior vertex has all its neighbors
in the retained DAG.

\begin{theorem}[Local enclosing intervals]\label{thm:local}
Let $d,h\ge1$ be integers and let $\delta,\alpha\in(0,1)$ be rational.
There are computable parameters $S,t,\rho$ and a bound $E$, depending
only on $d,h,\delta,\alpha$, with the following property.

Suppose $D$ is an order-restriction DAG with canonical dyadic intervals,
degree at most $d$, directed paths of at most $h$ vertices, and
$V(D)>0$. Write $K=K(D)$. For any nonempty set $T$ of
one or two coordinates, Algorithm~\ref{alg:finite-digits} returns a list
satisfying two guarantees:
\begin{enumerate}
\item A uniformly selected entry and a uniform feasible assignment $X$ can
be drawn jointly so that $A_x\le X_x\le B_x$ for every $x\in T$.
\item At most a fraction $\alpha$ of its entries have
$\max_{x\in T}(B_x-A_x)>\delta$.
\end{enumerate}
The calculation enumerates at most $E$ digit assignments. If the stored
bounds have at most $\Lambda$ fractional binary digits, every computed
endpoint has at most $\Lambda+\log E$ fractional digits.
\end{theorem}
\begin{proof}
The enclosure and dependence arguments follow below. See
Appendix~\ref{app:coupling} for the width and enumeration bounds, and
Appendix~\ref{app:arithmetic} for the precision bound.
\end{proof}

The enclosure guarantee holds for every finite number of sweeps and
every choice of radius $\rho\ge1$. Start a full assignment uniformly on
$K$ and update the entire graph with independent uniform digits. Share
its digits with the two endpoint calculations at interior vertices.
The update is increasing in every coordinate, since maxima, minima, and
the nonnegative linear combination in \eqref{eq:digit-update} are
increasing. Thus it preserves the inequalities $A_z\le X_z\le B_z$ at
an interior update. At a boundary vertex the full position always remains
between its fixed interval endpoints, even as it changes during the full
calculation. The full assignment remains uniform, and every interior
digit sequence has probability $1/N$. This proves the first guarantee.

\subsection{How far a sweep can reach}\label{sec:finite-dependence}

For the width estimate, consider lower and upper sweeps that update the
full graph. In either calculation, the update of a coordinate uses the
new values of its predecessors, the old values of its successors, and
its own old value. The resulting values are independent of the choice
of topological order because these dependencies specify every update.

To trace a dependency backwards through one sweep, follow new values
along incoming arcs. This follows a directed path with at most $h-1$
arcs. Moving from that path to an old value crosses at most one more
arc. A value after $t$ sweeps thus depends only on digits, bounds and
initial values within distance $ht$. With $\rho=ht+1$, every update
in this dependency calculation is in the retained interior. Its initial
values, stored bounds, and digits are the same in the local and full
calculations. Consequently the queried endpoints agree exactly for
every assignment of the digits, with arbitrary digits outside the
retained region.

Appendix~\ref{app:coupling} bounds the widths on the full graph.
Exact agreement transfers that estimate to the local lists.

\subsection{From intervals to answers and anchors}

The enclosure guarantee makes the fractions counted by \texttt{Select}
lower bounds on the corresponding answer probabilities.

The routine \texttt{ChooseAnchor} uses a one-coordinate list. It tests
whether a proposed interval contains at least a quarter of the mass,
with at least a quarter on either side. The test counts entries lying
wholly in each of these three regions. On success it rounds within the
tested interval. On failure it rounds in the middle half of the
coordinate's range. Appendix~\ref{app:certificates} gives the endpoint
selection and shows that a failed test identifies a short coordinate
interval. The gain and precision estimates in
Appendix~\ref{app:execution} complete the proof of
Lemmas~\ref{lem:local-routines} and~\ref{lem:anchor-selection}.

\begin{algorithm}[H]
\caption{\texttt{ChooseAnchor}$(D,x)$: choose an interior position.}
\label{alg:choose-anchor}
\DontPrintSemicolon
\KwIn{A canonical order-restriction DAG $D$ and a coordinate $x$ with interval $(\ell_x,r_x)$.}
\KwOut{A dyadic position $c\in(\ell_x,r_x)$.}
$J\gets$ \texttt{CentralInterval}$(D,x)$\;
\If{$J$ is \textnormal{\texttt{FAIL}}}{
  $W_x\gets r_x-\ell_x$\;
  $J\gets[\ell_x+W_x/4,\ r_x-W_x/4]$\;
}
\Return \texttt{RoundUp}$(J)$\;
\end{algorithm}