% ==========================================================================
% One Sample Suffices for Matroid Prophet Inequalities against an
% Almighty Adversary.
%
% A self-contained rewrite. Every definition, lemma and proof is kept, but
% the ideas are explained in plain words along the way so that a careful
% high-school reader can follow the entire argument.
%
% The result: one independent sample per element is enough to beat any
% arrival-order adversary, even one that sees all samples, all online
% values, and the algorithm's whole random seed.
% ==========================================================================
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs,array}
\usepackage{xcolor}
\definecolor{linkblue}{RGB}{22,64,95}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue]{hyperref}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\DeclareMathOperator{\cl}{cl}
\DeclareMathOperator{\rk}{r}
\DeclareMathOperator{\OPT}{OPT}
\newcommand{\Ex}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\ind}[1]{\mathbf 1_{\{#1\}}}
\newcommand{\given}{\,\middle|\,}
\setlist[itemize]{topsep=4pt,itemsep=2pt,parsep=0pt}
\setlist[enumerate]{topsep=4pt,itemsep=3pt,parsep=0pt}
\allowdisplaybreaks[1]
\title{One Sample Suffices for Matroid Prophet Inequalities\\against an Almighty Adversary}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle

\begin{abstract}
One independent sample per element always suffices for a constant-competitive
prophet inequality on every finite matroid.  The guarantee survives the
strongest order adversary, one that sees every sample, every online value,
and the algorithm's whole random seed before choosing the order.  The rule
never needs the value distributions, and it achieves the absolute
competitive ratio $2^{-310}$.
\end{abstract}

\section{Introduction}\label{sec:intro}

\paragraph{What a prophet inequality is.}
A gambler is shown a finite set $E$ of items (called \emph{labels} or
\emph{elements}) one at a time in some order.  Each item $e$ carries a
nonnegative random value $V_e$.  When $e$ appears the gambler sees $V_e$
and must decide, on the spot, to keep it or drop it.  A keep is final and
cannot be undone.  The kept set must stay \emph{feasible}.  A \emph{prophet}
who sees every value in advance could keep the best feasible set.  A
prophet inequality asks how large a fraction of the prophet's value an
online rule can guarantee without knowing the future.

\paragraph{What feasibility means here.}
Feasibility is described by a known finite \emph{matroid}
$M=(E,\mathcal I)$.  Its members $\mathcal I$ are the \emph{independent
sets}.  Informally a matroid is any combinatorial rule of independence that
obeys two axioms:
\begin{itemize}
\item if $I\in\mathcal I$ and $J\subseteq I$ then $J\in\mathcal I$
      (subsets of independent sets are independent), and
\item if $I,J\in\mathcal I$ and $|I|<|J|$ then some $e\in J\setminus I$
      has $I\cup\{e\}\in\mathcal I$ (exchange).
\end{itemize}
Graph edge-sets without cycles, and linearly independent vectors, are the
two examples to keep in mind.  For a value vector $v=(v_e:e\in E)$ the best
feasible value is
\begin{equation}\label{eq:OPT}
 \OPT_M(v)=\max_{I\in\mathcal I}\sum_{e\in I}v_e .
\end{equation}

\paragraph{The information the rule gets.}
The rule never learns the distributions.  Instead, before any arrival it
receives one independent \emph{sample} $S_e$ for every label, each drawn
from the same law $D_e$ as the true online value $V_e$.  The pairs
$(S_e,V_e)$ are mutually independent.  The rule also uses its own random
seed $R$, drawn independently of all samples and values.  The sample vector
$S$ is the only statistical information available.

\paragraph{The adversary.}
The arrival order is chosen by an \emph{almighty ordering adversary}.  This
adversary may inspect the matroid, the distributions, the full sample vector
$S$, the full online vector $V$, and the rule's complete seed $R$ before it
picks the order $\pi$.  The rule is never told the order in advance.  This
is the harshest information pattern: nothing random the rule owns is hidden.

\paragraph{The main theorem.}
\begin{theorem}\label{thm:main}
There is a measurable online selection rule, depending on no distributions,
with the following property.  Let $M=(E,\mathcal I)$ be any finite known
labeled matroid, and let $(S_e,V_e:e\in E)$ be mutually independent
nonnegative random variables with $S_e$ and $V_e$ sharing an arbitrary law
$D_e$.  Assume $\Ex[\OPT_M(V)]<\infty$.  The rule receives exactly the
sample vector $S$ before arrivals and uses a seed $R$ independent of $S,V$.
For every measurable permutation rule $\pi$ that may depend on $M$, the laws
$(D_e)$, $S$, $V$ and $R$, the rule accepts an independent set $A$, decides
irrevocably at each arrival using only the available history, and
\begin{equation}\label{eq:main-bound}
 \Ex\!\left[\sum_{e\in A}V_e\right]\ \ge\ 2^{-310}\,\Ex[\OPT_M(V)] .
\end{equation}
\end{theorem}
The constant is absolute: it does not depend on the matroid, its size, its
rank, or the distributions.  The rule is a finite measurable construction.
No running-time bound and no polynomial independence-oracle bound are
claimed.  The proof actually gives the stronger constant $2^{-293}$; the
statement above carries deliberate slack.

\paragraph{Why a loss is unavoidable, and why the sample helps.}
With no sample at all, a single-choice prophet inequality guarantees only
$1/2$ of the prophet's value even with known distributions, and this is
sharp.  With one sample per element the single-choice problem again admits
$1/2$.  The point of the present theorem is that the same one-sample
information, made robust against a full-seed order adversary, yields a
positive constant on \emph{every} matroid at once.

\paragraph{The information pattern in words.}
The unusual demand is the expectation of a \emph{minimum}.  A guarantee for
each fixed order would only control $\min_\pi \Ex[\text{reward}]$.  We must
control $\Ex[\min_\pi \text{reward}]$: the adversary picks a different order
for each seed, so the order can be tuned to the coins.  This is why the
proof first builds a rule for a \emph{hidden fixed} value vector, where the
minimum over orders sits inside the expectation, and only afterwards
transfers that guarantee to the one-sample model.

\paragraph{Context.}
For known distributions, a sharp factor of $1/2$ for arbitrary matroids was
proved by Kleinberg and Weinberg \cite{KW12}, following the single-choice
factor-two bound credited to Garling (see Krengel and Sucheston
\cite{KS77}).  For unknown distributions, Azar, Kleinberg and Weinberg
\cite{AKW14} introduced the limited-information sample framework and the
reduction from order-oblivious secretary rules.  In the single-choice setting
Rubinstein, Wang and Weinberg \cite{RWW20} obtained the optimal one-sample
fraction $1/2$, and Caramanis et al. \cite{CDF22} developed a
greedy-ordered sample-pair method.  For general matroids, Lachish
\cite{Lachish14} and Feldman, Svensson and Zenklusen \cite{FSZ15} first
gave one-sample guarantees with a doubly logarithmic loss in the rank.
Fu et al. \cite{FLTWWZ24} then obtained a constant using
$O(\log^4(2+n))$ samples per element, and \cite{FSZ26} improved the
sample dependence.  Those constant results allow an almighty adversary,
but with a sample budget that grows with the matroid.  The present theorem
uses a single sample.  Recent constant results for ordinary random-order
matroid secretary selection are in \cite{Singla26,Huang26}.

\paragraph{Proof strategy in one breath.}
In plain words: reveal a few weights as samples, use them to guess where the
valuable labels sit, and protect those guesses with extra revealed labels,
so that no arrival order can spoil the plan.
Round the values down to powers of a large base $B$ so there are only a few
``weight levels''.  Process levels from low to high.  For each level, a
sparse mask of revealed samples builds \emph{flats} (matroid-closed sets)
that capture many high-value samples per unit of rank; a second sparse mask
of revealed samples adds \emph{guards} that protect those captures one step
ahead.  Slice these nested flats into two-step \emph{layers}, and within each
layer greedily keep arriving labels that are independent of everything kept
so far.  Nesting makes the union feasible for \emph{every} arrival order.
Three independent losses are then bounded: competition from lower levels
(Section~\ref{sec:safety}), the fact that revealed samples are sacrificed
(Section~\ref{sec:transfer}), and the gap between the model path and the
final guarded path (Section~\ref{sec:accounting}).  A simple separate branch
handles the case where one label dominates the optimum.  A final coupling
carries the fixed-vector guarantee to the one-sample model.

\paragraph{How the sections fit together.}
Section~\ref{sec:setup} recasts the problem for a hidden fixed value vector
and proves the one-sample simulation lemma.  Section~\ref{sec:algorithm}
builds the online rule.  The next three sections each bound one of the three
losses described above, in order: Section~\ref{sec:safety}, then
Section~\ref{sec:transfer}, then Section~\ref{sec:accounting}, where the
constant $2^{-293}$ is assembled and Proposition~\ref{prop:hidden} and
Theorem~\ref{thm:main} are proved.  Section~\ref{sec:secretary} is a short
application to the secretary problem.

\section{A fixed-vector formulation}\label{sec:setup}

Throughout, $M=(E,\mathcal I)$ is a finite labeled matroid.  For a set
$X\subseteq E$, its \emph{rank} $\rk(X)$ is the size of a largest independent
subset of $X$, and its \emph{closure} is
$\cl(X)=\{e\in E:\rk(X\cup\{e\})=\rk(X)\}$.  A set is a \emph{flat} when it
equals its own closure.  We say $X$ \emph{spans} $A$ when
$A\subseteq\cl(X)$.  Write $L=\cl(\varnothing)$ for the set of \emph{loops}
(elements that are in no independent set), and put
\[
 \rk(A\mid P)=\rk(A\cup P)-\rk(P),\qquad
 \OPT_M(w)=\max_{I\in\mathcal I}\sum_{e\in I}w_e .
\]
Inside a closure, a rank argument, or a map on flats, a sum of sets means
their union.  A set is \emph{independent over $P$} when its conditional rank
over $P$ equals its size.  We fix one total order on the labels, used only to
break ties, once and for all.

\paragraph{The hidden-vector game.}
We first solve a cleaner game.  The value vector $w$ is a fixed but unknown
nonnegative vector.  Before arrivals the rule draws a random mask
$B_0\subseteq E$, independently of $w$, and is told $w$ on $B_0$.  It must
reject every label of $B_0$ (those samples are \emph{sacrificed}).  On every
other label it learns $w_e$ only when that label arrives.  The mask may
depend on the whole seed $R$.  Let $A(w,R,\pi)$ be the accepted set under
order $\pi$.

\begin{proposition}\label{prop:hidden}
There is a measurable rule for the hidden-vector game that is feasible for
every realization and every order and, for every
$w\in[0,\infty)^E$, satisfies
\begin{equation}\label{eq:hidden-guarantee}
 \Ex_R\!\left[\min_{\pi}\sum_{e\in A(w,R,\pi)}w_e\right]
 \ \ge\ 2^{-293}\,\OPT_M(w).
\end{equation}
Its revealed mask is chosen before any weight is seen.
\end{proposition}

The minimum in \eqref{eq:hidden-guarantee} is \emph{inside} the expectation.
So the adversary may choose a different order for every seed.  Everything
below is for a fixed $M,w$, which we suppress inside conditional
expectations.  The next lemma is the only bridge to Theorem~\ref{thm:main}.

\begin{lemma}[One-sample simulation]\label{lem:simulation}
A measurable hidden-vector rule satisfying \eqref{eq:hidden-guarantee} gives
a measurable one-sample rule with the same competitive ratio against the
adversary of Theorem~\ref{thm:main}.
\end{lemma}
\begin{proof}
Draw the rule's seed independently of $S,V$.  For the analysis, glue the two
copies together:
\[
 w^{\mathrm{glue}}_e=
 \begin{cases}S_e,&e\in B_0(R),\\ V_e,&e\notin B_0(R).\end{cases}
\]
Given the seed, the choice of which copy supplies each label is fixed, and
the mutual independence with matching laws gives
$\mathcal L(w^{\mathrm{glue}}\mid R)=\bigotimes_e D_e$, the law of $V$.
Hence $w^{\mathrm{glue}}$ is independent of the seed.

Run the hidden-vector rule with $S_e$ on its revealed mask and $V_e$
elsewhere, ignoring unused samples and rejecting revealed labels without
looking at their online values.  Induction on arrivals shows that, for
every fixed $S,V,R$ and every order, this execution accepts exactly
$A(w^{\mathrm{glue}},R,\pi)$, and each accepted weight is its true online
value.  So for any adversarial order, even one using all unused samples and
values, the reward is at least
$\min_{\pi'}\sum_{e\in A(w^{\mathrm{glue}},R,\pi')}w^{\mathrm{glue}}_e$.
Integrate \eqref{eq:hidden-guarantee} using independence of the glued vector
and seed.  Nonnegative integration needs no moment hypothesis beyond the
reported one, and feasibility caps the reward by $\OPT_M(V)$, whose
expectation is finite.
\end{proof}

\subsection{Elementary matroid facts}\label{sec:matroid-facts}

We use only rank and closure, so nothing below needs representability.  The
independent sets contain $\varnothing$, are closed under subsets, and satisfy
exchange.  Exchange implies that all maximal independent subsets of a set
have the same size and that independent sets extend to bases of larger sets.
Rank is \emph{submodular}:
\begin{equation}\label{eq:rank-submodular}
 \rk(A)+\rk(B)\ \ge\ \rk(A\cup B)+\rk(A\cap B).
\end{equation}
Indeed, take a basis of $A\cap B$, extend it to a basis of $A$, then to a
basis of $A\cup B$ using elements of $B\setminus A$.  The initial basis
together with those last elements is independent inside $B$, which gives the
inequality.  Two consequences we will use constantly:
\begin{itemize}
\item $\rk(Z\mid P)$ can only decrease as $P$ grows;
\item closure is increasing and idempotent, and adjoining already-spanned
      elements changes neither rank nor closure.
\end{itemize}
Finally, scanning any set $Z$ and greedily keeping the elements that raise
rank over a fixed base $P$ selects an independent set over $P$ of size
$\rk(Z\mid P)$ that spans all of $Z$ over $P$.

\section{Constructing the hidden-vector rule}\label{sec:algorithm}

We build the rule of Proposition~\ref{prop:hidden} for a fixed hidden vector
$w$.  It rounds values to geometric levels and flips a fair coin between two
sub-rules.  The \emph{maximum} branch handles the case where one label
dominates the optimum.  The \emph{main} branch filters arrivals against
revealed samples and sorts them into layers of nested flats built from those
samples; greedy independent sets from different layers then combine feasibly.

\subsection{Constants, rounding, and the maximum branch}

Fix the constants
\begin{equation}\label{eq:constants}
 B=2^{32},\qquad \kappa=2^{100},\qquad t=2^{-140},\qquad
 \eta=2^{-12},\qquad \gamma=\eta/16=2^{-16}.
\end{equation}
Here $B$ separates weight levels, $\kappa$ is the rank charge in the density
expansions, $t$ is the common sparsity of the guard and eligibility masks,
and the exit cutoff $\eta$ yields the sample-to-rank coefficient $\gamma$.
The sizes leave room for every loss combined in Section~\ref{sec:accounting}.

For $w_e>0$ round down,
$u_e=B^{\lfloor\log_B w_e\rfloor}$, and put $u_e=0$ when $w_e=0$.  Write
$u(Z)=\sum_{e\in Z}u_e$ and $W=\OPT_M(u)$.  Coordinates are rounded when
their weight is revealed or arrives; the full vector $u$ is for analysis
only.  Rounding gives
\begin{equation}\label{eq:rounding}
 \OPT_M(w)/B\ \le\ W\ \le\ \OPT_M(w).
\end{equation}
Higher rounded weight means higher priority, ties broken by the fixed label
order.  Running priority greedy over all positive labels keeps an
independent set $I^*$ of $u$-weight $W$: its intersection with every initial
segment of weight levels has full rank there, so adding up the gains of
successive levels proves optimality.

Let $m_*$ be the largest rounded weight of a positive nonloop, or $0$ if
there is none.  The \emph{maximum rule} reveals a fair independent mask
(rate $1/2$).  It accepts the first label outside the mask that is a positive
nonloop of higher priority than every positive nonloop in the mask, then
accepts nothing more.
Its guarantee is simple.  If there are at least two positive nonloops, then
with probability $1/4$ the top-priority one lies outside the mask and the
second lies in the mask; on that event only the top one can clear the
threshold, so it is
accepted in every order.  With one positive nonloop, success has probability
$1/2$.  Hence in all cases
\begin{equation}\label{eq:maximum}
 \Ex\!\left[\min_\pi u(A_{\mathrm{max}}(R,\pi))\right]\ \ge\ m_*/4.
\end{equation}
Final rule: with probability $1/2$ play the maximum rule and with
probability $1/2$ play the main rule built below.  All coins, including
unused branch coins, are drawn initially and independently of $w$.

\subsection{Candidates and weight groups}

The main rule draws mutually independent masks $H,D,C,T$, independently
across labels, with membership probabilities
\begin{center}
\begin{tabular}{@{}ccl@{}}
\toprule
Mask & Probability & Role \\
\midrule
$H$ & $1/2$ & filters candidates by higher-priority span \\
$D$ & $1/4$ & lists weight groups and supplies density data \\
$C$ & $t$   & supplies guards for the flat paths \\
$T$ & $t$   & thins online eligibility independently of the paths \\
\bottomrule
\end{tabular}
\end{center}
Reveal and sacrifice the weights on $H\cup D\cup C$.  By
Lemma~\ref{lem:simulation} these revealed weights are sample coordinates.
Being in $T$ alone reveals nothing and forces no rejection.  For each $e$
let $H_{>e}$ be the labels of $H$ of higher priority than $e$, and define a
candidate set together with a comparison independent set
\begin{equation}\label{eq:candidates}
 U=\{e\notin H:u_e>0,\ e\notin\cl(H_{>e})\},\qquad Y=I^*\setminus H.
\end{equation}
Only $U$ matters for analysis; the candidate test is computable as soon as
the weight of $e$ is known.

\begin{lemma}[Candidate mass]\label{lem:filter}
$Y$ is independent, $Y\subseteq U$, and
\begin{equation}\label{eq:candidate-mass}
 \Ex_H u(Y)=W/2,\qquad \Ex_H u(U)\le W .
\end{equation}
\end{lemma}
\begin{proof}
For $e\in I^*$ no higher-priority labels span $e$, so neither do the
higher-priority labels of $H$; thus $Y\subseteq U$, and the fair mask gives
the first identity.  Condition on all higher-priority memberships of $H$.
Then $\{e\notin\cl(H_{>e})\}$ is fixed, and its contribution to $u(U)$ has
the same expectation as the event that $e\in H$ and $e$ is chosen by
priority greedy on $H$.  Summing over positive labels, the expected greedy
value on $H$ is at most $W$.
\end{proof}

Conditional on $H$, the \emph{true weight groups} are
\[
 U_i=\{e\in U:u_e=B^i\},\quad n_i=|U_i|,\quad Y_i=Y\cap U_i
 \qquad(i\in\mathbb Z),
\]
empty ones omitted.  A group is \emph{listed} when $D\cap U_i\ne\varnothing$.
List the listed groups $G_1,\dots,G_m$ from low to high weight and write
$D_h=D\cap G_h$, $C_h=C\cap G_h$, $T_h=T\cap G_h$.  The whole $D_h,C_h$ is
known before arrivals: every label of $D\cup C$ is revealed, and its
candidate test uses only $H$ and its own weight.  The algorithm never needs
the full $G_h$ nor the true sizes $n_i$.  All candidates are nonloops.

\subsection{Density expansions}

For a listed group $h$ and a flat $P$, let $Q_h(P)$ be the largest flat
maximizing
\begin{equation}\label{eq:density-objective}
 f_h(Z)=|D_h\cap Z|-\kappa\rk(Z)\qquad\text{over flats }Z\supseteq P .
\end{equation}
For a nonflat argument take its closure first.  The objective rewards the
number of $D_h$ samples spanned and charges $\kappa$ per unit of rank, so
extending the flat and picking up more samples costs rank only at that rate.
This is a contracted, sample-restricted form of the cardinality-minus-rank
maximization behind principal partitions (Santiago, Sergeev and Zenklusen
\cite{SSZ25}); we prove the properties we need directly.

\begin{lemma}[Density expansion]\label{lem:density}
The largest maximizer in \eqref{eq:density-objective} exists, the map $Q_h$
is increasing, $P\subseteq Q_h(P)$, and if $Q=Q_h(P)$ then for every set $Z$
\begin{equation}\label{eq:density-residual}
 |D_h\cap(\cl(Q+Z)\setminus Q)|\ \le\ \kappa\,\rk(Z\mid Q).
\end{equation}
\end{lemma}
\begin{proof}
The function $f_h$ is supermodular on the lattice of flats: the counting
term is supermodular under intersection and closed union, and the rank term
is supermodular by \eqref{eq:rank-submodular}.  There are finitely many
flats, and the closed union of two maximizers containing $P$ is again a
maximizer, so a largest maximizer exists.

For $P\subseteq P'$, put $Q=Q_h(P)$, $Q'=Q_h(P')$.  The flats $Q\cap Q'$
and $\cl(Q\cup Q')$ are feasible at $P$ and at $P'$ respectively.  Optimality
gives one inequality, supermodularity the reverse:
\[
 f_h(Q\cap Q')+f_h(\cl(Q\cup Q'))
 \ \le\ f_h(Q)+f_h(Q')\ \le\ f_h(Q\cap Q')+f_h(\cl(Q\cup Q')).
\]
Equality forces $\cl(Q\cup Q')$ to be a maximizer at $P'$, and the largest
maximizer there contains $Q$.  Finally, the flat $\cl(Q+Z)$ is feasible in
\eqref{eq:density-objective}; the rank gap between it and $Q$ is $\rk(Z\mid
Q)$, which yields \eqref{eq:density-residual}.
\end{proof}

\subsection{Nominal and guarded paths}

An integer $k$ is an \emph{auxiliary time}, unrelated to arrival time.  Set
$F_0(k)=L$ for $k<0$ and $F_0(k)=E$ for $k\ge0$.  For a listed group put
$a_h=-3h$ and define an enabled expansion
\[
 Q_{h,k}(P)=\begin{cases}Q_h(P),&k\ge a_h,\\ P,&k1$ we have $a_{h-1}=a_h+3$, and induction makes $F_{h-1}(k)=L$ for
$k0$.  At $k=a_h$ the lower flat is $L$, giving
the last assertion.
\end{proof}

\section{Reverse exposure and safe samples}\label{sec:safety}

The guards serve two purposes: they build the paths, and they protect a
sampled label against lower-weight competition inside its layer.  We relate
these by exposing the guard mask \emph{backwards} in auxiliary time.  A label
leaves its nominal flat at some step with a decent conditional probability,
and a comparison using the test mask turns the square of that probability
into safety.

Fix $H,D$ and a listed group $h$ throughout; so the groups, their indices,
the density maps, and $Y$ are fixed.  Define the lower-weight competition set
\begin{equation}\label{eq:competition-set}
 K_{h,b}=\bigcup_{j0$.  An adaptive procedure queries each coordinate at most once and
groups queries into transactions; the next query, the boundaries, and any
stopping rule depend only on the transcript and perhaps an independent
auxiliary seed.  Suppose the number of transactions is deterministically
bounded.  A transaction may be declared successful only if the positive bits
queried within it alone form a certificate for $\mathcal A$.  Then
\begin{equation}\label{eq:certificate-budget}
 \Ex[\text{number of successful transactions}]\ \le\ \log(1/\delta),
\end{equation}
with $\log$ the natural logarithm.
\end{lemma}
\begin{proof}
Condition on the auxiliary seed.  Conditional on any query transcript, all
unqueried bits keep their joint product law; this follows by induction over
the predictably chosen queries.

For a remaining set $V\subseteq V_0$, let $p(V)$ be the failure probability of
$\mathcal A$ when bits on $V$ keep their laws and all others are zero.  For
the set $I$ of positive bits already queried in the current transaction, let
$p_I(V)$ be the same with bits on $I$ forced to one.  Then
$\delta\le p(V)\le1$, $0\le p_I(V)\le p(V)$, and
$p(V\setminus\{e\})\ge p(V)$.  The ratio $Z=p_I(V)/p(V)$ starts each
transaction at one.

A query of $e\in V$ with success probability $q_e$ updates to $V'=V\setminus
\{e\}$ via the one-coordinate identity
$p_I(V)=(1-q_e)p_I(V')+q_e p_{I\cup\{e\}}(V')$, valid conditional on the
current transcript.  The denominator $p(V')$ is the same for either answer,
so
\begin{align}
 \Ex[Z-Z'\mid\text{transcript}]
  &=Z\Bigl(1-\frac{p(V)}{p(V')}\Bigr)
   =Z\bigl(1-e^{-(\log p(V')-\log p(V))}\bigr)\notag\\
  &\le\log p(V')-\log p(V),
 \label{eq:log-resource}
\end{align}
using $0\le Z\le1$ and $1-e^{-x}\le x$.

At a successful transaction's end, the certificate forces $p_I(V)=0$, so
$Z=0$; at any other end $0\le Z\le1$.  Thus a success indicator is bounded
by its realized net decrement $1-Z_{\rm end}$.  Summing \eqref{eq:log-resource}
over the queries and taking expectations bounds each success probability by
the expected increase of $\log p(V)$.  Reset $I$ to empty but keep the
depleted $V$; the logarithmic increments telescope across all transactions
to at most $0-\log p(V_0)=\log(1/\delta)$.  Adaptive stopping is covered by
padding with zero increments, since there are finitely many queries and a
bounded number of transactions.
\end{proof}

\begin{lemma}[Exit mass]\label{lem:exit}
Every nonloop $d$ exits its $h$-th nominal path by the end of the reverse
computation, and
\begin{equation}\label{eq:low-exit-hazard}
 \Prob(\text{$d$ exits at a step with }p_{b-1}<\eta\mid H,D)<\tfrac12.
\end{equation}
Consequently,
\begin{equation}\label{eq:squared-exit-mass}
 \sum_{b=a_h}^{0}\Ex\bigl[\ind{d\in X_h(b)}\,p_{b-1}^{2}\mid H,D\bigr]
 \ \ge\ \frac{\eta}{2}.
\end{equation}
\end{lemma}
\begin{proof}
Fix $p_0>0$ and consider steps, before exit, whose exit probability lies in
$[p_0,2p_0)$.  By monotonicity they form one block, possibly empty.  Its
first step is determined by the pre-step transcript.  Condition on a possible
transcript there, with time $k_0$ and input state $S^0$, and on the fresh
bits $V_0=\bigcup_{j\le h}(G_j\cap S^0_j)$ fix the increasing event
$\mathcal A=\{c:d\in(\mathcal G_{k_0}(c,S^0))_h\}$.  Its failure probability
satisfies $\delta\ge p_0$.

Treat the queries within each later step of the block as one transaction.  If
a step does not exit, its own fresh positive bits alone certify $\mathcal A$:
hold the step's actual input $S$ fixed and let $I$ be only its queried
positives.  Evaluating $\mathcal G_k(c^I,S)$ with every other guard bit zero
gives the same output as the actual step, since new $N_j$ are unchanged,
positive additions outside $N_j$ were queried and lie in $I$, and additions
inside $N_j$ are already spanned.  Earlier queried coordinates lie outside
the current domains, and $k\le k_0$, $S\subseteq S^0$, so
$\mathcal G_k(c^I,S)\subseteq\mathcal G_{k_0}(c^I,S^0)$.  Non-exit thus gives
$I\in\mathcal A$.  Lemma~\ref{lem:transactions} bounds the conditional
expected number of non-exit steps in the block by $\log(1/\delta)\le
\log(1/p_0)$; there is at most one exit step.  Hence the expected number of
steps in the range is at most $\log(1/p_0)+1$, and summing their exit
probabilities bounds the chance of exit in the range by
$2p_0(\log(1/p_0)+1)$.  For $p_0=2^{-(\ell+1)}$, summing over $\ell\ge12$,
\[
 \sum_{\ell=12}^{\infty}2^{-\ell}\bigl((\ell+1)\log2+1\bigr)
 =2^{-11}(14\log2+1)<\tfrac12.
\]
An exit at probability zero has probability zero, and $X_h(a_h-1)=L$ forces
every nonloop to exit; this proves \eqref{eq:low-exit-hazard}.

The exit mass at steps with $p_{b-1}\ge\eta$ is at least $1/2$.  There
$p_{b-1}^2\ge\eta p_{b-1}$, and $\ind{d\in X_h(b)}p_{b-1}$ has expectation
equal to the probability of exit at step $b$.  Summing gives
\eqref{eq:squared-exit-mass}.
\end{proof}

\subsection{A hybrid transition}

Lemma~\ref{lem:exit} supplies mass for squared exit probabilities.  To use
it we compare the ordinary guard transition with a second transition of the
same conditional law that also uses the departing labels' test bits; joint
exit of the two will certify safety against $K_{h,b}$.

Fix $a_h+2\le b\le0$ and a pre-step transcript $\mathcal H_b$.  Run the
ordinary step from $S=X(b)$ to $S'=X(b-1)$ with transcript
$\mathcal H_{b-1}$.  Both transitions start from the frozen input $S$; the
ordinary output $S'$ decides where each hybrid bit comes from:
\begin{equation}\label{eq:hybrid-bits}
 \begin{array}{c|c|c}
  \text{coordinates }e & \text{ordinary status} & \widetilde c_e\\ \hline
  G_j\cap S'_j & \text{unqueried} & \ind{e\in C}\\
  G_j\cap(S_j\setminus S'_j) & \text{queried} & \ind{e\in T}
 \end{array}
\end{equation}
Let $\widetilde N=\mathcal G_{b-1}(\widetilde c,S)$, with intermediate flats
$\widetilde A_j$.

Conditional on the \emph{complete} ordinary transcript, the partition is
fixed.  The retained $C$-bits on $G_j\cap S'_j$ were never queried, so keep
their independent rate-$t$ laws; no $T$-bit was queried, and the whole test
mask is independent of the guard mask.  So the hybrid vector has the fresh
product law conditional on $\mathcal H_{b-1}$, and its output law is the
ordinary transition law determined by $\mathcal H_b$.  In particular on
$\{d\in X_h(b)\}$ we have
$\Prob(d\notin\widetilde N_h\mid\mathcal H_{b-1})=p_{b-1}$, and the tower
property gives
\begin{align}
 &\Prob(d\in X_h(b),\,d\notin X_h(b-1),\,d\notin\widetilde N_h\mid\mathcal H_b)
 \notag\\
 &\quad=\Ex\bigl[\ind{d\in X_h(b)}\ind{d\notin X_h(b-1)}p_{b-1}\mid\mathcal H_b\bigr]
 =\ind{d\in X_h(b)}p_{b-1}^{2}.
 \label{eq:double-exit}
\end{align}
This holds for one endpoint at a time; the same $T$ is reused across
endpoints, and no joint independence across endpoints is claimed.

There is also a deterministic containment:
\begin{equation}\label{eq:hybrid-containment}
 Q_h\bigl(F_{h-1}(b-2)+K_{h,b}\bigr)\subseteq\widetilde N_h.
\end{equation}
Induct over $j