Proof. We argue by induction on \(t\). For \(t=0\) we have \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,0}(w)=\{w\}\) and \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,0}(w)=\emptyset\), so the claim is immediate.

Now fix \(t \geq 1\) and assume that \[\begin{align} \mathcal{C}_{t-1} := \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t-1}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\nonumber \end{align}\] is a simple \(w\)-cut. Let \(v \in \Sigma^n\) be any leaf with \(v \succeq w\). Since \(\mathcal{C}_{t-1}\) is a simple \(w\)-cut, there is a unique node \(u \in \mathcal{C}_{t-1}\) on the path from \(w\) to \(v\).

If \(u \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\), then \(u\) is also in \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\). Moreover, no node of \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) or of \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w) \setminus \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\) can lie below \(u\), because every node added at time \(t\) must be a descendant of some element of \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t-1}(w)\), whereas \(u\) is already the unique cut node on the path from \(w\) to \(v\). Thus \(u\) is the unique node of \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\) on this path.

It remains to consider the case \(u \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t-1}(w)\). Along the path from \(u\) to \(v\), the leaf \(v\) itself satisfies (P2) relative to \(u\), simply because \(|v|=n\). Hence there is at least one descendant of \(u\) on the path to \(v\) satisfying either (P1) or (P2) relative to \(u\). Let \(z\) be the first such descendant. By definition, \(z\) belongs to \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) if it satisfies (P1) but not (P2), and to \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\) if it satisfies (P2).

By the choice of \(z\), no proper ancestor of \(z\) which is a descendant of \(u\) satisfies either (P1) or (P2). Also, no proper descendant of \(z\) can belong to \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) or to \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w) \setminus \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\), because membership in those sets requires that neither the node itself nor any of its ancestors satisfy (P1) or (P2). Finally, there is no element of \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\) below \(u\) on the path to \(v\), since \(u\) was the unique element of \(\mathcal{C}_{t-1}\) on that path. Therefore \(z\) is the unique node of \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\) lying on the path from \(w\) to \(v\).

Since this holds for every leaf \(v \succeq w\), the set \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\) is a simple \(w\)-cut. ◻

Proof. We first claim that every node in \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) lies at depth at least \(|w|+t\). Indeed, for \(t=0\) this is immediate since \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,0}(w)=\{w\}\). For \(t \geq 1\), if \(u \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\), then by definition \(u\) satisfies (P1) relative to some node \(u' \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t-1}(w)\), and hence \(u \succ u'\). By induction, \(|u'| \geq |w|+t-1\), so \(|u| \geq |u'|+1 \geq |w|+t\).

Next, no intermediate node can be a leaf. Indeed, if \(|u|=n\), then \(u\) satisfies (P2) by definition. But a node belongs to \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) only if neither it nor any of its ancestors satisfy (P1) or (P2). Therefore every \(u \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) must satisfy \(|u|<n\).

Combining the two observations, if \(t \geq n-|w|\) and \(u \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\), then \(|u| \geq |w|+t \geq n\), which forces \(|u|=n\), a contradiction. Hence \[\begin{align} \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)=\emptyset \qquad \forall t \geq n-|w|.\nonumber \end{align}\] Thus we may take \(t_0 := n-|w|\).

Finally, once \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) is empty, the inductive definition adds no further nodes to \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\), so the final sets remain constant for all subsequent times. ◻

Proof. We prove the first two claims by induction on \(t\), restricting attention to those values of \(t\) for which the \(i\)th outer-loop iteration actually reaches stage \(t\).

The base case \(t=0\) is immediate; now fix \(t \geq 1\) and assume the claim holds for \(t-1\). Suppose the \(i\)th outer-loop iteration reaches stage \(t\). Then stage \(t-1\) cannot have terminated in a final branch, so the only way to proceed is that Line [line:proceed-next-t] was executed at step \(t-1\). Consequently, \[\begin{align} w_{i,t-1} \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t-1}(w) \qquad\text{and}\qquad \mathcal{G}_{i,t-1}=\mathcal{G}_{t-1}(w_{i,t-1}). \nonumber \end{align}\] In particular, the proposal distribution used at step \(t\) is exactly \(\bar \eta_{t-1,w_{i,t-1}}\).

At step \(t\), the while loop (Line [line:while-wit]) walks down the sampled path until the first descendant \(z \succ w_{i,t-1}\) for which either (P1) or (P2) relative to \(w_{i,t-1}\) is triggered. By the recursive definition of \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w)\) and \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\), this implies \[\begin{align} w_{i,t} \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w). \nonumber \end{align}\] If Line [line:proceed-next-t] is reached at stage \(t\), then \(w_{i,t}\) satisfies (P1) relative to \(w_{i,t-1}\), so the algorithm updates \[\begin{align} \mathcal{G}_{i,t} = \left\{ \eta \in \mathcal{G}_{i,t-1} \mid \frac{1}{R} \leq \frac{\hat{\mu}(w_{i,t})}{\eta(w_{i,t})} \leq R \right\}. \nonumber \end{align}\] Using the induction hypothesis \(\mathcal{G}_{i,t-1}=\mathcal{G}_{t-1}(w_{i,t-1})\), and using that exactly one element of each of \(\mathcal{G}_{1}(w_{i,t-1}), \mathcal{G}_2(w_{i,t-1}), \ldots, \mathcal{G}_{t-1}(w_{i,t-1})\) lies on the path from \(w\) to \(w_{i,t}\) (namely \(w_{i,1}, \ldots, w_{i,t-1}\)), it follows from the definition of \(\mathcal{G}_t(\cdot)\) (see 10 ) that \(\mathcal{G}_{i,t} = \mathcal{G}_t(w_{i,t})\). This completes the induction.

Finally, every element added to \(\mathcal{T}\) is added either on Line [line:add-to-T-mid] or on Line [line:add-to-T-end]. In the first case, the node \(w_{i,t}\) necessarily satisfies (P2) relative to the intermediate node \(w_{i,t-1}\) because some child \(w_{i,t}\circ y\) violates the upper threshold; in the second case, \(|w_{i,t}|=n\), so \(w_{i,t}\) again satisfies (P2). In both cases, the argument above shows that the added node lies in \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w) \subseteq \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)\). ◻

Proof. On the event \(\mathcal{E}^{\mathsf{restrict}}\), there is at least one outer-loop iteration \(i \in [M]\) and one stage \(t \geq 1\) at which the algorithm executes Line [line:add-to-T-mid]. Fix any such pair \((i,t)\), and let \(z := w_{i,t} \in \Sigma^{<n}\) denote the node added to \(\mathcal{T}\) at that line. By the condition of the branch, there exists some \(y \in \Sigma\) such that \[\begin{align} \frac{\hat{\mu}(z \circ y)}{\hat{\mu}(w_{i,t-1}) \cdot \bar \eta_{i,t-1}(z \circ y \mid w_{i,t-1})} > M. \label{eq:gret-upper-trigger} \end{align}\tag{11}\] By definition of the class \(\mathcal{G}_{i,t-1}\) (Line [line:proceed-next-t] of 2), every \(\eta \in \mathcal{G}_{i,t-1}\) satisfies \(\frac{1}{R} \leq \frac{\hat{\mu}(w_{i,t-1})}{\eta(w_{i,t-1})} \leq R\). In particular, \(\hat{\mu}(w_{i,t-1}) \leq R \cdot \eta(w_{i,t-1})\) for every \(\eta \in \mathcal{G}_{i,t-1}\). Using that \(\bar \eta_{i,t-1} = \frac{1}{|\mathcal{G}_{i,t-1}|} \sum_{\eta \in \mathcal{G}_{i,t-1}} \eta\), we see that \(\hat{\mu}(w_{i,t-1}) \leq R \cdot \bar \eta_{i,t-1}(w_{i,t-1})\). Using this fact together with 11 , we see that \[\begin{align} \frac{\hat{\mu}(z \circ y)}{\bar \eta_{i,t-1}(z \circ y)} \geq \frac{\hat{\mu}(z \circ y)}{\bar \eta_{i,t-1}(z \circ y)} \cdot \frac{\bar \eta_{i,t-1}(w_{i,t-1})}{\hat{\mu}(w_{i,t-1})\cdot R} = \frac{\hat{\mu}(z \circ y)}{R \cdot \hat{\mu}(w_{i,t-1}) \cdot \bar \eta_{i,t-1}(z \circ y \mid w_{i,t-1})} > \frac{M}{R}\label{eq:hatmu-bareta-ratio}. \end{align}\tag{12}\] Since we have assumed that \(z\) is added to \(\mathcal{T}\) on Line [line:add-to-T-mid], then the value of \(\mathcal{G}^{\mathsf{ret}}\) eventually returned by 2 satisfies \[\begin{align} \mathcal{G}^{\mathsf{ret}}\subset \left\{ \eta \in \mathcal{G}_{i,t-1} \mid \frac{\hat{\mu}(z \circ y)}{\eta(z \circ y)} \leq R \right\}. \end{align}\] Combining this with 12 and using Markov’s inequality yields \(|\mathcal{G}^{\mathsf{ret}}| \leq |\mathcal{G}_{i,t-1}| \cdot \frac{R^2}{M} \leq |\mathcal{G}| \cdot \frac{R^2}{M}\). ◻

Proof. We first prove 13 . Fix \(t \geq 1\) and \(w' \in \mathcal{S}_{\mathcal{G},M,t}(w)\). For each \(0 \leq r < t\), let \(w_r\) denote the unique node on the path from \(w\) to \(w'\) that belongs to the simple cut \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,r}(w) \cup \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,r}(w).\nonumber\) By 4, we must have \(w_r \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,r}(w)\) for every \(0 \leq r < t\). In particular, \(w_0=w\), and for each \(1 \leq r \leq t\), the node \(w_r\) satisfies (P1) relative to \(w_{r-1}\).

For each \(1 \leq r \leq t\), conditioned on \(A_{i,r-1}(w_{r-1})\), the probability that the algorithm next reaches \(w_r\) and survives the Bernoulli test in the (P1) branch (on Line [line:proceed-next-t]) is \[\begin{align} \bar \eta_{r-1,w_{r-1}}(w_r \mid w_{r-1}) \cdot \frac{\hat{\mu}(w_r)}{\hat{\mu}(w_{r-1}) \cdot \bar \eta_{r-1,w_{r-1}}(w_r \mid w_{r-1})} = \frac{\hat{\mu}(w_r)}{\hat{\mu}(w_{r-1})}.\nonumber \end{align}\] Therefore \[\begin{align} \mathbb{P}(A_{i,t-1}(w_{t-1})) = \prod_{r=1}^{t-1} \frac{\hat{\mu}(w_r)}{\hat{\mu}(w_{r-1})} = \frac{\hat{\mu}(w_{t-1})}{\hat{\mu}(w)}.\nonumber \end{align}\] To establish 13 , we next note that \[\begin{align} \mathbb{P}(\bar A_{i,t}(w')) = \mathbb{P}(A_{i,t-1}(w_{t-1})) \cdot \bar \eta_{t-1,w_{t-1}}(w' \mid w_{t-1}) = \frac{\hat{\mu}(w_{t-1})}{\hat{\mu}(w)} \cdot \bar\eta_{t-1,w_{t-1}}(w' \mid w_{t-1})\label{eq:bar-ait-equality}, \end{align}\tag{15}\] which yields 13 by noting that \(w_{t-1} = \mathfrak{p}(w')\).

We proceed to prove 14 . Fix \(w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)\), and let \(t \geq 1\) be the smallest index for which \(w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w)\). For each \(0 \leq r < t\), let \(w_r\) denote the unique node on the path from \(w\) to \(w'\) that belongs to the simple cut \(\mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,r}(w).\) It follows from the same argument used to derive 13 that \[\begin{align} \mathbb{P}(A_{i,t-1}(w_{t-1})) = \frac{\hat{\mu}(w_{t-1})}{\hat{\mu}(w)}. \label{eq:ts-rs-intermediate-chain} \end{align}\tag{16}\]

Now condition on \(A_{i,t-1}(w_{t-1})\). Since \(w'=w_t\) satisfies (P2) relative to \(w_{t-1}\), the algorithm reaches \(w'\) with probability \(\bar \eta_{t-1,w_{t-1}}(w' \mid w_{t-1})\), and then adds \(w'\) to \(\mathcal{T}\) (on either Line [line:add-to-T-mid] or Line [line:add-to-T-end]) with Bernoulli probability \[\begin{align} \frac{\hat{\mu}(w')}{\hat{\mu}(w_{t-1}) \cdot \bar \eta_{t-1,w_{t-1}}(w' \mid w_{t-1})} \cdot \frac{1}{M}. \nonumber \end{align}\] This Bernoulli parameter is indeed at most \(1\): the node \(w'\) was obtained by extending from \(w_{t-1}\) in the immediately preceding step of the while loop, and that extension could only occur while the while-condition in Line [line:while-wit] held. Thus, if \(B_i\) denotes the event that the \(i\)th outer-loop iteration contributes one copy of \(w'\) to \(\mathcal{T}\), then \[\begin{align} \mathbb{P}(B_i \mid A_{i,t-1}(w_{t-1})) = \bar \eta_{t-1,w_{t-1}}(w' \mid w_{t-1}) \cdot \frac{\hat{\mu}(w')}{\hat{\mu}(w_{t-1}) \cdot \bar \eta_{t-1,w_{t-1}}(w' \mid w_{t-1})} \cdot \frac{1}{M} = \frac{\hat{\mu}(w')}{M \cdot \hat{\mu}(w_{t-1})}.\nonumber \end{align}\] Combining this with 16 , we obtain \[\begin{align} \mathbb{P}(B_i) = \frac{\hat{\mu}(w_{t-1})}{\hat{\mu}(w)} \cdot \frac{\hat{\mu}(w')}{M \cdot \hat{\mu}(w_{t-1})} = \frac{\hat{\mu}(w')}{M \cdot \hat{\mu}(w)}.\nonumber \end{align}\]

Each outer-loop iteration contributes at most one copy of \(w'\) to \(\mathcal{T}\), and the \(M\) outer-loop iterations are identically distributed. Therefore \[\begin{align} \mathbb{E}[\mathsf{occ}(w',\mathcal{T})] = \sum_{i=1}^M \mathbb{P}(B_i) = M \cdot \frac{\hat{\mu}(w')}{M \cdot \hat{\mu}(w)} = \frac{\hat{\mu}(w')}{\hat{\mu}(w)},\nonumber \end{align}\] as claimed. ◻

Proof. For each \(i \in [M]\), let \(T_i \in \mathbb{N}\) denote the final value of \(t\) reached in the for loop in Line [line:for-t] of 2, in outer iteration \(i\). The expected number of oracle calls made by 2, which we denote by the random variable \(V\), may be bounded as follows: \[\begin{align} \mathbb{E}[V] \leq M |\Sigma| \cdot O \left( \sum_{t=1}^n \sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \mathbb{P}(\bar A_{i,t}(w'))+ \mathbb{E}[T_i+1]\right)\label{eq:ev-init-bnd}. \end{align}\tag{17}\] Indeed, for each outer loop iteration \(i \in [M]\), 2 queries \(\hat{\mu}\) at each of the nodes along the path \(w_{i,0} \to w_{i,1} \to \cdots \to w_{i,T_i}\), as well as at each of the children of each of these nodes (in order to check the condition in the while statement on [line:while-wit]). For each \(0 \leq t \leq T_i\), we have \(w_t \in \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)\): the first term in 17 accounts for the queries made at the nodes in-between the \(w_{i,t}\), and the second term accounts for the queries made at the nodes \(w_{i,t}\).

First, we note that, since \(M \geq 2\), we have \(\mathbb{P}(T_i \geq t+1 \mid T_i \geq t) \leq 1/M \leq 1/2\) for each \(t \geq 0\). Thus, \(\mathbb{E}[T_i] \leq 4\). We proceed to bound the first term in 17 .

Next, for any \(t \geq 1\), we compute \[\begin{align} & \sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \mathbb{P}(\bar A_{i,t}(w')) \nonumber\\ = & \sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \frac{\bar \eta_{t-1,\mathfrak{p}(w')}(w') \cdot \hat{\mu}(\mathfrak{p}(w'))}{\hat{\mu}(w)}\nonumber\\ \leq &\sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \frac{M \cdot \hat{\mu}(w')}{\hat{\mu}(w)}\nonumber\\ \leq & \sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)}\nonumber\\ = & \sum_{w' \in \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)} \cdot (|w' - \mathfrak{p}(w')| - 1)\label{eq:aitbar-bound}, \end{align}\tag{18}\] where:

• The first equality uses 13 of 6.

• The following inequality uses the fact that \(w'\) (not being in \(\mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)\)) does not satisfy (P1), which gives \[\begin{align} \frac{\hat{\mu}(w')}{\hat{\mu}(\mathfrak{p}(w')) \cdot \bar \eta_{t-1,\mathfrak{p}(w')}(w' \mid \mathfrak{p}(w'))} \geq \frac{1}{M}.\label{eq:muhat-parent} \end{align}\tag{19}\]

• The following inequality uses 1.

• The final equality rearranges the summation, using that for each \(w' \in \mathcal{S}_{\mathcal{G},M,t}(w)\) we can write \[\begin{align} \mu^\star(w') = \sum_{\substack{x \in \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w) \\ w' \prec x}} \mu^\star(x)\nonumber \end{align}\] as \(\mu^\star\) is a distribution; further, each element \(w' \in \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)\) is preceded by exactly \(|w' - \mathfrak{p}(w')| - 1\) elements of \(\mathcal{S}_{\mathcal{G},M,t}(w)\).

Summing 18 over \(t \geq 1\), we see that \[\begin{align} \sum_{t=1}^n \sum_{w' \in \mathcal{S}_{\mathcal{G},M,t}(w)} \mathbb{P}(\bar A_{i,t}(w')) \leq & \sum_{t=1}^n \sum_{w' \in \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)} \cdot |w' - \mathfrak{p}(w')|\nonumber\\ = & \sum_{w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)} \cdot |w' - w|\nonumber\\ =& \sum_{w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)} \cdot (|w'| - |w|)\nonumber\\ =& \sum_{w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)} \frac{MR \cdot \mu^\star(w')}{\hat{\mu}(w)} \cdot |w'| - \frac{MR \cdot \mu^\star(w)}{\hat{\mu}(w)} \cdot |w|\nonumber\\ =& MR \cdot \left( \mathbb{E}\left[\sum_{w' \in \mathcal{T}} \frac{\mu^\star(w')}{\hat{\mu}(w')} \cdot |w'| \right] - \frac{\mu^\star(w)}{\hat{\mu}(w)} \cdot |w|\right)\label{eq:barait-final}, \end{align}\tag{20}\] where:

• The first inequality uses 18 for each \(t\).

• The following equality uses again the fact that \(\mu^\star\) is a distribution, writing, for each \(w' \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,t}(w) \subset \mathcal{N}^{\mathsf{append}}_{\mathcal{G},M,t}(w)\), \[\begin{align} \mu^\star(w') = \sum_{\substack{x \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w) \\ w' \prec x}} \mu^\star(x)\nonumber. \end{align}\] Moreover, for each \(w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)\), if we choose \(t\) so that \(w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t}(w) \backslash \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M,t-1}(w)\), there is some \(w_s \in \mathcal{N}^{\mathsf{int}}_{\mathcal{G},M,s}(w)\) for each \(1 \leq s < t\) so that \(w_s \prec w'\), and summing \(|w_s - \mathfrak{p}(w_s)| = |w_s - w_{s-1}|\) over \(1 \leq s < t\) gives \(|w' - w|\).

• The following equality uses the fact that \(|w' - w| = |w'| - |w|\) for \(w \succ w\).

• The following equality uses that \(\mu^\star\) is a distribution and \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)\) is a simple \(w\)-cut (2).

• The final equality uses 14 of 6, which gives \(\mathbb{E}[\mathsf{occ}(w',\mathcal{T})] = \hat{\mu}(w')/\hat{\mu}(w)\) for each \(w' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{G},M}(w)\).

The claim of the lemma follows by combining 20 with 17 together with the fact that \(|w'| - |w| \geq 1\) for all \(w' \in \mathcal{T}\) and the fact that \(\mathbb{E}\left[ \sum_{w' \in \mathcal{T}} \frac{\mu^\star(w')}{\hat{\mu}(w')} \right] \geq 1/R\) (which follows from 14 of 6). ◻

Proof. Consider any iteration \(j\) for which \(\mathcal{T}_j \cap \Sigma^{<n} \neq \emptyset\); 5 gives that for any such \(j\), we have \(|\mathcal{F}^{j+1}| \leq |\mathcal{F}^j| \cdot \frac{R^2}{\bar R} \leq |\mathcal{F}^j|/2\). Thus, the number of iterations \(j\) for which \(\mathcal{T}_j \cap \Sigma^{<n} \neq \emptyset\) is bounded above by \(\log_2 |\mathcal{F}|\). Since \(|\mathcal{T}_j| \leq \bar R\) almost surely for all \(j\) by the structure of 2, and all elements of \(\mathcal{S}^{j'} \backslash \mathcal{S}^0\) for any \(j' \in [J]\) are elements of some \(\mathcal{T}^j\) for some \(j < j'\), it follows that \(|\mathcal{S}^{j'}| \leq N + \bar R \cdot \log_2 |\mathcal{F}|\) for all \(j' \geq 1\).

Further, in any iteration \(j\) for which \(\mathcal{T}^j \cap \Sigma^{<n} = \emptyset\), we have \(|\mathcal{S}^{j} \cap \Sigma^{<n}| = |\mathcal{S}^{j-1} \cap \Sigma^{<n}| - 1\). It follows that \(J \leq \log_2 |\mathcal{F}| + \max_{j \geq 1} |\mathcal{S}^j| \leq 2 \bar R \cdot \log_2 |\mathcal{F}| + N\). ◻

Proof. For a fixed \(x \in \Sigma^n\), define \[\begin{align} \Phi_x(\mathcal{T}) := \sum_{x' \in \mathcal{T}} \frac{\mathbb{1}\left\{{x' \preceq x}\right\}}{\hat{\mu}(x')}\nonumber. \end{align}\] for any multiset \(\mathcal{T}\) of particles. We claim that \((\Phi_x(\mathcal{S}^j))_{j \geq 0}\) is a martingale with respect to \((\mathscr{F}^j)_{j \geq 0}\).

Fix any \(j \geq 1\). If \(j > J\), then \(\mathcal{S}^j = \mathcal{S}^{j-1}\) by definition, and there is nothing to prove. Suppose therefore that \(1 \leq j \leq J\). The update from \(\mathcal{S}^{j-1}\) to \(\mathcal{S}^j\) removes one copy of \(z_j\) from \(\mathcal{S}^{j-1}\) and then adds the multiset \(\mathcal{T}_j\) returned by 2. If \(z_j\not\preceq x\), then no element of \(\mathcal{T}_j\) can be an ancestor of \(x\), and so \(\Phi_x(\mathcal{S}^j) = \Phi_x(\mathcal{S}^{j-1})\). Otherwise, suppose that \(z_j \preceq x\). Conditioned on \(\mathscr{F}^{j-1}\), there is a unique ancestor of \(x\) that can belong to \(\mathcal{T}_j\), namely the unique ancestor of \(x\) in \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^{j},\bar R}(z_j)\); denote this element by \(w_j\). Thus, we have \[\begin{align} \mathbb{E}\left[ \sum_{w \in \mathcal{T}_j} \frac{\mathbb{1}\left\{{w \preceq x}\right\}}{\hat{\mu}(w)} \mid \mathscr{F}^{j-1}\right] =& \mathbb{E}\left[ \frac{\mathsf{occ}(w_j, \mathcal{T}_j)}{\hat{\mu}(w_j)} \mid \mathscr{F}^{j-1}\right] \nonumber\\ =& \frac{\hat{\mu}(w_j)}{\hat{\mu}(z_j)} \cdot \frac{1}{\hat{\mu}(w_j)} = \frac{1}{\hat{\mu}(z_j)}\nonumber, \end{align}\] where the second equality uses 14 of 6.

Hence, on the (\(\mathscr{F}^{j-1}\)-measurable) event that \(z_j \preceq x\), we have \[\begin{align} \mathbb{E}\!\left[\Phi_x(\mathcal{S}^j)-\Phi_x(\mathcal{S}^{j-1}) \mid \mathscr{F}^{j-1} \right] = -\frac{1}{\hat{\mu}(z_j)} + \mathbb{E}\left[ \sum_{w \in \mathcal{T}_j} \frac{\mathbb{1}\left\{{w \preceq x}\right\}}{\hat{\mu}(w)} \mid \mathscr{F}^{j-1}\right] = 0.\nonumber \end{align}\]

Thus \((\Phi_x(\mathcal{S}^j))_{j \geq 0}\) is a martingale. At time \(0\), the multiset \(\mathcal{S}^0\) consists of \(N\) copies of the empty sequence, so by the convention \(\hat{\mu}(\emptyset) = 1\) we have \[\begin{align} \Phi_x(\mathcal{S}^0) = \frac{N}{\hat{\mu}(\emptyset)} = N.\nonumber \end{align}\] Combining this base case with the martingale property yields \(\mathbb{E}[\Phi_x(\mathcal{S}^j)] = N\) for every \(j \geq 0\), which is exactly the claimed identity. ◻

Proof. Fix \(x \in \Sigma^n\). Note that \(J\) is a stopping time for the filtration \((\mathscr{F}^j)_{j\geq 0}\). The optional stopping theorem gives \[\begin{align} \mathbb{E}\left[ \sum_{x' \in \mathcal{S}^J} \frac{\mathbb{1}\left\{{x' \preceq x}\right\}}{\hat{\mu}(x')} \right] = \mathbb{E}[\Phi_x(\mathcal{S}^J)] = \mathbb{E}[\Phi_x(\mathcal{S}^0)] = N\nonumber. \end{align}\] By definition of \(J\), every element of \(\mathcal{S}^J = \mathcal{S}^{\mathsf{term}}\) has length \(n\). Since \(x \in \Sigma^n\), the condition \(x' \preceq x\) for \(x' \in \mathcal{S}^J\) is equivalent to \(x' = x\). Together with the assumption that \(\mu^\star(x) = \hat{\mu}(x)\) for \(x \in \Sigma^n\), this gives \(\mathbb{E}\left[ \sum_{x' \in \mathcal{S}^J} \frac{\mathbb{1}\left\{{x' = x}\right\}}{\mu^\star(x')} \right] = N,\) which yields the desired statement after rearranging. ◻

Proof. Fix any \(j \geq 1\). If \(j > J\), then \(M_j = M_{j-1}\) by definition, so the claim is immediate. For each \(1 \leq j \leq J\), we have \[\begin{align} M_j - M_{j-1} = \sum_{x' \in \mathcal{T}_j} \frac{\mu^\star(x')}{\hat{\mu}(x')} - \frac{\mu^\star(z_j)}{\hat{\mu}(z_j)}\nonumber. \end{align}\] It therefore suffices to show \[\begin{align} \mathbb{E}\left[ \sum_{x' \in \mathcal{T}_j} \frac{\mu^\star(x')}{\hat{\mu}(x')} \mid \mathscr{F}^{j-1} \right] = \frac{\mu^\star(z_j)}{\hat{\mu}(z_j)}.\label{eq:ij-mtgl} \end{align}\tag{21}\] Recall that \(\mathcal{T}_j \subset \mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^j, \bar R}(z_j)\) by 4. Then we may compute \[\begin{align} \mathbb{E}\left[ \sum_{x' \in \mathcal{T}_j} \frac{\mu^\star(x')}{\hat{\mu}(x')} \mid \mathscr{F}^{j-1} \right] =& \sum_{x' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^j, \bar R}(z_j)} \frac{\mu^\star(x')}{\hat{\mu}(x')} \cdot \mathbb{E}[\mathsf{occ}(x', \mathcal{T}_j) \mid \mathscr{F}^{j-1}] \nonumber\\ =& \sum_{x' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^j, \bar R}(z_j)} \frac{\mu^\star(x')}{\hat{\mu}(x')} \cdot \frac{\hat{\mu}(x')}{\hat{\mu}(z_j)} \nonumber\\ =& \frac{1}{\hat{\mu}(z_j)} \sum_{x' \in \mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^j, \bar R}(z_j)} \mu^\star(x') = \frac{\mu^\star(z_j)}{\hat{\mu}(z_j)}\label{eq:mij-mtgl}, \end{align}\tag{22}\] where the second equality uses 14 of 6 and the final equality uses the fact that \(\mathcal{N}^{\mathsf{fin}}_{\mathcal{F}^j, \bar R}(z_j)\) is a simple \(z_j\)-cut (2). ◻

Proof. Let \(T := 2 \bar R \cdot \log_2 |\mathcal{F}| + N\), so that 8 ensures that \(J \leq T\) with probability \(1\). For \(1 \leq j \leq J\), \(|\mathcal{T}_j| \leq \bar R\) almost surely and so \(0 \leq \sum_{x' \in \mathcal{T}_j} \frac{\mu^\star(x')}{\hat{\mu}(x')} \leq R \cdot \bar R\); thus \(|M_j - M_{j-1}| \leq R \bar R\) for all \(j\). Using the fact that a random variable \(M\) taking values in \([0,A]\) satisfies \(\log \mathbb{E}[\exp(\lambda \cdot (A - \mathbb{E}[A]))] \leq \lambda^2 A^2 / 8\), together with the fact that \(\mathbb{E}[M_j - M_{j-1} \mid \mathscr{F}^{j-1}] = 0\) (which was established in 11), we may conclude that for any \(\lambda \in \mathbb{R}\), \[\begin{align} \log \mathbb{E}\left[ \exp(\lambda \cdot (M_j - M_{j-1})) \mid \mathscr{F}^{j-1}\right] \leq \lambda^2 (R \bar R)^2\label{eq:mgf-bound-for-freedman}. \end{align}\tag{23}\] Since \(M_j=M_J\) for all \(j \geq J\), iterating the preceding conditional moment-generating function bound up to the deterministic time \(T\) gives, for every \(\lambda \geq 0\), \[\begin{align} \log \mathbb{E}\left[\exp(\lambda \cdot (M_J-M_0))\right] \leq T\lambda^2(R\bar R)^2.\nonumber \end{align}\] Therefore, for every \(s > 0\), \(\mathbb{P}(M_J-M_0 > s) \leq \exp\left(-\frac{s^2}{4T(R\bar R)^2}\right).\) Using \(M_0=N\) and \(R \geq 1\), it follows that \[\begin{align} \mathbb{E}\left[\left(\frac{M_J}{2RN}-1\right)_+\right] &= \frac{1}{2RN}\int_{(2R-1)N}^{\infty} \mathbb{P}(M_J-M_0 > s)\,ds \nonumber\\ &\leq \frac{1}{2RN}\int_N^{\infty} \exp\left(-\frac{s^2}{4T(R\bar R)^2}\right)\,ds \nonumber\\ &\leq \frac{T(R\bar R)^2}{RN^2}\exp\left(-\frac{N^2}{4T(R\bar R)^2}\right) \leq \frac{\delta}{2R},\nonumber \end{align}\] where the final inequality follows from the choice of \(N\) in 3, after increasing the absolute constant \(C_{\mathsf{N}}\) if necessary.

Moreover, using 23 , by 23 and a union bound over \(j \in [T]\) it follows that for any \(\lambda \in \mathbb{R}\), with probability at least \(1-\delta/(4R)\), for all \(1 \leq j \leq J\), we have \[\begin{align} \lambda \cdot (M_j - M_0) \leq j \cdot \lambda^2 (R \bar R)^2 + \log(4RT/\delta)\nonumber. \end{align}\] Rearranging and choosing \(\lambda =\pm\frac{\sqrt{\log (4RT/\delta)}}{\sqrt{T} \cdot R \bar R}\) gives that, with probability \(1-\delta/2R\), \[\begin{align} \max_{1 \leq j \leq J} |M_j - M_0| \leq & |\lambda |\cdot j (R \bar R)^2 + \frac{\log (4RT/\delta)}{|\lambda|} \leq O \left( R \bar R \cdot \sqrt{T \log (R\log_2(|\mathcal{F}|) N/\delta)} \right) \nonumber\\ \leq & O \left(R \bar R \sqrt{(\bar R \cdot \log_2 |\mathcal{F}| + N) \cdot \log (R\log_2(|\mathcal{F}|) N/\delta)} \right) \leq \frac{N}{2} = \frac{M_0}{2}\nonumber, \end{align}\] where the final inequality uses the choice of \(N\) in 3 for an appropriately large constant \(C_{\mathsf{N}}\). ◻

Proof. Fix one outer-loop iteration (i.e., over \(k \in [K]\)). Let \(X\) denote the random variable which is equal to the sample returned in that iteration if the final Bernoulli step succeeds, and is equal to \(\bot\) otherwise. By 10, we have, for any set \(\mathcal{A}\subseteq \Sigma^n\), \[\begin{align} \mathbb{P}(X\in \mathcal{A}) = \mathbb{E}\left[ \sum_{x \in \mathcal{A}} \frac{\mathsf{occ}(x, \mathcal{S}^{\mathsf{term}})}{|\mathcal{S}^{\mathsf{term}}|} \cdot \min \left\{ 1, \frac{|\mathcal{S}^{\mathsf{term}}|}{2RN} \right\} \right] \leq \frac{1}{2R} \cdot \mu^\star(\mathcal{A}).\label{eq:single-round-output-law} \end{align}\tag{24}\] For the lower bound, note that the pointwise inequality \[\begin{align} \sum_{x \in \mathcal{A}} \frac{\mathsf{occ}(x, \mathcal{S}^{\mathsf{term}})}{|\mathcal{S}^{\mathsf{term}}|} \cdot \min \left\{1, \frac{|\mathcal{S}^{\mathsf{term}}|}{2RN}\right\} \geq \frac{1}{2RN}\sum_{x \in \mathcal{A}}\mathsf{occ}(x,\mathcal{S}^{\mathsf{term}}) - \left(\frac{|\mathcal{S}^{\mathsf{term}}|}{2RN}-1\right)_+ \nonumber \end{align}\] holds for every realization of \(\mathcal{S}^{\mathsf{term}}\), where the left-hand side is interpreted as \(0\) if \(|\mathcal{S}^{\mathsf{term}}|=0\). Therefore, \[\begin{align} \mathbb{P}(X \in \mathcal{A}) &\geq \frac{1}{2RN}\mathbb{E}\left[\sum_{x \in \mathcal{A}} \mathsf{occ}(x,\mathcal{S}^{\mathsf{term}})\right] - \mathbb{E}\left[\left(\frac{|\mathcal{S}^{\mathsf{term}}|}{2RN}-1\right)_+\right] \nonumber\\ &\geq \frac{1}{2R} \cdot \mu^\star(\mathcal{A}) - \frac{\delta}{2R}.\label{eq:single-round-output-lb} \end{align}\tag{25}\] It follows that \(\frac{1}{2R} - \frac{\delta}{2R}\leq \mathbb{P}(X \neq \perp) \leq \frac{1}{2R}\), and so \[\begin{align} \mu^\star(\mathcal{A}) - \delta\leq \mathbb{P}(X \in \mathcal{A}\mid X \neq \perp) \leq \mu^\star(\mathcal{A}) \cdot \frac{1}{1-\delta} \leq \mu^\star(\mathcal{A}) \cdot (1 + \delta)\label{eq:mustar-close}. \end{align}\tag{26}\] Let \(\tilde{\mu}^{\mathsf{alg}}\in \Delta(\Sigma^n)\) be the distribution defined by \(\tilde{\mu}^{\mathsf{alg}}(x) := \mathbb{P}(X = x \mid X \neq \perp)\). Then 26 gives that \(D_{\mathsf{TV}}({\mu^\star}, {\tilde{\mu}^{\mathsf{alg}}}) \leq \delta\). By our choice of \(K = \lceil 4R \log_2(1/\delta) \rceil\) and the fact that each outer-loop iteration produces a symbol which is not \(\perp\) with probability at least \(\frac{1}{2R} - \frac{\delta}{2R} \geq \frac{1}{4R}\), with probability at least \(1-\delta\), some outer loop iteration will produce a symbol which is not \(\perp\), and which is therefore distributed according to \(\tilde{\mu}^{\mathsf{alg}}\). It follows that \(D_{\mathsf{TV}}({\mu^\star}, {\mu_{\mathsf{alg}}}) \leq 2\delta\); the claimed result follows by rescaling \(\delta\). ◻

Proof. For each \(j \geq 1\), we let the random variable \(V_j\) denote the number of oracle calls to \(\hat{\mu}\) made by 2 in Line [line:rs-call] of 3 during step \(j\) of the algorithm. By 7, we have \[\begin{align} \mathbb{E}[V_j \mid \mathscr{F}^{j-1}] \leq O \left(|\Sigma| \cdot R \cdot \bar R^2 \right) \cdot \mathbb{E}\left[ \sum_{x \in \mathcal{T}_j} \frac{\mu^\star(x)}{\hat{\mu}(x)} \cdot |x| - \frac{\mu^\star(z_j)}{\hat{\mu}(z_j)} \cdot |z_j| \mid \mathscr{F}^{j-1} \right]\label{eq:vj-update}. \end{align}\tag{27}\] Next, we define a random variable \[\begin{align} W_j = \sum_{x \in \mathcal{S}_j}\frac{\mu^\star(x)}{\hat{\mu}(x)} \cdot |x|\nonumber. \end{align}\] Note that \[\begin{align} W_j = W_{j-1} - \frac{\mu^\star(z_j)}{\hat{\mu}(z_j)} \cdot |z_j| + \sum_{x \in \mathcal{T}_j} \frac{\mu^\star(x)}{\hat{\mu}(x)} \cdot |x| \label{eq:wj-update}, \end{align}\tag{28}\] so that 27 28 give \[\begin{align} \mathbb{E}[V_j \mid \mathscr{F}^{j-1}] \leq O \left(|\Sigma| \cdot R \cdot \bar R^2 \right) \cdot \mathbb{E}[W_j - W_{j-1} \mid \mathscr{F}^{j-1}].\label{eq:vj-wj} \end{align}\tag{29}\] It follows that \[\begin{align} \mathbb{E}\left[ \sum_{j=1}^J V_j \right] \leq O(|\Sigma| R \bar R^2) \cdot \mathbb{E}[W_J] = O(n \cdot |\Sigma| R \bar R^2) \cdot \mathbb{E}[M_J] = O(Nn \cdot |\Sigma| R \bar R^2)\nonumber. \end{align}\] Let \(T := 2 \bar R \cdot \log_2 |\mathcal{F}| + N\), so that \(J \leq T\) almost surely by 8. Fix one outer-loop iteration of 3. For each \(j \in [T]\), define \(\Gamma_j := V_j - \mathbb{E}[V_j \mid \mathscr{F}^{j-1}],\) where for \(j > J\) we interpret \(V_j := 0\). Then \((\sum_{s=1}^j \Gamma_s)_{j \in [T]}\) is a martingale. By the almost-sure bound in 7, \(|\Gamma_j| \leq O(|\Sigma| \bar R n)\) for every \(j\). Applying Azuma’s inequality, with probability at least \(1-\delta/(4K)\) we have \[\begin{align} \sum_{j=1}^J V_j \leq \sum_{j=1}^J \mathbb{E}[V_j \mid \mathscr{F}^{j-1}] + O\left(|\Sigma| \bar R n \sqrt{T \log \frac{K}{\delta}}\right).\label{eq:oracle-calls-v-azuma} \end{align}\tag{30}\] Next, define \[\begin{align} \Delta_j := (W_j - W_{j-1}) - \mathbb{E}[W_j - W_{j-1} \mid \mathscr{F}^{j-1}],\nonumber \end{align}\] where for \(j > J\) we interpret \(W_j := W_J\). Then \((\sum_{s=1}^j \Delta_s)_{j \in [T]}\) is a martingale. Since \(|\mathcal{T}_j| \leq \bar R\) almost surely and \(\mu^\star(x)/\hat{\mu}(x) \leq R\) for every \(x\), we have \[\begin{align} |W_j - W_{j-1}| \leq Rn(\bar R + 1) = O(R \bar R n)\nonumber \end{align}\] for every \(j\), and hence \(|\Delta_j| \leq O(R \bar R n)\). Applying Azuma’s inequality, with probability at least \(1-\delta/(4K)\) we therefore have \[\begin{align} \sum_{j=1}^J \mathbb{E}[W_j - W_{j-1} \mid \mathscr{F}^{j-1}] \leq W_J - W_0 + O\left(R \bar R n \sqrt{T \log \frac{K}{\delta}}\right).\label{eq:oracle-calls-w-azuma} \end{align}\tag{31}\] Since \(W_0 = 0\), 29 31 imply that, with probability at least \(1-\delta/(4K)\), \[\begin{align} \sum_{j=1}^J \mathbb{E}[V_j \mid \mathscr{F}^{j-1}] \leq O(|\Sigma| R \bar R^2) \cdot W_J + O\left(|\Sigma| R^2 \bar R^3 n \sqrt{T \log \frac{K}{\delta}}\right).\label{eq:oracle-calls-predictable} \end{align}\tag{32}\] Since \[\begin{align} N = C_{\mathsf{N}} \left\lceil \sqrt{\log |\mathcal{F}|} \cdot R^2 \bar R^2 \left( \log \frac{R \log |\mathcal{F}|}{\delta}\right) \right\rceil\nonumber \end{align}\] and by 12 we have, after increasing \(C_{\mathsf{N}}\) if needed, that \(M_J \leq 3N/2\) with probability at least \(1-\delta/(4K)\), it follows that with the same probability \(W_J \leq n M_J \leq 3nN/2.\) Combining this with 30 32 yields that, with probability at least \(1-3\delta/(4K)\), \[\begin{align} \sum_{j=1}^J V_j \leq O(|\Sigma| R \bar R^2) \cdot nN + O\left(|\Sigma| R^2 \bar R^3 n \sqrt{T \log \frac{K}{\delta}}\right) + O\left(|\Sigma| \bar R n \sqrt{T \log \frac{K}{\delta}}\right).\nonumber \end{align}\] Using \(T = O(\bar R \log |\mathcal{F}| + N)\) together with \(K = O(R \log(1/\delta))\), the choice of \(N\) ensures that the second and third terms are both absorbed into the main term for a sufficiently large absolute constant \(C_{\mathsf{N}}\). Therefore, one outer-loop iteration uses at most \[\begin{align} O\left(n \cdot |\Sigma| \cdot R \bar R^2 \cdot \left\lceil \sqrt{\log |\mathcal{F}|} \cdot R^2 \bar R^2 \left(\log \frac{R \log |\mathcal{F}|}{\delta}\right) \right\rceil \right)\nonumber \end{align}\] oracle calls with probability at least \(1-\delta/K\). Summing over the \(K\) outer-loop iterations and using a union bound proves that the total number of oracle calls made by 3 is at most \[\begin{align} O\left(n \cdot |\Sigma| \cdot K \cdot R \bar R^2 \cdot \left\lceil \sqrt{\log |\mathcal{F}|} \cdot R^2 \bar R^2 \left(\log \frac{R \log |\mathcal{F}|}{\delta}\right) \right\rceil \right)\nonumber, \end{align}\] with probability at least \(1-\delta\). Using \(\bar R = 2R^2\) and \(K = \lceil 4R\log_2(1/\delta) \rceil\) gives the second displayed bound in the lemma statement. ◻

Proof of 3. Run 3 with failure tolerance \(\delta/2\). By 13, its output distribution \(\hat{\nu}'\) satisfies \(D_{\mathsf{TV}}({\mu^\star}, {\hat{\nu}'}) \leq \delta/2\). By 14, with probability at least \(1-\delta/2\), the number of oracle calls made by the algorithm is at most \[\begin{align} O\left(n \cdot |\Sigma| \cdot R^{12} \cdot \sqrt{\log |\mathcal{F}|} \cdot \log \frac{1}{\delta} \cdot \left(\log \frac{R \log |\mathcal{F}|}{\delta}\right) \right)\label{eq:final-oracle-ub}. \end{align}\tag{33}\] We can modify 3 so that, whenever its number of oracle calls reaches the threshold in 33 , it aborts and outputs an arbitrary symbol. This changes its output distribution by at most \(\delta/2\) in total variation distance, meaning that the resulting output distribution, which we denote by \(\hat{\nu}\), satisfies \(D_{\mathsf{TV}}({\mu^\star}, {\hat{\nu}}) \leq \delta\). ◻

Proof. For a leaf \(x \in \{0,1\}^n\), define \[\begin{align} W(x) := \prod_{j=1}^n \omega(x_{1:j}), \qquad \hat{W}(x) := \prod_{j=1}^n \hat{\omega}(x_{1:j}).\nonumber \end{align}\] Then \(\mu(x) = \hat{\mu}(x) = \hat{W}(x)/\hat{Z}\) and \(\mu_{\mathsf{ideal}}(x) = W(x)/Z\) for \(x \in \{0,1\}^n\).

Let \(\mathcal{E} \subseteq \{0,1\}^n\) be the set of leaves \(x\) such that \(x_1=1-v^{\mathsf{init}}\) and \[\begin{align} \mathsf{query}_a(x) \notin B(\mathsf{base}_a(x)) \qquad \text{for every } 0 \leq a \leq r-1.\nonumber \end{align}\] We claim that for every leaf \(x \in \{0,1\}^n\), \[\begin{align} \hat{W}(x) = \bigl(1+\gamma \cdot \mathbb{1}\left\{{x \in \mathcal{E}}\right\}\bigr) \cdot W(x).\label{eq:What-over-W} \end{align}\tag{44}\] Indeed, if \(x_1=v^{\mathsf{init}}\), then \(x \not \in \mathcal{E}\) and the defining condition for \(\hat{\omega}\) always selects \(\phi\), so \(\hat{\omega}\) and \(\omega\) agree at every prefix of \(x\), including the root. Hence \(\hat{W}(x)=W(x)\). Now suppose that \(x_1=1-v^{\mathsf{init}}\). At the root we have \(\hat{\omega}(x_1)=1+\gamma\) whereas \(\omega(x_1)=1\). If \(x \in \mathcal{E}\), then for every index \(a < r\) we have \(\mathsf{query}_a(x) \in A(\mathsf{base}_a(x)) \cup C(\mathsf{base}_a(x))\), so \[\begin{align} \phi(\mathsf{base}_a(x);\mathsf{query}_a(x)) = \tilde{\phi}(\mathsf{base}_a(x);\mathsf{query}_a(x)).\nonumber \end{align}\] Thus, by the definitions in 40 41 38 , \(\hat{\omega}(x_{1:i}) = \omega(x_{1:i})\) for all \(i \geq 2\), and so \(\hat{W}(x) = (1+\gamma) \cdot W(x)\). Finally, if \(x \notin \mathcal{E}\), and let \(a_\star\) be the least index in \(\{0,\ldots,r-1\}\) such that \(\mathsf{query}_{a_\star}(x) \in B(\mathsf{base}_{a_\star}(x)).\) The definitions of \(\omega,\hat{\omega}\) give that \(\hat{\omega}(x_{1:i}) = \omega(x_{1:i})\) for all \(i \geq 2\) with \(i \neq 2(a_\star +1)k+1\), and for \(i = 2(a_\star+1)k+1\), we have \(\hat{\omega}(x_{1:i}) \cdot (1+\gamma) = \omega(x_{1:i})\). Then we again have \(\hat{W}(x) = W(x)\).

Let \(p := \mu_{\mathsf{ideal}}(\mathcal{E})\). Summing 44 over all leaves shows that \[\begin{align} \hat{Z} = \sum_{x \in \{0,1\}^n} \hat{W}(x) = \sum_{x \in \{0,1\}^n} W(x) + \gamma \sum_{x \in \mathcal{E}}W(x) = Z \cdot (1 + \gamma p).\label{eq:zhat-z-comparison} \end{align}\tag{45}\] Using that \(\mu(x) = \hat{\mu}(x)\) for \(x \in \{0,1\}^n\), it follows that \[\begin{align} \mu(x) = \frac{1+\gamma \cdot \mathbb{1}\left\{{x \in \mathcal{E}}\right\}}{1+\gamma p} \cdot \mu_{\mathsf{ideal}}(x).\label{eq:mu-vs-muideal-pointwise} \end{align}\tag{46}\] Therefore \[\begin{align} D_{\mathsf{TV}}({\mu}, {\mu_{\mathsf{ideal}}}) &= \frac{1}{2} \sum_{x \in \{0,1\}^n} \mu_{\mathsf{ideal}}(x) \cdot \left|\frac{1+\gamma \cdot \mathbb{1}\left\{{x \in \mathcal{E}}\right\}}{1+\gamma p} - 1\right|\nonumber\\ &= \frac{\gamma p(1-p)}{1+\gamma p} \leq p.\label{eq:tvd-by-p} \end{align}\tag{47}\]

It remains to bound \(p\). Under \(\mu_{\mathsf{ideal}}\), the probability of taking the root edge \(x_1 = 1-v^{\mathsf{init}}\) is \(1/(2+\gamma)\), because the two root subtrees have identical total \(W\)-mass below the root and the two root weights are \(1\) and \(1+\gamma\). Next, fix any \(0 \leq a \leq r-1\) and any \(y \in \{0,1\}^{2ak+1}\) with \(y_1 = 1-v^{\mathsf{init}}\) and so that for all \(b < a\), \(\phi(\mathsf{base}_b(y);\mathsf{query}_b(y)) = \tilde{\phi}(\mathsf{base}_b(y);\mathsf{query}_b(y))\). For each \(z \in \{0,1\}^k\), there is a unique “key” \(\kappa(z) \in \{0,1\}^k\) for which \(\mathsf{key}_a(y \circ z \circ \kappa(z)) = \psi(y;z)\). Moreover, we have \[\begin{align} \frac{W(y \circ z \circ \kappa(z))}{W(y)} = \prod_{j=2ak+2}^{2(a+1)k+1} \omega((y \circ z \circ \kappa(z))_{1:j}) = 1 + \gamma \cdot \phi(y;z).\nonumber \end{align}\] Therefore, under \(x \sim \mu_{\mathsf{ideal}}\), conditioned on \(x_{1:2ak+1} = y\), the conditional probability that \(\mathsf{query}_a(x) \notin B(y)\) is \[\begin{align} \frac{(1+\gamma)|A(y)| + |C(y)|}{(1+\gamma)(|A(y)|+|B(y)|) + |C(y)|} &= 1 - \frac{(1+\gamma)|B(y)|}{2^k + \gamma 2^{k-1}}\nonumber\\ &= 1 - \frac{1+\gamma}{1+\gamma/2} \cdot \epsilon\nonumber\\ &\leq 1-\epsilon,\label{eq:no-B-probability} \end{align}\tag{48}\] where we used 37 . Since the right-hand side of 48 is uniform over all such prefixes \(y\), we obtain \[\begin{align} p = \mu_{\mathsf{ideal}}(\mathcal{E}) \leq \frac{1}{2+\gamma} \cdot (1-\epsilon)^r \leq e^{-\epsilon r}.\nonumber \end{align}\] Combining this with 47 proves the lemma. ◻

Proof. For \(x \in \{0,1\}^{\leq n}\), write \[\begin{align} P(x) := \prod_{j=1}^{|x|} \hat{\omega}(x_{1:j}),\qquad T(x) := \sum_{z \in \{0,1\}^{m-|x|}} \prod_{j=|x|+1}^{m} \hat{\omega}((x\circ z)_{1:j}).\nonumber \end{align}\] Then \[\begin{align} \hat{\mu}(x) = \frac{P(x)}{\hat{Z}_{|x|}},\qquad \mu(x) = \frac{P(x)\,T(x)}{\hat{Z}}, \qquad \frac{\mu(x)}{\hat{\mu}(x)} = \frac{T(x) \hat{Z}_{|x|}}{\hat{Z}}.\label{eq:muhat-mu-factorization} \end{align}\tag{49}\] In particular, \(\hat{\mu}(x)=0\) if and only if \(P(x)=0\). Moreover, for \(x \in \{0,1\}^{\leq n}\), whenever \(P(x)>0\) there is at least one leaf descendent of \(x\) with positive \(\hat{\omega}\)-mass, and therefore \(\mu(x)>0\) if and only if \(\hat{\mu}(x)>0\).

We next bound the possible values of \(T(x)\) at depths \(1 \pmod{2k}\). For \(0 \leq a \leq r\) and \(x \in \{0,1\}^{2ak+1}\), we say that \(x\) is switched if either \(x_1 = v^{\mathsf{init}}\), or there is some \(0 \leq b < a\) such that \(\mathsf{query}_b(x) \in B(\mathsf{base}_b(x)).\) Otherwise we say that \(x\) is unswitched.

For any \(i \leq n\), we have \(\hat{Z} = \sum_{x \in \{0,1\}^i} P(x) T(x)\), and \(\hat{Z}_i = \sum_{x \in \{0,1\}^i} P(x)\). Thus, for any \(0 \leq a \leq r-1\) and \(x \in \{0,1\}^{2ak + 1}\), we have \[\begin{align} \frac{1}{(1+\gamma) \cdot \hat{Z}_{2ak+1}} = \frac{G_a}{\sum_{x' \in \{0,1\}^{2ak+1}} P(x') \cdot (1+\gamma) G_a} \leq \frac{T(x)}{\hat{Z}} \leq \frac{(1+\gamma) \cdot G_a}{\sum_{x' \in \{0,1\}^{2ak+1}} P(x') \cdot G_a} = \frac{1+\gamma}{\hat{Z}_{2ak+1}}\nonumber, \end{align}\] and it follows from 49 that \(1/(1+\gamma) \leq \mu(x) / \hat{\mu}(x) \leq 1+\gamma\). In the above display, both inequalities use 5: the first inequality uses the claim to bound \(G_a \leq T(x)\) for all \(x \in \{0,1\}^{2ak+1}\) and \((1+\gamma) G_a \geq T(x')\) for all \(x' \in \{0,1\}^{2ak+1}\); the second inequality uses the claim to bound \(T(x) \leq (1+\gamma) \cdot G_a\) and \(T(x') \geq G_a\).

Having established the statement of 17 for \(x \in \{0,1\}^{\leq n}\) with \(|x| = 2ak+1\) for some \(0 \leq a \leq r\), we may now use this to extend the result for the remaining values of \(x \in \{0,1\}^{\leq n}\):

4.3.0.1 Case 1: \(|x| \pmod{2k} \in \{k+1, \ldots, 2k \}\).

For any \(0 \leq a \leq r-1\) and \(k+1 \leq a' \leq 2k\), we have \[\begin{align} \hat{Z}_{2ak + a'} = \sum_{x \in \{0,1\}^{2ak + a'}} P(x) \in [(1+\gamma)^{-1},1] \cdot \sum_{x \in \{0,1\}^{2ak + 2k +1}} P(x) = [(1+\gamma)^{-1} \cdot\hat{Z}_{2ak + 2k +1}, \hat{Z}_{2ak + 2k +1}]\nonumber, \end{align}\] since for each \(x \in \{0,1\}^{2ak + a'}\) with \(P(x) > 0\), there is a unique \(z \in \{0,1\}^{2k+1-a'}\) so that \(P(x \circ z) > 0\), and such \(z\) satisfies \(P(x \circ z) = P(x) \cdot \hat{\omega}(x \circ z)\). For such \(x,z\), we have \(T(x \circ z)\cdot \hat{\omega}(x \circ z) = T(x)\), which means that \[\begin{align} \frac{\mu(x)}{\hat{\mu}(x)} = \frac{T(x) \cdot \hat{Z}_{2ak+a'}}{\hat{Z}} = \frac{T(x \circ z) \cdot \hat{\omega}(x \circ z) \cdot \hat{Z}_{2ak+a'}}{\hat{Z}} \in [(1+\gamma)^{-1}, (1+\gamma)] \cdot \frac{\mu(x \circ z)}{\hat{\mu}(x \circ z)}. \end{align}\] Thus, by 5, \(\frac{\mu(x)}{\hat{\mu}(x)} \in [(1+\gamma)^{-2}, (1+\gamma)^2]\). As a consequence of this argument and of 5, we also see that for all \(x \in \{0,1\}^{2ak + k+1}\) (for any \(0 \leq a \leq r-1\)), we have \[\begin{align} T(x) \in [G_a/(1+\gamma), (1+\gamma)G_a].\label{eq:tx-kp1} \end{align}\tag{50}\]

4.3.0.2 Case 2: \(|x| \pmod{2k} \in \{2, \ldots, k \}\).

For any \(0 \leq a \leq r-1\) and \(1 \leq a' \leq k-1\), we have \[\begin{align} \hat{Z}_{2ak + 1 + a'} = \sum_{x \in \{0,1\}^{2ak + 1 + a'}} P(x) = 2^{a'-k} \cdot \hat{Z}_{2ak + k+1} \in 2^{a'-k} \cdot \hat{Z}_{2ak+2k+1} \cdot [(1+\gamma)^{-1},1]\nonumber, \end{align}\] since for any \(x \in \{0,1\}^{2ak + 1 + a'}\), we have \(P(x) = P(x_{1:2ak + k+1})\). Moreover, for such \(x\), \[\begin{align} T(x) = \sum_{x' \in \{0,1\}^{2ak+k+1} :\;x' \succ x} T(x') \in \left[ {2^{k-a'} \cdot G_a}/{(1+\gamma)}, 2^{k-a'} \cdot G_a \cdot (1+\gamma) \right],\nonumber \end{align}\] where the final step uses 50 . Thus \[\begin{align} \frac{\mu(x)}{\hat{\mu}(x)} = \frac{T(x) \cdot \hat{Z}_{2ak+1+a'}}{\hat{Z}} \in \frac{G_a \cdot \hat{Z}_{2ak+2k+1}}{\hat{Z}} \cdot [(1+\gamma)^{-2}, (1+\gamma)]\nonumber, \end{align}\] and it then follows from 5 that \(\frac{\mu(x)}{\hat{\mu}(x)} \in [(1+\gamma)^{-2}, (1+\gamma)^2]\). ◻

Proof. The proof is immediate by symmetry: consider any tuples \(\tau = (v^{\mathsf{init}}, \phi, \psi), \tau' = ((v^{\mathsf{init}})', \phi', \psi') \in \mathcal{H}_{n,k,q,\epsilon}\). Let the mappings \(\hat{\omega}\) corresponding to these two tuples be denoted \(\hat{\omega} = \hat{\omega}_{\tau}, \hat{\omega}'=\hat{\omega}_{\tau'} : \{0,1\}^{\leq n} \to \mathbb{R}_{\geq 0}\). We claim that, for each \(i \leq n\), we can find a permutation \(\pi_i : \{0,1\}^{i} \to \{0,1\}^{i}\) so that \(\prod_{j=1}^i\hat{\omega}(x_{1:j}) = \prod_{j=1}^i \hat{\omega}'(\pi_i(x)_{1:j})\) for all \(x \in \{0,1\}^{i}\). To see this, we may construct the permutations \(\pi_i\) inductively, in blocks of size \(2k\). For the base case, \(\pi_1\) is the identity if \(v^{\mathsf{init}}= (v^{\mathsf{init}})'\), and swaps the bits otherwise. We will suppose (inductively) that we have constructed \(\pi_i\) for \(i \leq 2ak+1\) for some \(a \geq 0\), which satisfy the desired property above and also that \(x \in \{0,1\}^{2ak+1}\) satisfies 39 for \(\phi\) if and only if \(\pi_{2ak+1}(x)\) satisfies 39 for \(\phi'\).

We now construct \(\pi_i\) for the depths in the next block. Fix \(x \in \{0,1\}^{2ak+1}\) and write \(x' := \pi_{2ak+1}(x)\). Let the sets \(A(x), B(x), C(x)\) be defined as in 34 35 36 in terms of \(\phi\), and let \(A'(x'), B'(x'), C'(x')\) be defined similarly in terms of \(\phi'\). Since the sizes of these respective sets match up (per 37 ), we can find a permutation \(\sigma_x : \{0,1\}^k \to \{0,1\}^k\) so that \(\sigma_x(A(x)) = A'(x')\), \(\sigma_x(B(x)) = B'(x')\), and \(\sigma_x(C(x)) = C'(x')\).

We first define the permutations at depths lying in the query block. For \(1 \leq s \leq k\) and \(u \in \{0,1\}^s\), set \(\pi_{2ak+1+s}(x \circ u) := x' \circ u.\) Since all edge weights in the query block are equal to \(1\), this preserves the product of edge weights up to depth \(2ak+1+s\).

It remains to define the permutations inside the key block. Fix \(z \in \{0,1\}^k\) and \(1 \leq s \leq k\). Choose any bijection \(\lambda_{x,z,s}:\{0,1\}^s \to \{0,1\}^s\) satisfying \(\lambda_{x,z,s}\left(\psi(x;z)_{1:s}\right) = \psi'(x';\sigma_x(z))_{1:s}.\) Then for \(v \in \{0,1\}^s\), define \[\begin{align} \pi_{2ak+k+1+s}(x \circ z \circ v) := x' \circ \sigma_x(z) \circ \lambda_{x,z,s}(v).\label{eq:pi-key-block} \end{align}\tag{51}\] For each fixed \(s\), this defines a bijection on \(\{0,1\}^{2ak+k+1+s}\), since \(\pi_{2ak+1}\), \(\sigma_x\), and each \(\lambda_{x,z,s}\) are bijections. Moreover, 51 maps a prefix whose key block agrees with \(\psi(x;z)\) for its first \(s\) coordinates to a prefix whose key block agrees with \(\psi'(x';\sigma_x(z))\) for its first \(s\) coordinates, and maps every other key prefix to one which also fails the corresponding agreement condition. Thus the product of the key-indicator factors is preserved. If \(s<k\), this proves the desired product identity at depth \(2ak+k+1+s\). To deal with depth \(i = 2(a+1)k+1\), we simply note that the choice of \(\sigma_x\) maps \(A(x)\) to \(A'(x')\), \(B(x)\) to \(B'(x')\), and \(C(x)\) to \(C'(x')\), which completes the inductive construction of the permutations \(\pi_i\).

Now, existence of \(\pi_i\) as above implies that \[\begin{align} \sum_{x \in \{0,1\}^i} \prod_{j=1}^i \hat{\omega}(x_{1:j}) = \sum_{x \in \{0,1\}^i} \prod_{j=1}^i \hat{\omega}'(\pi_i(x)_{1:j}) = \sum_{x' \in \{0,1\}^i} \prod_{j=1}^i \hat{\omega}'(x'_{1:j}),\nonumber \end{align}\] as desired. ◻

Proof. The definition of \(\hat{\omega} = \hat{\omega}_\tau\) and \(\hat{\mu} = \hat{\mu}_\tau\) above gives that there is a quantity \(\eta_{v^{\mathsf{init}},\phi}(x) > 0\) depending only on \((v^{\mathsf{init}},\phi)\) and an indicator \(\chi_\psi(x) \in \{0,1\}\) depending only on \(\psi\) such that \[\begin{align} \hat{\mu}_{\tau}(x) = \eta_{v^{\mathsf{init}},\phi}(x) \cdot \chi_\psi(x)\label{eq:muhat-factor-ci} \end{align}\tag{52}\] for all \(x \in \{0,1\}^{\leq n}\). Indeed, \(\eta_{v^{\mathsf{init}},\phi}(x)\) is the product of the positive factors of the form \(1+\gamma\) and \(1+\gamma \cdot \phi(\mathsf{base}_a(x); \mathsf{query}_a(x))\) or \(1+\gamma \cdot \tilde{\phi}(\mathsf{base}_a(x); \mathsf{query}_a(x))\), divided by \(\hat{Z}_{\epsilon,|x|}\), while \(\chi_\psi(x)=1\) if and only if every key block appearing along the path to \(x\) agrees with the corresponding value determined from \(\psi\).

Let \[\begin{align} \mathcal{E}:= & \{ (v^{\mathsf{init}}, \phi, \psi) \mid \hat{\mu}_{v^{\mathsf{init}},\phi,\psi}(x_j) = \mu_j\;\forall j \in [q]\}\nonumber\\ \mathcal{E}_\eta:=& \{(v^{\mathsf{init}},\phi,\psi) \mid \eta_{v^{\mathsf{init}}, \phi}(x_j) = \mu_j \;\forall js.t.\mu_j > 0 \}\nonumber\\ \mathcal{E}_\chi :=& \{(v^{\mathsf{init}}, \phi,\psi) \mid \chi_\psi(x_j) = 1 \;\forall js.t.\mu_j > 0, \;\chi_\psi(x_j) = 0 \;\forall js.t.\mu_j = 0\}\nonumber \end{align}\] Then since \(\eta_{v^{\mathsf{init}}, \phi}(x) > 0\) for all \(v^{\mathsf{init}},\phi, x\), it follows from 52 that \(\mathcal{E}= \mathcal{E}_\eta \cap \mathcal{E}_\chi\): for each \(j\) with \(\mu_j>0\) the equality \(\hat{\mu}(x_j)=\mu_j\) is equivalent to \(\eta_{v^{\mathsf{init}},\phi}(x_j)=\mu_j\) and \(\chi_\psi(x_j)=1\), while for each \(j\) with \(\mu_j=0\) it is equivalent to \(\chi_\psi(x_j)=0\). Moreover, note that the event \((v^{\mathsf{init}}, \phi, \psi) \in \mathcal{E}_\eta\) depends only on \((v^{\mathsf{init}}, \phi)\), while the event \((v^{\mathsf{init}}, \phi, \psi) \in \mathcal{E}_\chi\) depends only on \(\psi\). For any \((v', \phi')\) for which \(\mathbb{P}(\{ (v^{\mathsf{init}}, \phi) = (v', \phi') \} \cap \mathcal{E}) > 0\), we have \[\begin{align} \mathbb{P}(\psi = \psi' \mid \{(v^{\mathsf{init}}, \phi) = (v',\phi')\} \cap \mathcal{E}) &= \mathbb{P}(\psi = \psi' \mid \{(v^{\mathsf{init}}, \phi) = (v',\phi')\} \cap \mathcal{E}_\chi)\nonumber\\ &= \mathbb{P}(\psi = \psi' \mid \mathcal{E}_\chi) = \mathbb{P}(\psi = \psi' \mid \mathcal{E}_\chi \cap \mathcal{E}_\eta)\nonumber, \end{align}\] where the first equality uses that \((v^{\mathsf{init}}, \phi) = (v', \phi')\) implies that \(\mathcal{E}_\eta\) holds, while the second and third equalities use the independence of \((v^{\mathsf{init}}, \phi)\) and \(\psi\). Since \(\mathcal{E}=\mathcal{E}_\eta \cap \mathcal{E}_\chi\), this is the desired conditional independence statement. ◻

Proof. To simplify notation, we will typically write \(\hat{\mu} := \hat{\mu}_\tau, \hat{\omega}:= \hat{\omega}_\tau\). Further, we will make use of the sets \(A(x), B(x), C(x)\) indexed by \(x \in \{0,1\}^n\) (which are determined by the choice of \(\tau\)), defined in 34 35 36 , respectively. We consider the following two cases for \(X_j\):

4.3.0.3 Case 1 for \(X_j\).

Suppose \(X_j\) lies strictly inside a key block, so that \(|X_j| = 2ak + k + 1 + t\) for some \(0 \leq a < r\) and \(1 \leq t \leq k-1\). Since the sequence \(X_1, \ldots, X_j\) is ideal, there is some \(j' < j\) for which \(X_{j'} = (X_j)_{1:2ak+1}\). Note that \(\hat{\mu}(X_{j'}) = \mu_{j'}'\) under \(\mathcal{E}\), so that \[\begin{align} \hat{\mu}(X_j) = \frac{\mu_{j'}' \cdot \hat{Z}_{2ak+1}}{\hat{Z}_{|X_j|}} \cdot \mathbb{1}\left\{{\mathsf{key}_a(X_j) = \psi(\mathsf{base}_a(X_j); \mathsf{query}_a(X_j))_{1:t}}\right\},\nonumber \end{align}\] since every edge weight between depths \(2ak+2\) and \(2ak+k+1\) is equal to \(1\). In particular, \(\hat{\mu}(X_j)\) is \(\psi\)-measurable conditioned on \(\mathcal{E}\) (under both \(\mathbb{P}_0, \mathbb{P}_1\)). By 19, \(\psi\) and \((\phi, v^{\mathsf{init}})\) are conditionally independent conditioned on \(\mathcal{E}\) under both \(\mathbb{P}_0, \mathbb{P}_1\), so \[\begin{align} \mathbb{P}_0(\hat{\mu}(X_j) = \cdot \mid \mathcal{E}) = \mathbb{P}_1(\hat{\mu}(X_j) = \cdot \mid \mathcal{E}).\label{eq:case1-kl} \end{align}\tag{53}\]

4.3.0.4 Case 2 for \(X_j\).

Suppose \(|X_j| = 2(a+1)k+1\) for some \(0 \leq a < r\). Let \[\begin{align} I_j :=& \mathbb{1}\left\{{\mathsf{key}_a(X_j) = \psi(\mathsf{base}_a(X_j); \mathsf{query}_a(X_j))}\right\}\nonumber\\ R_j :=& \mathbb{1}\left\{{v^{\mathsf{init}}= (X_j)_1 \text{ or } \exists b<a:\;\phi(\mathsf{base}_b(X_j); \mathsf{query}_b(X_j)) \neq \tilde{\phi}(\mathsf{base}_b(X_j); \mathsf{query}_b(X_j))}\right\}\nonumber\\ S_j := & R_j \cdot \phi(\mathsf{base}_a(X_j); \mathsf{query}_a(X_j)) + (1-R_j) \cdot \tilde{\phi}(\mathsf{base}_a(X_j); \mathsf{query}_a(X_j)) \in \{0,1\}.\nonumber \end{align}\] Since the sequence \(X_1, \ldots, X_j\) is ideal, there is some \(j' < j\) so that \(X_{j'} = (X_j)_{1:2ak+1}\). We may then write \[\begin{align} \hat{\mu}(X_j) = \frac{\hat{\mu}(X_{j'}) \cdot \hat{Z}_{2ak+1}}{\hat{Z}_{|X_j|}} \cdot I_j \cdot \left(1 + \gamma \cdot S_j \right),\label{eq:hatmu-formula} \end{align}\tag{54}\] To characterize the distribution of \(\hat{\mu}(X_j)\) conditioned on \(\mathscr{F}_{j-1}\) under \(\mathbb{P}_0, \mathbb{P}_1\) we observe that \([j-1]\) may be partitioned into 3 subsets:

• \(\mathcal{J}_1\) consists of \(\ell \in [j-1]\) for which \(\mu_\ell' = 0\).

• \(\mathcal{J}_2\) consists of \(\ell \not \in \mathcal{J}_1\) for which \(\mathsf{base}_a(X_\ell) \neq \mathsf{base}_a(X_j)\).

• \(\mathcal{J}_3\) consists of \(\ell \not \in \mathcal{J}_1 \cup \mathcal{J}_2\). We claim that all \(\ell \in \mathcal{J}_3\) satisfy \(\mathsf{query}_a(X_\ell) \neq \mathsf{query}_a(X_j)\). This claim holds since, in order to have \(\hat{\mu}(X_\ell) > 0\) (which must have positive probability) and \(\mathsf{base}_a(X_\ell) = \mathsf{base}_a(X_j)\) and \(\mathsf{query}_a(X_\ell) = \mathsf{query}_a(X_j)\), we must have \(X_j \prec X_\ell\), which is impossible since the sequence \(X_1, \ldots, X_j\) (as \(|X_j| \pmod{2k} = 1\)) is ideal.

Since sequence \(X_1, \ldots, X_j\) is ideal, under \(\mathcal{E}\), the values of \(\hat{\omega}(X_\ell)\) for each \(\ell \in \mathcal{J}_2 \cup \mathcal{J}_3\) are uniquely determined (under the distributions \(\mathbb{P}_0, \mathbb{P}_1\)); indeed, for such \(\ell\) we have \(\hat{\mu}(X_\ell) = \frac{1}{\hat{Z}_{|X_\ell|}} \cdot \prod_{b=0}^{\lfloor (|X_\ell| - 2)/(2k) \rfloor} \hat{\omega}(\mathsf{base}_b(X_\ell))\), and the values of \(\hat{\omega}(\mathsf{base}_b(X_\ell))\) for all but (potentially) the largest value of \(b\) in this product are determined by \(\mu'_1, \ldots, \mu'_{\ell-1}\)on the event \(\{ \hat{\mu}(X_{\ell'}) = \mu_{\ell'}' \;\forall \ell' < \ell \}\). Thus, we may make the following definitions:

• Let \(\tilde{A}\) denote the set of values of \(\mathsf{query}_a(X_\ell)\), for \(\ell \in \mathcal{J}_3\), for which \(\hat{\omega}(X_\ell) = 1 + \gamma\).

• Let \(\tilde{C}\) denote the set of values of \(\mathsf{query}_a(X_\ell)\), for \(\ell \in \mathcal{J}_3\), for which \(\hat{\omega}(X_\ell) = 1\).

All \(\ell \in \mathcal{J}_3\) satisfy \(\mathsf{query}_a(X_\ell) \in \tilde{A} \cup \tilde{C}\) since \(\hat{\omega}(\mathsf{base}_a(X_\ell)) \neq 0\) for \(\ell \in \mathcal{J}_3\). Let \(\mathcal{E}^{\mathsf{query}}\) denote the event that \(\hat{\omega}(x) = 1+\gamma\) for all \(x \in \tilde{A}\) and that \(\hat{\omega}(x) = 1\) for all \(x \in \tilde{C}\).

Finally, let \(\mathcal{D}\) denote the set of all values of \(\mathsf{base}_b(X_\ell)\) not equal to \(\mathsf{base}_a(X_j)\) for any \(0 \leq b< r\) and \(\ell \in \mathcal{J}_2 \cup \mathcal{J}_3\) with \(2bk+1 \leq |X_\ell|\). Since the sequence \(X_1, \ldots, X_j\) is ideal, each \(X_\ell\) can only contribute at most one new value to \(\mathcal{D}\), meaning that \(|\mathcal{D}| \leq q-1\). For each \(d \in \mathcal{D}\), let \((v^{(d)}, \tilde{v}^{(d)}) \in \mathcal{V}^{\mathsf{valid}}_{k,\epsilon}\) be an arbitrary \(\epsilon\)-valid tuple; via slight abuse of notation, we let \((v,\tilde{v})\) denote the collection of \((v^{(d)}, \tilde{v}^{(d)})\) for \(d \in \mathcal{D}\). Let \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\) denote the event that \(\phi(d) = (v^{(d)}, \tilde{v}^{(d)})\) for each \(d \in \mathcal{D}\).

We proceed to analyze the distribution \(\mathbb{P}_{(X_j)_1}(\hat{\mu}(X_j) = \cdot \mid \mathcal{E})\). For any values of \(\psi' \in \Psi_{n,k,q}\) and \((v,\tilde{v}) \in (\mathcal{V}^{\mathsf{valid}}_{k,\epsilon})^{\mathcal{D}}\) as above which are consistent with \(\mathcal{E}\) in the sense that \(\mathbb{P}_{(X_j)_1}(\mathcal{E}\mid \{ \psi = \psi' \} \cap \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}) > 0\), we have \[\begin{align} & \mathbb{P}_{(X_j)_1} \left(S_j = 1 \mid \mathcal{E}\cap \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\cap \{\psi = \psi'\} \right) \nonumber\\ =& \mathbb{P}_{(X_j)_1} \left(S_j = 1 \mid \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\cap \{\psi = \psi'\} \right) \nonumber\\ =& \mathbb{P}_{(X_j)_1} \left(S_j = 1 \mid \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\right) \nonumber\\ =& \mathbb{P}_{(X_j)_1} \left( \mathsf{query}_a(X_j) \in A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j))\mid \mathcal{E}^{\mathsf{query}}\right) \nonumber\\ =& \mathbb{P}_{(X_j)_1} \left( \mathsf{query}_a(X_j) \in A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)) \mid \tilde{A} \subset A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)),\;\tilde{C} \subset C(\mathsf{base}_a(X_j)) \right)\nonumber\\ =& \frac{2^{k-1} - |\tilde{A}|}{2^k - |\tilde{A}| - |\tilde{C}|}\label{eq:xj-same}, \end{align}\tag{55}\] where the first equality uses that, for \(\psi', (v,\tilde{v})\) which are consistent with \(\mathcal{E}\), we have \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\cap \{\psi = \psi'\} \subseteq \mathcal{E}\); the second equality uses that \(S_j\) and \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\) depend only on \(\phi\), together with the fact that \(\phi, \psi\) are independent; and the third equality uses the fact that \(\phi\) is \(q\)-wise independent: \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\) conditions on the values of \(\phi(d)\) for at most \(q-1\) values of \(d\), and \(S_j = 1\) if and only if \(\phi(\mathsf{base}_a(X_j); \mathsf{query}_a(X_j)) = 1\), i.e., if \(\mathsf{query}_a(X_j) \in A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j))\). The fourth equality simply rewrites the definition of \(\mathcal{E}^{\mathsf{query}}\), and the final equality follows from the following reasoning: on the event \(\tilde{A} \subset A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)),\;\tilde{C} \subset C(\mathsf{base}_a(X_j))\), the set \(A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)) \backslash \tilde{A}\) is a uniformly random set of size \(2^{k-1} - |\tilde{A}|\) in \(\{0,1\}^k \backslash (\tilde{A} \cup \tilde{C})\), which has size \(2^k - |\tilde{A}| - |\tilde{C}|\).

We next perform a similar computation for \(\mathbb{P}_{1-(X_j)_1}\). To do so, first note that, under \(\mathbb{P}_{1-(X_j)_1}\), conditioned on \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\), the values of \(v,\tilde{v}\) uniquely determine the value of \(R_j\): indeed, conditioned on \(\mathcal{E}^{\mathsf{base}}_{b,\tilde{v}}\), \(R_j = 1\) if and only if some \(b < a\) satisfies \(v^{(\mathsf{base}_b(X_j))}_{\mathsf{query}_b(X_j)} \neq \tilde{v}^{(\mathsf{base}_b(X_j))}_{\mathsf{query}_b(X_j)}\). For any \((v,\tilde{v}) \in (\mathcal{V}^{\mathsf{valid}}_{k,\epsilon})^{\mathcal{D}}\) and \(\psi' \in \Psi_{n,k,q}\) which are consistent with \(\mathcal{E}\) under \(\mathbb{P}_{1-(X_j)_1}(\cdot)\), which further satisfy that \(R_j = 1\) under \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\), we have \[\begin{align} & \mathbb{P}_{1-(X_j)_1} \left(S_j = 1 \mid\mathcal{E}\cap \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\cap \{\psi = \psi'\} \right)\nonumber\\ =& \mathbb{P}_{1-(X_j)_1} \left( \mathsf{query}_a(X_j) \in A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)) \mid \tilde{A} \subset A(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j)),\;\tilde{C} \subset C(\mathsf{base}_a(X_j)) \right)\nonumber\\ =& \mathbb{P}_{(X_j)_1} \left( S_j = 1\mid \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}\right)\label{eq:xj-diff1}, \end{align}\tag{56}\] using the same reasoning as in 55 . In instead \((v,\tilde{v})\) is so that \(R_j = 0\) under \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\), we have \[\begin{align} & \mathbb{P}_{1-(X_j)_1} \left(S_j = 1 \mid\mathcal{E}\cap \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\cap \{\psi = \psi'\} \right)\nonumber\\ =& \mathbb{P}_{1-(X_j)_1} \left( S_j = 1 \mid \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \mathcal{E}^{\mathsf{query}}\right)\nonumber\\ =& \mathbb{P}_{1-(X_j)_1} \left( S_j = 1 \mid \mathcal{E}^{\mathsf{base}}_{v,\tilde{v}} \cap \{\tilde{A} \subset A(\mathsf{base}_a(X_j))\} \cap \{\tilde{C} \subset C(\mathsf{base}_a(X_j))\cup B(\mathsf{base}_a(X_j))\} \right)\nonumber\\ =& \mathbb{P}_{1-(X_j)_1} \left( \mathsf{query}_a(X_j) \in A(\mathsf{base}_a(X_j)) \mid \tilde{A} \subset A(\mathsf{base}_a(X_j)) ,\;\tilde{C} \subset C(\mathsf{base}_a(X_j))\cup B(\mathsf{base}_a(X_j)) \right)\nonumber\\ =& \frac{2^{k-1} - \epsilon 2^k - |\tilde{A}|}{2^k - |\tilde{A}| - |\tilde{C}|}\label{eq:xj-diff2}, \end{align}\tag{57}\] where the first equality follows the steps as in 55 ; the second equality uses that under \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\)) (so that \(R_j = 0\)), the event \(\mathcal{E}^{\mathsf{query}}\) is equivalent to the event that \(\tilde{A} \subset A(\mathsf{base}_a(X_j))\) and \(\tilde{C} \subset C(\mathsf{base}_a(X_j))\cup B(\mathsf{base}_a(X_j))\); and the third equality uses the \(q\)-independence of \(\phi\), together with the fact that \(\mathcal{E}^{\mathsf{base}}_{v,\tilde{v}}\) depends on the values of \(\phi(d)\) for at most \(q-1\) values of \(d\), all not equal to \(\mathsf{base}_a(X_j)\). The final equality uses the following reasoning: on the event \(\tilde{A} \subset A(\mathsf{base}_a(X_j))\), \(\tilde{C} \subset C(\mathsf{base}_a(X_j)) \cup B(\mathsf{base}_a(X_j))\), the set \(A(\mathsf{base}_a(X_j)) \backslash \tilde{A}\) is a uniformly random set of size \(2^{k-1} - \epsilon 2^k - |\tilde{A}|\) in \(\{0,1\}^k \backslash (\tilde{A} \cup \tilde{C})\), which has size \(2^k - |\tilde{A}| - |\tilde{C}|\).

Note that \(|\tilde{A}| \cup |\tilde{C}| \leq |\mathcal{J}_3| \leq j-1 \leq q-1\). Since we have assumed that \(q \leq 2^k/100\), the right-hand sides of 55 56 57 all lie in \([1/3, 2/3]\) and differ by at most \(10\epsilon\). Since 55 56 57 hold for every \(v,\tilde{v}\), it follows that \[\begin{align} \mathbb{P}_0(S_j = 1 \mid \mathcal{E}), \mathbb{P}_1(S_j = 1 \mid \mathcal{E}) \in [1/3,2/3], \qquad \left| \mathbb{P}_0(S_j = 1 \mid \mathcal{E}) - \mathbb{P}_1(S_j = 1 \mid \mathcal{E}) \right| \leq 10\epsilon\nonumber, \end{align}\] and so \[\begin{align} D_{\mathsf{KL}}({\mathbb{P}_0(S_j = \cdot \mid \mathcal{E})}||{\mathbb{P}_1(S_j = \cdot \mid \mathcal{E})}) \leq O(\epsilon^2).\nonumber \end{align}\] Next, 19 gives that, conditioned on \(\mathcal{E}\), \(I_j\) is independent of \(S_j\) under the measures \(\mathbb{P}_0, \mathbb{P}_1\); and further, the distribution of \(I_j\) conditioned on \(\mathcal{E}\) is identical under \(\mathbb{P}_0, \mathbb{P}_1\). Thus, combining the above display with 54 gives that \[\begin{align} D_{\mathsf{KL}}({\mathbb{P}_0(\hat{\mu}(X_j) = \cdot \mid \mathcal{E})}||{\mathbb{P}_1(\hat{\mu}(X_j) = \cdot \mid \mathcal{E})}) \leq O(\epsilon^2),\nonumber \end{align}\] as desired. ◻

Proof. Fix an algorithm \(\mathsf{Alg}\), and denote the (adaptive) queries the algorithm makes by \(X_1, \ldots, X_q \in \{0,1\}^{\leq n}\). We begin by setting up some notation.

4.3.0.5 Setup.

For any \(x \in \{0,1\}^{2ak + i}\) for some \(0 \leq a < r\) and \(1 \leq i \leq 2k\), if \(i \in \{2,3,\ldots,k+1\}\), then every edge weight on the path from \(x_{1:2ak+1}\) to \(x\) is equal to \(1\), so \(\hat{\mu}(x)\) is determined by \(\hat{\mu}(x_{1:2ak+1})\) together with the deterministic normalizing constant \(\hat{Z}_{2ak+i}\) from 42 18. Hence, it is without loss of generality to assume that for each query \(j \in [q]\), \(|X_j| \pmod{2k} \in \{1, k+2, k+3, \ldots, 2k\}\).

For each \(j \in [q]\), write \(\mathscr{F}_{j}\) for the sigma-algebra generated by the first \(j\) query-answer pairs \((X_1, \hat{\mu}(X_1)), \ldots, (X_{j}, \hat{\mu}(X_{j}))\), as well as the internal randomness of \(\mathsf{Alg}\); then for each \(j \in [q]\), \(X_j\) is \(\mathscr{F}_{j-1}\)-measurable. Moreover, at a cost of a factor of at most \(2\) in \(q\), we may assume the following: for each query \(X_j\) lying strictly inside a “key block”, i.e., with \(|X_j| = 2ak + k + 1 + t\) for some \(0 \leq a < r\) and \(1 \leq t \leq k-1\), there is some \(j' < j\) for which \(X_{j'} = (X_j)_{1:2ak+1}\). In words, prior to making such a query, the algorithm has already queried the most recent ancestor of \(X_j\) whose length is \(1 \pmod{2k}\).

Recall that \(\mathbb{P}\) denotes the joint distribution over the random draw of \((v^{\mathsf{init}},\phi,\psi) \sim \mathcal{H}_{n,k,q,\epsilon}\) and the internal randomness of \(\mathsf{Alg}\), and \(\mathbb{E}\) denotes the corresponding expectation. For each \(b \in \{0,1\}\), recall that \(\mathbb{P}_b(\cdot) := \mathbb{P}(\cdot \mid v^{\mathsf{init}}= b)\). We will show that the probability laws of \(\mathbb{P}_0(X_1, \ldots, X_q, \hat{\mu}(X_1), \ldots, \hat{\mu}(X_q) = \cdot)\) and \(\mathbb{P}_1(X_1, \ldots, X_q, \hat{\mu}(X_1), \ldots, \hat{\mu}(X_q) = \cdot)\) are close, from which the desired result will follow using Bayes rule.

4.3.0.6 Alternative algorithm: \(\widetilde{\mathsf{Alg}}\).

First, we consider the following further modification of \(\mathsf{Alg}\), which we denote by \(\widetilde{\mathsf{Alg}}\). \(\widetilde{\mathsf{Alg}}\) internally simulates \(\mathsf{Alg}\), in the following manner: it maintains a sequence \(Y_1, Y_2, \ldots, Y_t\) (intialized to be the empty sequence, so that \(t = 0\)), as follows. For each \(j \in [q]\), when \(\mathsf{Alg}\) is about to query \(\hat{\mu}(X_j)\), \(\widetilde{\mathsf{Alg}}\) checks if the sequence \(Y_1, \ldots, Y_t, X_j\) is ideal (in the sense of 8); we let this event be denoted by \(\mathcal{E}_j\). If \(\mathcal{E}_j\) holds, then \(\widetilde{\mathsf{Alg}}\) sets \(Y_{t+1} = X_j\), increments \(t\) by \(1\), and continues to execute \(\mathsf{Alg}\). Otherwise, \(\widetilde{\mathsf{Alg}}\) does not query \(\hat{\mu}(X_j)\) and simply proceeds as if the result of the query had returned \(\hat{\mu}(X_j) = 0\). We let \(\tilde{B}\) denote the output bit returned by \(\widetilde{\mathsf{Alg}}\). Moreover, for each \(j \in [q]\), we let \(\tilde{\mu}_j\) denote the value which \(\widetilde{\mathsf{Alg}}\) uses for \(\hat{\mu}(X_j)\) (i.e., \(\tilde{\mu}_j = \hat{\mu}(X_j)\) if \(Y_1, \ldots, Y_t, X_j\) is ideal, and otherwise \(\tilde{\mu}_j = 0\)). We may consider \(\mathsf{Alg},\widetilde{\mathsf{Alg}}\) as being defined on the same probability space, using the same internal randomness and the same sampled tuple \((v^{\mathsf{init}},\phi,\psi) \sim \mathcal{H}_{n,k,q,\epsilon}\). We denote the corresponding probability measure by \(\mathbb{P}\) (and use \(\mathbb{P}_0, \mathbb{P}_1\) to denote conditioning on \(v^{\mathsf{init}}= 0,1\), respectively).

The proof of 6 is deferred to below. Given 6, it suffices to upper bound \(\mathbb{P}(\tilde{B} = v^{\mathsf{init}})\).

4.3.0.7 Analyzing \(\widetilde{\mathsf{Alg}}\).

Let \(t_j\) be the value of \(t\) maintained by \(\widetilde{\mathsf{Alg}}\) at the beginning of step \(j\), so that prior to step \(j\), \(\widetilde{\mathsf{Alg}}\) has queried \(\hat{\mu}(\cdot)\) only at \(Y_1, \ldots, Y_{t_j}\). We denote the “simulated queries” of \(\mathsf{Alg}\) made by \(\widetilde{\mathsf{Alg}}\) by \(\tilde{X}_1, \ldots, \tilde{X}_q\). Further, we let \(\tilde{\mathscr{F}}_j\) denote the sigma-algebra generated by the internal randomness of \(\widetilde{\mathsf{Alg}}\) together with \((\tilde{X}_\ell, \tilde{\mu}_\ell)_{\ell \in [j]}\). If \(\mathcal{E}_j\) holds, then the sequence \(Y_1, \ldots, Y_{t_j}, Y_{t_j+1} = \tilde{X}_j\) is ideal, so we may apply 20 to this sequence to obtain that there is an absolute constant \(C\) such that \[\begin{align} D_{\mathrm{KL}}\!\left( \mathcal{\mathbb{P}}_1\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right)\, \middle\|\, \mathcal{\mathbb{P}}_0\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right) \right) \leq C\epsilon^2.\label{eq:case2-kl} \end{align}\tag{58}\] If \(\mathcal{E}_j\) does not hold, then \(\tilde{\mu}_j = 0\) and so \[\begin{align} D_{\mathrm{KL}}\!\left( \mathcal{\mathbb{P}}_1\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right)\, \middle\|\, \mathcal{\mathbb{P}}_0\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right) \right) = 0.\label{eq:case2b-kl} \end{align}\tag{59}\]

The chain rule for KL divergence yields \[\begin{align} & D_{\mathsf{KL}}({\mathbb{P}_1(\tilde{X}_{1:q},\tilde{\mu}_{1:q} = \cdot)}||{\mathbb{P}_0(\tilde{X}_{1:q}, \tilde{\mu}_{1:q} = \cdot)})\nonumber\\ =& \sum_{j=1}^q D_{\mathrm{KL}}\!\left( \mathcal{\mathbb{P}}_1\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right)\, \middle\|\, \mathcal{\mathbb{P}}_0\left(\tilde{\mu}_j = \cdot \mid \tilde{\mathscr{F}}_{j-1}\right) \right) \leq C q \epsilon^2\nonumber, \end{align}\] where the final inequality uses 58 59 .

Pinsker’s inequality yields \[\begin{align} D_{\mathsf{TV}}({\mathbb{P}_1(\tilde{X}_{1:q},\tilde{\mu}_{1:q} = \cdot)}, {\mathbb{P}_0(\tilde{X}_{1:q}, \tilde{\mu}_{1:q} = \cdot)})\leq O(\epsilon\sqrt q).\nonumber \end{align}\] Consequently, we have \[\begin{align} & \mathbb{E}\left[ \left|\mathbb{P}(v^{\mathsf{init}}= 1 \mid \tilde{X}_{1:q}, \tilde{\mu}_{1:q})- \mathbb{P}(v^{\mathsf{init}}= 0 \mid \tilde{X}_{1:q}, \tilde{\mu}_{1:q})\right| \right]\nonumber\\ =& D_{\mathsf{TV}}({\mathbb{P}_1(\tilde{X}_{1:q},\tilde{\mu}_{1:q} = \cdot)}, {\mathbb{P}_0(\tilde{X}_{1:q}, \tilde{\mu}_{1:q} = \cdot)})\leq O(\epsilon\sqrt q)\nonumber, \end{align}\] and since \(v^{\mathsf{init}}\in \{0,1\}\), it follows that \[\begin{align} \mathbb{E}\left[ \left|\mathbb{P}(v^{\mathsf{init}}= 1 \mid \tilde{X}_{1:q}, \tilde{\mu}_{1:q}) - \frac{1}{2}\right| \right] \leq O(\epsilon\sqrt q),\nonumber \end{align}\] and thus, since \(\tilde{B}\) is a function of \(\tilde{X}_{1:q}, \tilde{\mu}_{1:q}\), and the internal randomness of \(\mathsf{Alg}\), \[\begin{align} \left|\mathbb{P}(v^{\mathsf{init}}= \tilde{B}) - \frac{1}{2} \right| \leq \mathbb{E}\left[ \left|\mathbb{P}(v^{\mathsf{init}}= \tilde{B} \mid \tilde{X}_{1:q}, \tilde{\mu}_{1:q}) - \frac{1}{2}\right| \right] \leq O(\epsilon\sqrt q).\nonumber \end{align}\] Combining the above with 6 yields the desired result. ◻

Proof of 6. Recall that we couple \(\mathsf{Alg}\) and \(\widetilde{\mathsf{Alg}}\) using the same internal randomness and the same realization of \((v^{\mathsf{init}},\phi, \psi)\). The two algorithms can differ only if, at some query step \(j\), the event \(\mathcal{E}_j^c\) holds and yet the true oracle value satisfies \(\hat{\mu}(X_j)\neq 0\); indeed, in all other cases \(\widetilde{\mathsf{Alg}}\) feeds the same answer to the algorithm as \(\mathsf{Alg}\) does.

For each \(j \in [q]\), let \(a_j \geq 0\) be chosen as small as possible so that \(2k \cdot a_j +1 < |X_j|\) and \(\mathsf{base}_{a_j}(X_j)\) has not been previously queried. (If no such \(a_j\) exists, then we set \(a_j = \perp\).) Let \(J \in [q] \cup \{ \infty\}\) be a random variable denoting the first iteration for which \(a_J \neq \perp\) and \(\hat{\mu}(X_J) \neq 0\).

Fix \(j \in [q]\); in order for \(J = j\) to hold, it is necessary that (a) \(a_j \neq \perp\) and (b) \(\mathsf{key}_{a_j}(X_j) = \psi(\mathsf{base}_{a_j}(X_j); \mathsf{query}_{a_j}(X_j))\). Note that \(a_j\) is \(\mathscr{F}_{j-1}\)-measurable. We now make the following claim:

If \(a_j \neq \perp\) (so that \(\mathsf{base}_{a_j}(X_j)\) has not been previously queried), then we must in fact that \(|X_j| = 2(a_j+1)k + 1\) (by our assumption on \(\mathsf{Alg}\)). Hence, for any realization of the history for which \(a_j \neq \perp\), we have \[\begin{align} \mathbb{P}(J = j \mid \mathscr{F}_{j-1}) = \mathbb{P}(\mathsf{key}_{a_j}(X_j) = \psi(\mathsf{base}_{a_j}(X_j); \mathsf{query}_{a_j}(X_j)) \mid \mathscr{F}_{j-1}) = 2^{-k}\nonumber, \end{align}\] where the final equality uses the fact that \(\mathsf{key}_{a_j}(X_j)\), \(\mathsf{base}_{a_j}(X_j)\), and \(\mathsf{query}_{a_j}(X_j)\) are all \(\mathscr{F}_{j-1}\)-measurable, and \(\psi(\mathsf{base}_{a_j}(X_j); \mathsf{query}_{a_j}(X_j))\) is uniform on \(\{0,1\}^k\), conditioned on \(\mathscr{F}_{j-1}\), by 7. A union bound then yields \(\mathbb{P}\left( J \leq q \right) \leq q/2^k\); in other words, with probability at least \(1-q/2^k\), the execution traces of \(\mathsf{Alg}, \widetilde{\mathsf{Alg}}\) are identical, and thus the algorithms return the same bit as output. ◻

Proof of 4. Set \(q = \frac{c \gamma^2 n^2}{ \log^2 (n) \cdot \log^2(2/\gamma)}\), for a sufficiently small constant \(c > 0\) to be chosen later. Take \[\begin{align} k = \lceil 2 \log_2(n)\rceil, \qquad r =\left\lfloor \frac{n-1}{2k}\right\rfloor, \qquad \epsilon:= \frac{4 \log(48/\gamma) \cdot k}{n}, \qquad n' = 2rk+1.\label{eq:weak-params} \end{align}\tag{60}\]

Suppose to the contrary that such \(\mathsf{Alg}\) exists, and consider the execution of \(\mathsf{Alg}\) with respect to the distribution \(\mu^\star = \mu_{\tau}\) and mapping \(\hat{\mu}_{\tau}\), where \(\tau = (v^{\mathsf{init}}, \phi, \psi) \sim \mathcal{H}_{n',k,q}\) is drawn uniformly at random. First, 17 ensures that we indeed have that \(\frac{1}{(1+\gamma)^2} \leq \frac{\mu_{\tau}(x)}{\hat{\mu}_{\tau}(x)} \leq (1+\gamma)^2\) with probability \(1\) for all \(x \in \{0,1\}^{\leq n}\); further, by definition we have \(\mu_\tau(x) = \hat{\mu}(x)\) for \(x \in \{0,1\}^n\). Thus 1 is satisfied. For any instantiation of \(\tau\), let the distribution of the output \(X\) of \(\mathsf{Alg}\) be denoted \(\hat{\nu}_{\tau}\). The assumption that \(D_{\mathsf{TV}}({\mu_\tau}, {\hat{\nu}_\tau}) \leq \frac{\gamma}{8}\) and \(\gamma < 1\), as well as the fact that \(e^{-\epsilon r} \leq \gamma/48\) (from 60 ) yields \[\begin{align} & \mathbb{P}_{X \sim \hat{\nu}_\tau}(X_1 = v^{\mathsf{init}}_1) \geq \mathbb{P}_{X \sim \mu_\tau}(X_1 = v^{\mathsf{init}}_1) - \frac{\gamma}{8} \geq \mathbb{P}_{X \sim \mu_{\mathsf{ideal}}}(X_1 = v^{\mathsf{init}}_1) - \frac{\gamma}{8} - e^{-\epsilon r} \nonumber\\ & \geq \frac{1+\gamma}{2+\gamma} - \frac{\gamma}{8} - e^{-\epsilon r} \geq \frac{1}{2} + \frac{\gamma}{24} - e^{-\epsilon r} \geq \frac{1}{2} + \frac{\gamma}{48}\nonumber. \end{align}\] Above the second inequality uses 16, and the third inequality uses the definition of \(\mu_{\mathsf{ideal}}\). This contradicts 21 as long as \(q \leq \frac{c \gamma^2}{\epsilon^2}\) (which also yields \(q \cdot 2^{-k} < \gamma/100\)), for a sufficiently small constant \(c\).

Note that we have shown a lower bound for an instance \(\tau \in \mathcal{H}_{n',k,q}\), for which the corresponding measures are defined on \(\{0,1\}^{n'}\); but we can extend this to \(\{0,1\}^n\) by simply padding the last \(n-n'\) bits deterministically.

Finally, we remark that we can take the class \(\mathcal{F}\) to be equal to \(\mathcal{H}_{n',k,q}\). By 7 (which relies on 15), its cardinality satisfies \[\begin{align} \log |\mathcal{F}| = 2 + \log |\Phi_{n',k,q}| + \log |\Psi_{n',k,q}| \leq O(q k2^k) \leq O(n^4)\nonumber. \end{align}\] ◻

Proof. It is without loss of generality to assume that \(S \leq \exp(n^4)\) (as the function \(f(n,S)\) is constant as a function of \(S\) for \(S > \exp(n^4)\)).

4.4.0.1 Case 1: large \(S\).

We first show a lower bound of \(\Omega\left(\min \left\{\frac{\sqrt{\log S}}{\log^2(2 + \log S)}, \frac{n^2}{\log^2 n} \right\} \right)\) on the query complexity. Write \(n' = c'\log(S)^{1/4}\), for a sufficiently small constant \(c' > 0\) to be specified below. Then 4 with \(\gamma = 1/2\) gives that there is a class of distributions \(\mathcal{F}' \subset \Delta(\{0,1\}^{n'})\) of size at most \(\exp(O((n')^4))\) so that no randomized algorithm \(\mathsf{Alg}\) enjoys the following guarantee: for any \(\mu^\star \in \mathcal{F}'\) and \(\hat{\mu} : \{0,1\}^{\leq n'} \to \mathbb{R}_{\geq 0}\) satisfying 1 with \(R = 9/4\), \(\mathsf{Alg}\) makes \(\frac{c \cdot (n')^2}{\log^2(n')}\) queries to \(\hat{\mu}\) and outputs a random string \(X' \in \{0,1\}^{n'}\) according to some distribution \(\hat{\nu}\) which satisfies \(D_{\mathsf{TV}}({\mu^\star}, {\hat{\nu}}) \leq 1/16\), for some constant \(c > 0\). Note that we can view \(\mathcal{F}'\) as a subset of \(\Delta(\{0,1\}^n)\) by padding the last \(n-n'\) coordinates to be \(0\) with probability 1 (for all \(\mu \in \mathcal{F}'\)). Thus, noting that \((n')^2 = \Theta(\sqrt{\log S})\) and \(\log^2(n') \leq \log^2(2 + \log S)\), as well as \(|\mathcal{F}'| \leq S\) as long as the constant \(c'\) is sufficiently small, we obtain that any randomized algorithm satisfying the requirement of 8 must make \(\Omega\left(\min \left\{\frac{\sqrt{\log S}}{\log^2(2 + \log S)}, \frac{n^2}{\log^2 n} \right\} \right)\) queries to \(\hat{\mu}\).

4.4.0.2 Case 2: Small \(S\).

We next show a lower bound of \(\Omega (\min\{S, n\})\) on the query complexity. It suffices to assume \(S \leq n\). For \(1 \leq i \leq S\), let \(v_i \in \{0,1\}^S\) be defined by \(v_{i,j} = \mathbb{1}\left\{{j \leq i}\right\}\). We define a class \(\mathcal{F}_S \subset \Delta(\{0,1\}^S)\) consisting of the \(S-1\) measures \(\mu_1, \ldots, \mu_{S-1}\), where for each \(i \in [S-1]\), \[\begin{align} \mu_i := \frac{1}{2} \cdot \delta_{v_i} + \frac{1}{2} \cdot \delta_{v_S}.\nonumber \end{align}\] Next, for each \(i \in [S-1]\), define \(\hat{\mu}_i : \{0,1\}^{\leq S} \to \mathbb{R}_{\geq 0}\) by \[\begin{align} \hat{\mu}_i(x) = \begin{cases} \frac{1}{2} &: x \preceq v_iorx \preceq v_S \\ 0 &: otherwise. \end{cases}\nonumber \end{align}\] We claim that \(\hat{\mu}_i\) satisfies 1 with respect to \(\mu_i\), with \(R = 2 \leq 9/4\). Indeed, fix any \(x \in \{0,1\}^{\leq S}\). If \(x \npreceq v_i\) and \(x \npreceq v_S\), then \(\mu_i(x) = \hat{\mu}_i(x) = 0\). If \(x\) is a prefix of exactly one of \(v_i, v_S\), then \(\mu_i(x) = \hat{\mu}_i(x) = 1/2\). Finally, if \(x\) is a prefix of both \(v_i\) and \(v_S\), then necessarily \(x = 1^t\) for some \(t \leq i\), and thus \(\mu_i(x) = 1\) while \(\hat{\mu}_i(x) = 1/2\). Therefore, whenever \(\hat{\mu}_i(x) > 0\), we have \[\begin{align} 1 \leq \frac{\mu_i(x)}{\hat{\mu}_i(x)} \leq 2 \leq 9/4.\nonumber \end{align}\] Moreover, for every leaf \(x \in \{0,1\}^S\), the definition gives \(\hat{\mu}_i(x) = \mu_i(x)\), as required.

It remains to show that any randomized algorithm requires \(\Omega(S)\) queries. Fix any randomized algorithm making at most \(q\) queries, and draw \(I \sim \mathrm{Unif}([S-1])\). We will show that if \(q \leq cS\) for a sufficiently small constant \(c > 0\), then the algorithm cannot output a distribution within total variation distance \(1/16\) of \(\mu_I\).

Fix a realization \(\rho\) of the algorithm’s internal randomness, and consider the resulting deterministic algorithm. Let \(\hat{\mu}_\circ\) denote the reference oracle defined by \[\begin{align} \hat{\mu}_\circ(x) := \frac{1}{2} \cdot \mathbb{1}\left\{{x \preceq v_S}\right\}.\nonumber \end{align}\] Run the deterministic algorithm against \(\hat{\mu}_\circ\), and let \(x_1^{\rho}, \ldots, x_q^{\rho}\) denote the resulting query sequence, with output \(Y_{\rho} \in \{0,1\}^S\). Define \[\begin{align} T_{\rho} := \{ i \in [S-1] \mid \exists j \in [q]such thatx_j^{\rho} \preceq v_iandx_j^{\rho} \npreceq v_S\}.\nonumber \end{align}\] For any fixed query \(x\), there is at most one index \(i \in [S-1]\) such that \(x \preceq v_i\) and \(x \npreceq v_S\): indeed, once a prefix leaves the all-ones path leading to \(v_S\), it can lie on at most one of the paths to \(v_1, \ldots, v_{S-1}\). Consequently, \(|T_{\rho}| \leq q\).

Now fix any \(i \in [S-1] \setminus T_{\rho}\). By definition of \(T_{\rho}\), every query \(x_j^{\rho}\) receives the same answer from \(\hat{\mu}_i\) as from \(\hat{\mu}_\circ\): if \(x_j^{\rho} \preceq v_S\), then both oracles return \(1/2\), and otherwise \(x_j^{\rho} \npreceq v_i\), so both return \(0\). Thus, when run against \(\hat{\mu}_i\), the deterministic algorithm follows the exact same execution trace as it does against \(\hat{\mu}_\circ\), and hence outputs the same string \(Y_{\rho}\). Therefore, \[\begin{align} \mathbb{P}_{I \sim \mathrm{Unif}([S-1])}(Y_{\rho} = v_I) \leq \mathbb{P}(I \in T_{\rho}) + \mathbb{P}(Y_{\rho} = v_I,\;I \notin T_{\rho}) \leq \frac{|T_{\rho}|}{S-1} + \frac{1}{S-1} \leq \frac{q+1}{S-1}.\nonumber \end{align}\] Since this bound holds for every realization \(\rho\) of the algorithm’s internal randomness, averaging over \(\rho\) yields \[\begin{align} \mathbb{P}(X = v_I) \leq \frac{q+1}{S-1},\label{eq:small-s-success-bound} \end{align}\tag{61}\] where \(X\) denotes the output of the original randomized algorithm.

On the other hand, if the algorithm were to satisfy the guarantee of 8, then for every \(i \in [S-1]\) its output distribution \(\hat{\nu}_i\) under oracle \(\hat{\mu}_i\) would satisfy \(D_{\mathsf{TV}}({\hat{\nu}_i}, {\mu_i}) \leq 1/16\). Since \(\mu_i(v_i) = 1/2\), this implies \[\begin{align} \mathbb{P}(X = v_i \mid I = i) = \hat{\nu}_i(v_i) \geq \mu_i(v_i) - D_{\mathsf{TV}}({\hat{\nu}_i}, {\mu_i}) \geq \frac{1}{2} - \frac{1}{16} = \frac{7}{16}.\nonumber \end{align}\] Averaging over \(I \sim \mathrm{Unif}([S-1])\), we obtain \(\mathbb{P}(X = v_I) \geq 7/16\), which contradicts 61 as long as \(q \leq cS\) for a sufficiently small universal constant \(c > 0\).

Finally, we may view \(\mathcal{F}_S\) as a subset of \(\Delta(\{0,1\}^n)\) by padding the last \(n-S\) coordinates with zeros deterministically. Since \(|\mathcal{F}_S| = S-1 \leq S\), this establishes the desired \(\Omega(S) = \Omega(\min\{S,n\})\) lower bound in the small-\(S\) regime, and completes the proof. ◻

Proof. Let us write \(x = (x^{(1)}, \ldots, x^{(a)}) \in \{0,1\}^{\leq \bar{n}}\) with \(x^{(1)}, \ldots, x^{(a-1)} \in \{0,1\}^n\) and \(x^{(a)} \in \{0,1\}^{\leq n}\). By definition of \(\mu_{\tau^{(i)}}, \hat{\mu}_{\tau^{(i)}}\), for \(i < a\), since we have \(x^{(i)} \in \{0,1\}^n\), it holds that \(\mu_{\tau^{(i)}}(x^{(i)}) = \hat{\mu}_{\tau^{(i)}}(x^{(i)})\). Thus \[\begin{align} \frac{\mu_{\tau^{(1:s)}}(x)}{\hat{\mu}_{\tau^{(1:s)}}(x)} = \frac{\prod_{i=1}^a \mu_{\tau^{(i)}}(x^{(i)})}{\prod_{i=1}^a \hat{\mu}_{\tau^{(i)}}(x^{(i)})} = \frac{\mu_{\tau^{(a)}}(x^{(a)})}{\hat{\mu}_{\tau^{(a)}}(x^{(a)})} \in [(1+\gamma)^{-2}, (1+\gamma)^2],\nonumber \end{align}\] where the final inclusion uses 17. (Above, we interpret \(0/0 = 1\).) ◻

Proof. If \(\frac{800 \mathsf{K}}{\gamma^2} > \frac{\bar{n}}{ 100 \log \bar{n}}\), then the claimed query bound \(c' \bar{n}^2\gamma^6 / (\mathsf{K}^2 \log^2 \bar{n} \cdot \log^2(2/\gamma))\) is \(O(1)\), so the result is trivial. Thus we may assume \(\frac{800 \mathsf{K}}{\gamma^2} \leq \frac{\bar{n}}{ 100 \log \bar{n}}\). Take \[\begin{align} s := \left\lceil \frac{800}{\gamma^2} \mathsf{K}\right\rceil, \qquad k := \lceil 10 \log_2 \bar{n} \rceil, \qquad r := \left\lfloor \frac{\lfloor \bar{n}/s \rfloor - 1}{2k} \right\rfloor,\nonumber\\ n := 1 + 2k \cdot r, \qquad \epsilon:= \frac{32 \log(96/\gamma) \cdot k}{n}, \qquad \bar{n}' :=ns \nonumber. \end{align}\] Since \(\frac{800 \mathsf{K}}{\gamma^2} \leq \frac{\bar{n}}{ 100 \log \bar{n}}\), we have \(s \leq \frac{\bar n}{50 \log \bar n}\) and hence \(r \geq 1\). Since \(\bar{n}' \leq \bar{n}\), it suffices to prove the lower bound with \(\bar{n}'\) in place of \(\bar{n}\) (we can simply pad the last \(\bar{n}-\bar{n}'\) coordinates deterministically).

Suppose to the contrary that such \(\mathsf{Alg}\) exists, and consider the execution of \(\mathsf{Alg}\) with respect to the distribution \(\mu^\star = \mu_{\tau^{(1:s)}}\) and mapping \(\hat{\mu}_{\tau^{(1:s)}}\), where \(\tau^{(1:s)} \sim \mathcal{H}_{n,k,q,\epsilon}^s\) is drawn uniformly at random. Note that \(\mu_{\tau^{(1:s)}} \in \Delta(\{0,1\}^{\bar{n}'})\), and that the domain of \(\hat{\mu}_{\tau^{(1:s)}}\) is \(\{0,1\}^{\leq \bar{n}'}\). First, 22 ensures that we indeed have that \(\frac{1}{(1+\gamma)^2} \leq \frac{\mu_{\tau^{(1:s)}}(x)}{\hat{\mu}_{\tau^{(1:s)}}(x)} \leq (1+\gamma)^2\) for all \(x \in \{0,1\}^{\leq \bar{n}'}\) with probability \(1\). Further, the definitions of \(\mu_{\tau^{(1:s)}}\) and \(\hat{\mu}_{\tau^{(1:s)}}\) ensure that \(\mu_{\tau^{(1:s)}}(x) = \hat{\mu}_{\tau^{(1:s)}}(x)\) for all \(x \in \{0,1\}^{\bar{n}}\). Hence 1 is satisfied.

For any instantiation of \(\tau^{(1:s)}\), let the distribution of the output \(X = (X^{(1)}, \ldots, X^{(s)}) \in \{0,1\}^{\bar{n}}\) of \(\mathsf{Alg}\) be denoted \(\hat{\nu}_{\tau^{(1:s)}}\), and the distribution of the first bits of each block, namely \((X^{(1)}_1, \ldots, X^{(s)}_1) \in \{0,1\}^s\), be denoted \(\hat{\beta}_{\tau^{(1:s)}}\).

For \(\tau = (v^{\mathsf{init}}, \phi, \psi) \in \mathcal{H}_{n,k,q,\epsilon}\), let \(\alpha_\tau \in \Delta(\{0,1\})\) be the distribution which puts mass \(\frac{1+\gamma}{2+\gamma}\) on \(v^{\mathsf{init}}\) and mass \(\frac{1}{2+\gamma}\) on \(1-v^{\mathsf{init}}\); in other words, \(\alpha_\tau\) is the distribution of \(X_1\), for \(X = (X_1, \ldots, X_n) \sim \mu_\tau\). Let \(\alpha_{\tau^{(1:s)}} := \alpha_{\tau^{(1)}} \times \cdots \times \alpha_{\tau^{(s)}} \in \Delta(\{0,1\}^s)\). Next, we may write \[\begin{align} \mathsf{K}\geq & \mathbb{E}_{\tau^{(1:s)} \sim \mathcal{H}_{n,k,q,\epsilon}^s} \left[ D_{\mathsf{KL}}({\mu_{\tau^{(1:s)}}}||{\hat{\nu}_{\tau^{(1:s)}}}) \right] \geq \mathbb{E}_{\tau^{(1:s)} \sim \mathcal{H}_{n,k,q,\epsilon}^s} \left[ D_{\mathsf{KL}}({\alpha_{\tau^{(1:s)}}}||{\hat{\beta}_{\tau^{(1:s)}}}) \right] \label{eq:exp-tau-alphabeta}, \end{align}\tag{62}\] where the first inequality uses the assumption on \(\mathsf{Alg}\) and the second inequality uses the data processing inequality. Next, for any \(\tau^{(1:s)} \in \mathcal{H}_{n,k,q,\epsilon}^s\), the chain rule for KL divergence gives \[\begin{align} D_{\mathsf{KL}}({\alpha_{\tau^{(1:s)}}}||{\hat{\beta}_{\tau^{(1:s)}}}) =& \sum_{i=1}^s \mathbb{E}_{(X^{(1)}, \ldots, X^{(i-1)}) \sim \alpha_{\tau^{(1:i-1)}}}\left[D_{\mathsf{KL}}({\alpha_{\tau^{(i)}}}||{\hat{\beta}_{\tau^{(1:s)}}(X^{(i)} = \cdot \mid X^{(1)}, \ldots, X^{(i-1)})})\right]\label{eq:alphabeta-chain}. \end{align}\tag{63}\] Combining 62 63 as well as convexity of KL divergence gives that there exists some \(i \in [s]\) such that \[\begin{align} & \mathbb{E}_{\tau^{(1:s)} \sim \mathcal{H}_{n,k,q,\epsilon}^s}\left[ D_{\mathsf{KL}}({\alpha_{\tau^{(i)}}}||{\hat{\beta}_{\tau^{(1:s)}}(X^{(i)} = \cdot)})\right]\nonumber\\ \leq & \mathbb{E}_{\tau^{(1:s)} \sim \mathcal{H}_{n,k,q,\epsilon}^{s}}\mathbb{E}_{(X^{(1)}, \ldots, X^{(i-1)}) \sim \alpha_{\tau^{(1:i-1)}}}\left[D_{\mathsf{KL}}({\alpha_{\tau^{(i)}}}||{\hat{\beta}_{\tau^{(1:s)}}(X^{(i)} = \cdot \mid X^{(1)}, \ldots, X^{(i-1)})})\right] \leq \frac{\mathsf{K}}{s}.\label{eq:algi-output} \end{align}\tag{64}\] This contradicts 21, however: consider the algorithm \(\mathsf{Alg}'\) which functions as follows, given access to \(\hat{\mu}_{\tau^{(i)}}\), for \(\tau^{(i)} \sim \mathcal{H}_{n,k,q,\epsilon}\). It draws \(\tau^{(j)} \sim \mathcal{H}_{n,k,q,\epsilon}\) uniformly for each \(j \in [s]\) with \(j \neq i\), and then simulates \(\mathsf{Alg}\), using \(\hat{\mu}_{\tau^{(i)}}\) together with \(\hat{\mu}_{\tau^{(j)}}\) (where \(\tau^{(j)}\) are known for \(j \neq i\)) to simulate access to the oracle \(\hat{\mu}_{\tau^{(1:s)}}\). The output of \(\mathsf{Alg}'\) is the first bit of the \(i\)th block of the output of \(\mathsf{Alg}\). By 64 , \(\mathsf{Alg}'\) outputs a distribution whose KL divergence from \(\alpha_{\tau^{(i)}}\) is at most \(\frac{\mathsf{K}}{s}\); in particular, by Pinsker’s inequality, the probability that the output bit of \(\mathsf{Alg}'\) is equal to \((v^{\mathsf{init}})^{(i)}\) is at least \[\begin{align} \mathbb{P}_{X \sim \mu_{\tau^{(i)}}}(X_1 = (v^{\mathsf{init}})^{(i)}) - \sqrt{\frac{\mathsf{K}}{2s}} \geq \frac{1+\gamma}{2+\gamma} - \sqrt{\frac{\mathsf{K}}{2s}} - e^{-\epsilon r} \geq \frac{1+\gamma}{2+\gamma} - 2 \cdot \frac{\gamma}{20} \geq \frac{1}{2} + \frac{\gamma}{15}.\nonumber \end{align}\] Above, the first inequality uses 16. The second inequality uses that \(\sqrt{\mathsf{K}/(2s)} \leq \gamma/20\) (from the definition of \(s\)) and that \(e^{-\epsilon r} \leq \gamma/96\) (from the definition of \(\epsilon\) and \(r\) and the fact that \(2kr \geq 1\)).

This contradicts 21 as long as the number of queries \(q\) made by \(\mathsf{Alg}\) satisfies \(q \leq c'\gamma^2/ \epsilon^2\), for a sufficiently small constant \(c' > 0\) (note that \(q \leq c'\gamma^2/\epsilon^2\) also ensures that \(q \cdot 2^{-k} \leq q/\bar{n}^{10} \leq \bar{n}^{-5} \leq \gamma/100\) for sufficiently small \(\bar{n}\)). In turn, the condition \(q \leq c'\gamma^2/\epsilon^2\) is satisfied as long as \(q\leq c \cdot \frac{\bar{n}^2 \gamma^6}{\mathsf{K}^2 \log^2(\bar{n}) \cdot \log^2(1/\gamma)}\) for a sufficiently small constant \(c\). ◻

Proof. The algorithm \(\mathsf{Alg}'\) simply simulates \(\mathsf{Alg}\), answering queries to \(\hat{\mu}(x_{1:i})\) by returning \(\hat{\mu}(x_{1:i}) = \pi_{\mathsf{ref}}(x_{1:i}) \cdot \exp(\hat{V}(x_{1:i}))\). By scale-invariance of \(\mathsf{Alg}\), the distribution of the output of \(\mathsf{Alg}'\) is the same as if it had instead answered queries by returning \(\frac{1}{Z} \cdot \hat{\mu}(x_{1:i})\), which is an \(R\)-multiplicative approximation of \(\mu^\star\) by the assumption that \(\| \hat{V} - V^\star\|_\infty \leq \log R\). (Further, we have \(\frac{1}{Z} \hat{\mu}(x) = \mu^\star(x)\) for \(x \in \Sigma^n\).) Thus, the output distribution of \(\mathsf{Alg}'\) is \(\delta\)-close to \(\mu^\star\), as desired. ◻