A
D
V
E
R
T

I
S
E
M
E
N
T

LEVEL 1 OF 1 · One-sample matroid prophet inequalities against an almighty adversary

One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary

expertly designed by an internal OpenAI model · released 2026-09-23 · original PDF

Theorems: 1	Lemmas: 15	Proofs: 17
Formulas: 877	Words: 12,591	Play time: ~1 hour

>>> How to Play <<<

We prove that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid. The guarantee holds even when the arrival-order adversary observes all samples, all online values, and the algorithm's entire random seed. The rule needs no description of the value distributions and achieves the absolute competitive ratio $2^{-310}$.

>>> Level Map <<<

Introduction

A prophet inequality compares irrevocable online choices with the best feasible choice after all values are known. Here feasibility is described by a known finite labeled matroid $M=(E,\mathcal I)$: its independent sets $\mathcal I$ are closed under taking subsets and satisfy the augmentation axiom. For a nonnegative vector $v=(v_e:e\in E)$, write \[\mathop{\mathrm{OPT}}_M(v)=\max_{I\in\mathcal I}\sum_{e\in I}v_e.\] An online rule observes labels and their values one at a time, and must accept or reject each label before the next arrival while keeping its accepted set independent. The value at each label has an unknown distribution; before arrivals the rule receives one independent sample from each of these distributions.

We prove a constant guarantee against an almighty ordering adversary. Besides the samples and the entire online value vector, this adversary sees the rule’s complete random seed before choosing the permutation. The rule is not told that future order. This exposes both the statistical information and every random choice that might otherwise protect the online rule from an unfavorable ordering.

Theorem 1. There is a measurable online selection rule, independent of the value 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 real random variables, with $S_e$ and $V_e$ having the same arbitrary law $D_e$. Assume $\mathbb E[\mathop{\mathrm{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$ depending on $M$, the laws $(D_e)$, $S$, $V$, and $R$, the rule accepts an independent set $A$, irrevocably deciding at each arrival using only the available history, and \[ \mathbb E\left[\sum_{e\in A}V_e\right] \ge 2^{-310}\mathbb E[\mathop{\mathrm{OPT}}_M(V)]. \tag{1}\]

The constant is independent of the matroid, its size and rank, and the distributions. The rule is a finite measurable construction; no running-time or polynomial independence-oracle guarantee is claimed. Section 6 proves the stronger constant $2^{-293}$, leaving slack in the stated bound. We use no distributional description, extra samples, or randomness concealed from the adversary.

The proof also gives a secretary consequence. In that model the weights are fixed before any randomness, and the rule observes and rejects a random initial segment of a uniformly random permutation. After this prefix, an adversary that sees all weights, the ordered prefix, and the complete rule seed may rearrange the remaining labels arbitrarily. Corollary 18 gives a constant guarantee even with this suffix order. Both results follow from the same fixed-weight guarantee: after a random set of weights is revealed and its labels sacrificed, the expected minimum reward over all orders is a constant fraction of the fixed optimum.

Historical context.

In the classical single-choice problem, independent nonnegative values with known distributions admit a sharp reward fraction of $1/2$; the original work of Krengel and Sucheston credits Garling for the factor-two bound (Krengel and Sucheston 1977). Kleinberg and Weinberg proved the same $1/2$ guarantee for arbitrary matroid constraints when the distributions are known (Kleinberg and Weinberg 2012). Their arrival model permits the next label to depend on previously revealed values, without giving the adversary the unseen values.

For unknown distributions, independent labeled samples provide a natural alternative source of information. Azar, Kleinberg, and Weinberg developed this limited-information framework and a reduction from order-oblivious secretary algorithms to single-sample prophet algorithms (Azar et al. 2014). In the single-choice setting, Rubinstein, Wang, and Weinberg obtained the optimal one-sample reward fraction $1/2$ (Rubinstein et al. 2020). Caramanis et al. developed greedy-ordered selection and a pointwise sample-pair framework for single-sample guarantees under structured feasibility constraints (Caramanis et al. 2022). These works illustrate how symmetry between a sample and a realized value can replace knowledge of a distribution.

This connection also links sample-based selection to the matroid secretary problem, introduced by Babaioff, Immorlica, and Kleinberg (Babaioff et al. 2007). In that problem the weights are fixed and the arrival order is uniformly random. Lachish (Lachish 2014) and Feldman, Svensson, and Zenklusen (Feldman et al. 2015) obtained guarantees with a doubly logarithmic loss in the rank. The latter gave an order-oblivious rule, whose guarantee survives adversarial reordering after its observation prefix, and derived a one-sample prophet inequality with the same loss (Feldman et al. 2015, Theorem 1.1 and Corollary 1.2). Thus one sample already gave guarantees for general matroids; we obtain a constant independent of rank under full-seed order selection. Recent work also obtains constant guarantees for ordinary random-order matroid secretary selection (Singla 2026; Huang 2026). Section 7 compares these results, which retain uniformly random arrivals throughout, with the full-seed adversarial-suffix consequence proved here.

For every fixed $0<\delta<1/4$, Fu et al. obtained a reward fraction $1/4-\delta$ for arbitrary matroids on $n$ elements, using $O_\delta(\log^4(2+n))$ samples per element (Fu et al. 2024). Feldman, Svensson, and Zenklusen subsequently improved the sample dependence on the ground-set size and rank (Feldman et al. 2026). These latter results allow an almighty adversary, which observes all random realizations before choosing the order, including the algorithm’s randomness. The full-seed adversary is the almighty adversary of the greedy online-contention-resolution framework of Feldman, Svensson, and Zenklusen (Feldman et al. 2016, sec. 1.1). The distinction between one sample and a sample budget growing with the matroid remains essential even when the latter gives a much larger numerical constant.

For a different arrival model, Abdi, Banihashem, Hajiaghayi, and Mittal give a one-sample $1/2$ matroid prophet guarantee using $O(n^2)$ independence queries (Abdi et al. 2026, Theorem 1.3). Their order is fixed independently of the samples, online values, and internal random coins. Theorem 1 instead permits the order to depend jointly on all of them. A bound for every fixed order controls the minimum of expected rewards, whereas this information pattern requires an expected minimum of rewards. The two guarantees therefore have different adversary interfaces, as well as different quantitative and computational bounds.

The density decompositions used below have a classical foundation in Edmonds’s matroid partition theorem (Edmonds 1965). Soto used principal partitions and their uniformly dense minors for secretary selection in the random-assignment model (Soto 2013); Santiago, Sergeev, and Zenklusen subsequently developed that approach without advance knowledge of the matroid (Santiago et al. 2025). Our density optimizer is applied within each sampled weight group and incorporated into paths expanded by independent guards. The layer construction also has a predecessor in the alternating restriction–contraction minors along sampled spans used by Feldman, Svensson, and Zenklusen (Feldman et al. 2015, sec. 3). Here the sampled density expansions and guards produce the flats, and the analysis must control the expected minimum over orders after all seed information is exposed.

Proof strategy.

We work first with a fixed hidden vector of weights. Independent masks reveal some coordinates, which are then sacrificed. The goal in this formulation is the expectation of the minimum over all orders, not a guarantee for an order chosen independently of the masks. A simple coordinatewise coupling subsequently transfers this guarantee to the one-sample model (Section 2).

After rounding weights into geometric levels, the main rule constructs nested paths of flats, that is, subsets closed under matroid span. The path index is an auxiliary integer, unrelated to arrival time. Process weight groups from low to high. For each group, enlarge the incoming flats to capture revealed labels at high density relative to rank. A separate sparse mask of revealed labels supplies guards, which enlarge a flat one auxiliary step before those labels enter its nominal path. Differences between alternate flats give two-step layers. Within each layer the rule greedily selects labels independent over the earlier endpoint flat. Nesting makes their union feasible for every arrival order (Section 3).

The proof must show that these layers retain enough valuable rank. Three losses arise, each requiring a different argument.

First, lower-weight arrivals may block a focal weight group. At a revealed label’s nominal entry step, the safety test asks whether it remains outside the density expansion of the earlier flat together with all possible lower-weight competitors. Expose the guards backwards in auxiliary time, so that the nominal flats shrink. A disjoint-certificate bound shows that a label usually leaves at a step with substantial conditional exit probability. A second transition, using the independent mask that governs online eligibility, turns this exit estimate into an expected safe count (Section 4). All masks are drawn initially; reverse exposure analyzes their law without concealing any coins from the adversary.

Second, the safe labels themselves have been sacrificed. In each layer, choose an independent set spanning the unsacrificed labels over the earlier flat and lower-weight competitors. The density inequality bounds the safe count by the density charge times the total size of these sets, plus the number of labels left outside their span. A large safe count can therefore fail to yield rank only if this residual is large. The residual lies entirely in the sacrificed mask. Such a set can depend on that mask, so a bound for one fixed set does not suffice. We encode residuals by the marks at which their labels first become spanned in two sequences with boundedly many inserted generators. A combinatorial bound controls all such marked-pivot patterns before the focal group’s mask is exposed. Crucially, its bound depends on the number of inserted generators, not the number of auxiliary times. A union bound then rules out large residuals with high probability, giving rank on unsacrificed labels (Section 5).

Third, passing from a group’s nominal path to the final guarded path enlarges the layer bases, which can reduce that rank. One common set of generators accounts for all such expansions. A telescoping conditional-rank identity charges its cost only once across the entire path. After independent eligibility thinning, the remaining rank lower-bounds cumulative accepted counts simultaneously for every permutation. Only then do we average and sum over weight levels (Section 6). A separate single-choice branch covers the case in which the heaviest label is a substantial part of the optimum.

Section 7 realizes the sacrificed mask as a random observation prefix and proves the secretary consequence.

A fixed-vector formulation

Throughout, $M=(E,\mathcal I)$ is a finite labeled matroid. For $X\subseteq E$, its rank $\mathop{\mathrm{r}}(X)$ is the maximum size of an independent subset of $X$, and $\mathop{\mathrm{cl}}(X)=\{e\in E:\mathop{\mathrm{r}}(X\cup\{e\})=\mathop{\mathrm{r}}(X)\}$ is its closure. A flat equals its closure; $X$ spans $A$ when $A\subseteq\mathop{\mathrm{cl}}(X)$. Write $L=\mathop{\mathrm{cl}}(\varnothing)$ for the set of loops, and put \[\mathop{\mathrm{r}}(A\mid P)=\mathop{\mathrm{r}}(A\cup P)-\mathop{\mathrm{r}}(P),\qquad \mathop{\mathrm{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 denotes their union. A set is independent over $P$ if its conditional rank over $P$ equals its cardinality. We fix a total order on the labels once and for all.

We first consider a deterministic nonnegative weight vector $w$ that is initially hidden. Before arrivals, a rule draws a mask $B_0\subseteq E$ independently of $w$ and learns $w$ on $B_0$. It must reject every label in $B_0$. On other labels it learns the weight at arrival. The mask may be a function of the rule’s complete initial random seed $R$. Let $A(w,R,\pi)$ denote its accepted set under permutation $\pi$.

Proposition 2. There is a measurable rule in the fixed-vector formulation that is feasible for every realization and every permutation, and for every $w\in[0,\infty)^E$ satisfies \[ \mathbb E_R\left[\min_{\pi}\sum_{e\in A(w,R,\pi)}w_e\right] \ge 2^{-293}\mathop{\mathrm{OPT}}_M(w). \tag{2}\] Its revealed mask is selected before any weights are seen.

The minimum in (2) is inside the expectation. In particular, an adversary may choose a different order for each seed. All estimates below are for a fixed $M,w$; we suppress these deterministic objects in conditional expectations.

Using samples on a sacrificed observation set and realized values on its complement is the simulation underlying the limited-information reduction of Azar, Kleinberg, and Weinberg (Azar et al. 2014, sec. 3). Related sample/value symmetries appear in the paired-draw analyses of Rubinstein, Wang, and Weinberg (Rubinstein et al. 2020, sec. 3) and Caramanis et al. (Caramanis et al. 2022, sec. 2 and 6). Here the mask may depend on the entire seed, and the transfer must preserve the minimum inside the expectation. We verify these requirements directly.

Lemma 3 (One-sample simulation). A measurable fixed-vector rule satisfying (2) yields a measurable one-sample rule with the same competitive ratio against the adversary of Theorem 1.

Proof. Draw its entire seed independently of the sample and value vectors $S,V$. For analysis, define \[w_e^{\mathrm{glue}}= \begin{cases}S_e,&e\in B_0(R),\\ V_e,&e\notin B_0(R).\end{cases}\] Given any seed, the choices of which copies to use are fixed. The mutual independence and matching laws of $S_e,V_e$ imply \[\mathcal L(w^{\mathrm{glue}}\mid R) =\bigotimes_{e\in E}D_e.\] Thus $w^{\mathrm{glue}}$ is independent of the complete seed and has the law of $V$. Implement the fixed-vector rule using $S_e$ only on its revealed mask and $V_e$ elsewhere when a label arrives. Ignore unused samples and reject revealed labels without using their online values. For every fixed $S,V,R$ and every permutation, induction on arrivals shows that this execution has exactly the accepted set $A(w^{\mathrm{glue}},R,\pi)$; each accepted weight is its actual online value.

Consequently, for any adversarial choice of $\pi$, including one depending on all the unused samples and values, its reward is at least $\min_{\pi'}\sum_{e\in A(w^{\mathrm{glue}},R,\pi')}w_e^{\mathrm{glue}}$. Integrate (2) using independence of the glued vector and seed. This gives the desired inequality. Nonnegative integration is valid without further moment assumptions, and feasibility bounds the reward by $\mathop{\mathrm{OPT}}_M(V)$, whose expectation is finite. ◻

Elementary matroid facts

The independent sets contain $\varnothing$, are closed under subsets, and satisfy augmentation: for $I,J\in\mathcal I$ with $|I|<|J|$, some $e\in J\setminus I$ has $I\cup\{e\}\in\mathcal I$. A basis of a set $X$ is a maximal independent subset of $X$. We use only rank and closure, so the argument applies to nonrepresentable matroids as well. The augmentation axiom implies that all maximal independent subsets of a given set have the same size, and that independent sets extend to bases of larger sets. Rank is submodular: \[ \mathop{\mathrm{r}}(A)+\mathop{\mathrm{r}}(B)\ge\mathop{\mathrm{r}}(A\cup B)+\mathop{\mathrm{r}}(A\cap B). \tag{3}\] Indeed, extend a basis of $A\cap B$ to one of $A$, then to one of $A\cup B$ using elements of $B\setminus A$. The initial intersection basis together with these last elements is independent in $B$, which proves the inequality. It follows that $\mathop{\mathrm{r}}(Z\mid P)$ decreases when $P$ grows. Closure is increasing and idempotent, and adjoining spanned elements changes neither rank nor closure. In particular, scanning a set and greedily accepting elements that increase rank over a fixed base $P$ selects an independent set over $P$ of size $\mathop{\mathrm{r}}(Z\mid P)$ and spans all of $Z$ over $P$.

Constructing the fixed-vector rule

We construct the rule of Proposition 2 for a fixed hidden weight vector. It uses geometric rounding and chooses with equal probability between a single-choice maximum branch and a main branch. The maximum branch handles weight concentrated on one label. The main branch filters arriving labels against revealed weights and assigns eligible arrivals to layers of nested flats constructed from those revealed weights. Greedy independent sets from different layers can then be combined feasibly.

Rounding and a maximum branch

Fix the constants \[ B=2^{32},\qquad \kappa=2^{100},\qquad t=2^{-140},\qquad \eta=2^{-12},\qquad \gamma=\eta/16=2^{-16}. \tag{4}\] Here $B$ separates weight levels, $\kappa$ is the rank charge in the density expansions, and $t$ is the common sparsity of the guard and eligibility masks. The exit-probability cutoff $\eta$ gives the sample-to-rank coefficient $\gamma$. The choices leave room for the losses combined in Section 6. For $w_e>0$, round down to $u_e=B^{\lfloor\log_B w_e\rfloor}$, and put $u_e=0$ when $w_e=0$. Define $u(Z)=\sum_{e\in Z}u_e$ and $W=\mathop{\mathrm{OPT}}_M(u)$. The rule rounds each coordinate when its weight is revealed or arrives; the full vector $u$ is used only for analysis. Then \[ \mathop{\mathrm{OPT}}_M(w)/B\le W\le\mathop{\mathrm{OPT}}_M(w). \tag{5}\] Larger rounded weights have higher priority, with ties resolved by the fixed label order. Priority greedy on all positive labels produces an independent set $I^*$ of weight $W$: its intersection with every initial segment of weight levels has full rank there, so summing the differences of successive levels proves optimality.

Let $m_*$ be the largest rounded weight of a positive nonloop, or zero if there is none. A maximum rule reveals a fair independent mask and accepts the first unmasked positive nonloop of higher priority than every revealed positive nonloop, then accepts nothing further. If there are at least two positive nonloops, with probability $1/4$ the highest-priority one is unmasked and the second is masked. On this event only the highest can exceed the threshold, so it is accepted in every order. With one positive nonloop, success has probability $1/2$. Thus in all cases \[ \mathbb E\big[\min_\pi u(A_{\mathrm{max}}(R,\pi))\big]\ge m_*/4. \tag{6}\] The final fixed-vector rule uses this rule or the main rule constructed next, with equal probability. The maximum branch gives the guarantee when the largest rounded weight is large enough relative to the rounded optimum; the main branch handles the complementary case. Draw all coins, including unused branch coins, initially and independently of the weights.

Candidates and weight groups

For the main rule draw mutually independent masks $H,D,C,T$, independently across labels, with respective membership probabilities $1/2,1/4,t,t$. Their roles are summarized below.

Mask	Probability	Role
$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

Reveal the fixed-vector weights on $H\cup D\cup C$ and sacrifice these labels. Under Lemma 3, these revealed weights are the corresponding sample coordinates. Membership in $T$ alone reveals no weight and forces no rejection. For each label $e$, let $H_{>e}$ be the labels in $H$ with higher priority than $e$. Define the candidate set and a comparison independent set by \[ U=\{e\notin H:u_e>0,\ e\notin\mathop{\mathrm{cl}}(H_{>e})\}, \qquad Y=I^*\setminus H. \tag{7}\] The full set $U$ is used for analysis; the candidate test itself is computable as soon as the weight of $e$ is known.

Lemma 4 (Candidate mass). The set $Y$ is independent, $Y\subseteq U$, and \[ \mathbb E_H u(Y)=W/2,\qquad \mathbb E_H u(U)\le W. \tag{8}\]

Proof. For $e\in I^*$, no higher-priority labels span $e$, so neither do the higher-priority labels of $H$. This proves $Y\subseteq U$; its expectation follows from the fair mask. Conditional on all higher-priority memberships in $H$, the event $e\notin\mathop{\mathrm{cl}}(H_{>e})$ is fixed. Its contribution to $u(U)$ has the same expected weight as the event that $e$ belongs to $H$ and is selected by priority greedy on $H$. Sum over the positive labels. The resulting expected greedy weight on $H$ is at most $W$. ◻

Conditional on $H$, the true weight groups \[U_i=\{e\in U:u_e=B^i\},\qquad n_i=|U_i|,\qquad Y_i=Y\cap U_i \quad(i\in\mathbb Z)\] are fixed. Empty groups may be omitted. A group is listed when $D\cap U_i\ne\varnothing$. Enumerate the listed groups as $G_1,\ldots,G_m$ from lower to higher weight, and write $D_h=D\cap G_h$, $C_h=C\cap G_h$, and $T_h=T\cap G_h$. The complete $D_h,C_h$ are known before arrivals: every label of $D\cup C$ is revealed, and its candidate test uses only $H$ and its own weight. The algorithm needs neither the complete $G_h$ nor the true group sizes $n_i$. All candidates are nonloops.

Density expansions

For a listed group $h$ and a flat $P$, let $Q_h(P)$ be the largest flat maximizing \[ f_h(Z)=|D_h\cap Z|-\kappa\mathop{\mathrm{r}}(Z) \qquad\text{over flats }Z\supseteq P. \tag{9}\] For a nonflat argument, take its closure first. The objective rewards the number of $D_h$ labels spanned and charges $\kappa$ per unit of rank. Comparison with a further extension bounds its additional sample count by $\kappa$ times its additional rank. A separate telescoping argument in Lemma 8 bounds the generators used over the entire path.

This is a contracted, sample-restricted form of the cardinality-minus-rank maximization associated with principal partitions; see Santiago, Sergeev, and Zenklusen (Santiago et al. 2025, sec. 3.1, Equation (1)). We prove the needed monotonicity and residual-rank bounds directly.

Lemma 5 (Density expansion). The largest maximizer in (9) exists, the map $Q_h$ is increasing, and $P\subseteq Q_h(P)$. If $Q=Q_h(P)$, then for every set $Z$, \[ |D_h\cap(\mathop{\mathrm{cl}}(Q+Z)\setminus Q)|\le\kappa\mathop{\mathrm{r}}(Z\mid Q). \tag{10}\]

Proof. The function $f_h$ is supermodular on the lattice of flats: the counting term is supermodular under intersection and closed union, and the negative rank term is supermodular by (3). There are finitely many flats. The closed union of any two maximizers containing $P$ is again a maximizer, so there is a largest one.

For $P\subseteq P'$, put $Q=Q_h(P)$ and $Q'=Q_h(P')$. The flat $Q\cap Q'$ is feasible at $P$ and $\mathop{\mathrm{cl}}(Q\cup Q')$ is feasible at $P'$. Optimality gives one inequality and supermodularity the reverse: \[f_h(Q\cap Q')+f_h(\mathop{\mathrm{cl}}(Q\cup Q')) \le f_h(Q)+f_h(Q') \le f_h(Q\cap Q')+f_h(\mathop{\mathrm{cl}}(Q\cup Q')).\] Equality in the two optimality comparisons shows that $\mathop{\mathrm{cl}}(Q\cup Q')$ is also a maximizer at $P'$. Its largest maximizer contains $Q$, as claimed. Finally compare $Q$ with the feasible flat $\mathop{\mathrm{cl}}(Q+Z)$ in (9). The difference of their ranks is $\mathop{\mathrm{r}}(Z\mid Q)$, giving (10). ◻

Nominal paths and guards

Integer $k$ denotes an auxiliary time, unrelated to arrival time. Set $F_0(k)=L$ for $k<0$ and $F_0(k)=E$ for $k\ge0$. For each 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,&k<a_h,\end{cases} \qquad(P\text{ a flat}).\] In increasing group order, form its nominal and guarded paths \[ X_h(k)=Q_{h,k}(F_{h-1}(k)),\qquad F_h(k)=\mathop{\mathrm{cl}}\bigl(X_h(k)+(C_h\cap X_h(k+1))\bigr). \tag{11}\] Thus a guard uses a label one auxiliary step before it enters the nominal path. Each density map uses only $D_h$ and the known matroid, and each guard set uses the revealed labels $C_h$. Consequently these flats can be computed as subsets of $E$ before arrivals, even though the weights of some labels they contain remain unknown.

Lemma 6 (Path properties). The paths increase with $k$ and satisfy \[ F_{h-1}(k)\subseteq X_h(k)\subseteq F_h(k)\subseteq X_h(k+1). \tag{12}\] They equal $E$ for $k\ge0$. Moreover $X_h(k)=L$ for $k<a_h$ and $F_h(k)=L$ for $k<a_h-1$. If $e$ is a nonloop, its nominal birth \[b_h(e)=\min\{k:e\in X_h(k)\}\] is either $a_h$, with $e\in Q_h(L)$, or belongs to $[a_h+2,0]$.

Proof. Induct on $h$. The map $Q_{h,k}$ is increasing both in its argument and in $k$, since enabling it replaces the identity by an extensive increasing map. Thus $X_h$ and then $F_h$ are increasing. The first two inclusions in (12) are extensiveness; the last follows because both sets adjoined in the definition of $F_h(k)$ lie in the flat $X_h(k+1)$. The same recursion gives $E$ at times at least zero.

For $h>1$, $a_{h-1}=a_h+3$ and the inductive lower bound makes $F_{h-1}(k)=L$ for $k<a_h+2$; this also holds for $h=1$ directly from $F_0$. Before $a_h$ the new map is the identity, proving the asserted lower bounds for $X_h$ and $F_h$. At $a_h$ and $a_h+1$, the nominal flat is the same flat $Q_h(L)$, so no nonloop is born at $a_h+1$. ◻

The online decisions

Choose an independent fair parity $\varepsilon\in\{0,1\}$ and put $\widehat F(k)=F_m(k)$. When $m=0$, use $\widehat F=F_0$ and reject all arrivals. In general the layer endpoints are the integers $b\equiv\varepsilon\pmod2$, with layer $(b-2,b]$ having base $\widehat F(b-2)$. The rule maintains a set $A_b\subseteq\widehat F(b)$ in each layer, independent over its base $\widehat F(b-2)$. Since successive layers share an endpoint, all labels selected in an earlier layer lie in the base of every later layer. Greedy selection in alternating restriction–contraction minors also appears in Feldman, Svensson, and Zenklusen (Feldman et al. 2015, sec. 3); here the nested flats come from the guarded density paths.

At arrival of a label $e$, perform the following operations.

Reject if $e\in H\cup D\cup C$, if its candidate test fails, or if its rounded weight is not listed.
For its listed group $h$, compute $b=b_h(e)$. Reject unless \[ e\in T,\qquad b\ge a_h+2,\qquad b\equiv\varepsilon\pmod2, \qquad e\notin\widehat F(b-2). \tag{13}\]
Let $A_b$ be the previously accepted labels assigned to this layer. Accept $e$ exactly when $\mathop{\mathrm{r}}(\{e\}\mid\widehat F(b-2)+A_b)=1$, and then add it to $A_b$.

These operations use the revealed data, the arriving label and weight, the seed, and the previous decisions. In particular, no full true weight group or future arrival is needed. By Lemma 6, the three-step activation schedule leaves no birth at $a_h+1$. Excluding the baseline birth $a_h$ therefore leaves exactly the births for which $b-2\ge a_h$: the density map is already enabled at the preceding layer endpoint. Figure 1 shows both the guard step and the nesting that makes layerwise decisions feasible.

Above: a density expansion followed by guards from the next nominal time gives $F_h(k)\subseteq X_h(k+1)$. Below: two consecutive layers of the chosen parity on the final path. The set $A_b$ is independent over $\widehat F(b-2)$ and lies in $\widehat F(b)$; $A_{b+2}$ is independent over this latter base. In the lower panel, the horizontal order is auxiliary time, regardless of the actual arrival order.

Lemma 7 (Feasibility and measurability). The main rule maintains an independent accepted set at every arrival prefix, for every permutation. It is a measurable rule based only on the allowed information.

Proof. Every eligible label at endpoint $b$ lies in $X_h(b)\subseteq\widehat F(b)$. The accepted set of its layer is independent over $\widehat F(b-2)$. In increasing auxiliary endpoint order, all earlier accepted layers lie in that base flat, so extending by the current layer preserves independence. This proves independence of the union for any interleaving of arrivals, and of every prefix.

All masks are drawn initially and the matroid is known. Each density maximization is over finitely many flats. By Lemma 6, it is enough to compute a finite interval of integer times for the at most $|E|$ listed groups. Positive rounding has countably many measurable level sets; each realized vector has finitely many occupied levels. All remaining operations are finite rank tests, comparisons, and set operations with fixed tie rules. They therefore define measurable decisions. Zeros are never passed to a logarithm, and loops fail the candidate test. ◻

A generator budget for the entire path

The rule is now fully specified. To analyze it, we need a bound on how much each density expansion can change the path. Bounding the rank increase separately at each time would charge the same sample labels repeatedly. The next lemma instead chooses one set of generators for all times. It also bounds the independent sampled mass excluded by the baseline-birth condition.

Lemma 8 (A generator budget for the entire path). For each listed group $h$ there is a set $J_h\subseteq D_h$ and increasing subsets $J_h(k)\subseteq J_h$ such that \[ X_h(k)=\mathop{\mathrm{cl}}(F_{h-1}(k)+J_h(k)),\qquad |J_h|\le |D_h|/\kappa. \tag{14}\] In particular $\mathop{\mathrm{r}}(Q_h(L))\le |D_h|/\kappa$.

Proof. Before $a_h$ no generators are needed. Process the enabled times $k=a_h,a_h+1,\ldots,0$ in order. Given the preceding generators, set \[P_k=\mathop{\mathrm{cl}}(F_{h-1}(k)+X_h(k-1)).\] By monotonicity, $P_k\subseteq X_h(k)$. It is feasible in the maximization defining $X_h(k)$, whence \[\begin{align*} \kappa\bigl(\mathop{\mathrm{r}}(X_h(k))-\mathop{\mathrm{r}}(P_k)\bigr) &\le |D_h\cap X_h(k)|-|D_h\cap P_k|\\ &\le |D_h\cap X_h(k)|-|D_h\cap X_h(k-1)|. \end{align*}\] The flat $R_k=\mathop{\mathrm{cl}}(F_{h-1}(k)+(D_h\cap X_h(k)))$ is contained in $X_h(k)$ and has exactly the same $D_h$ count. If this inclusion were proper, $R_k$ would have smaller rank, since a proper subflat has smaller rank. It would then improve the objective, contradicting optimality. Thus $R_k=X_h(k)$, and the extension over $P_k$ has a basis chosen from $D_h\cap X_h(k)$.

Adjoin such a basis to the generators, choosing by the fixed label order. Since $F_{h-1}$ increases, the preceding generators together with $F_{h-1}(k)$ already generate $P_k$. This proves the first identity inductively. The new generators are distinct, and their counts satisfy the displayed inequality. Summing it telescopes the $D_h$ counts and gives $|J_h|\le |D_h|/\kappa$. Extend the generator sets constantly for $k>0$. At $k=a_h$, the lower-group flat is $L$, yielding the last assertion. ◻

For the analysis, we first work on a group’s own nominal path. The next section shows that earlier groups’ guards protect a constant fraction of its independent sampled mass against lower-weight competition. We then transfer this sampled count to unsacrificed rank. Later groups’ path expansions will be paid for by a single rank budget in Section 6.

Reverse exposure and safe samples

The guards from lower-weight groups serve two purposes. They determine the paths, and they protect a sampled label against lower-weight competition in its layer. We relate these purposes by exposing the guard mask backwards in auxiliary time. A label leaves its nominal flat at a step having a reasonably large conditional exit probability with constant probability. A comparison using the test mask then turns the square of that exit probability into a safety guarantee.

Fix $H,D$ and a listed group $h$ throughout this section. Thus the groups, their indices, the density maps, and $Y$ are fixed. As elsewhere, the deterministic $M,w$ are suppressed from conditioning. Define \[ K_{h,b}=\bigcup_{j<h} \bigl(T_j\cap(X_j(b)\setminus X_j(b-1))\bigr). \tag{15}\] This set contains all possible eligible lower-weight competitors at endpoint $b$, and is contained in $F_{h-1}(b)$. It includes test-mask memberships on sacrificed labels; this only enlarges the comparison set. Let $\sigma_h$ count the labels $d\in D_h\cap Y$ whose birth $b$ on $X_h$ satisfies \[ a_h+2\le b\le0,\qquad b\equiv\varepsilon\pmod2,\qquad d\notin Q_h\bigl(F_{h-1}(b-2)+K_{h,b}\bigr). \tag{16}\] These are analysis quantities; the online rule does not compute them. Our objective is Lemma 11: a constant fraction of $D_h\cap Y$ contributes to $\sigma_h$ in expectation, apart from the loss $|D_h|/\kappa$. We first expose the guards backwards so that each step queries only previously untouched bits. A bound on disjoint positive certificates then locates an exit of substantial conditional probability. Comparing two transitions at that exit will establish the exclusion in (16).

The reverse computation and its filtration

The guard mask was drawn as part of the initial seed and may be fully known to the adversary. Reverse exposure analyzes that mask’s product law; it introduces no new online randomness and does not restrict the adversary’s information.

For $k<0$, a later state $S=(S_j:j\le h)$ and a guard-bit vector $c$, define a one-step map $\mathcal G_k(c,S)$ as follows: \[ \begin{aligned} A_0&=F_0(k),\qquad N_j=Q_{j,k}(A_{j-1}),\\ A_j&=\mathop{\mathrm{cl}}\bigl(N_j+\{e\in G_j\cap S_j:c_e=1\}\bigr) \quad(1\le j\le h). \end{aligned} \tag{17}\] Its output is $(N_j:j\le h)$. The map is increasing in $k$, in each coordinate of $S$, and in the bits $c$, by monotonicity and extensivity of the density maps. We may view $c$ as a bit vector on the fixed union of the groups, even though only its restrictions to $G_j\cap S_j$ are used.

Starting with $X_j(0)=E$, compute $X(k)$ at $k=-1,-2,\ldots,a_h-1$ using \[X(k)=\mathcal G_k(C,X(k+1)).\] This is exactly the defining path recursion. For an actual later state $S=X(k+1)$, the new $N_j$ is contained in $S_j$ for every choice of $c$. Indeed, inductively $A_{j-1}\subseteq S_{j-1}\subseteq F_{j-1}(k+1)$, so $N_j\subseteq Q_{j,k+1}(F_{j-1}(k+1))=S_j$; all the guard additions forming $A_j$ also belong to $S_j$. For $j=1$, use $F_0(k)\subseteq F_0(k+1)$ to begin the induction.

After computing $N_j$, inspect only the bits on \[ G_j\cap(S_j\setminus N_j). \tag{18}\] The omitted additions inside $N_j$ do not change its closure. Fix a label order within each such batch. Its domain is determined before its first query: $N_j$ uses only previous groups’ bits. The groups are disjoint and their domains shrink at each reverse step, so no coordinate is ever queried twice.

Let $\mathcal H_b$ be the sigma-field generated by the complete transcript just before the step from $X(b)$ to $X(b-1)$, including the queried labels, their answers, and the states obtained from them. Thus $\mathcal H_b\subseteq\mathcal H_{b-1}$ as reverse time advances. Conditional on $\mathcal H_b$, the unqueried bits on \[V_b=\bigcup_{j\le h}(G_j\cap X_j(b))\] are jointly independent Bernoulli bits of rate $t$. Indeed, the unqueried coordinates are exactly these domains, and each preceding query was chosen from its prior transcript. In particular, the conditional transition law is (17) with fresh product bits. The transcript reveals no test bits, parity, or flat at a smaller time that has not yet been computed.

For a fixed nonloop $d$, on $\{d\in X_h(b)\}$ define the predictable exit probability \[ p_{b-1}=\mathbb P\bigl(d\notin X_h(b-1)\mid\mathcal H_b\bigr). \tag{19}\] Set $p_{b-1}=0$ when $d\notin X_h(b)$. Before exit, these probabilities are nondecreasing in the order of the reverse computation. To see this, evaluate each conditional transition probability with an independent product mask $\xi$ on the whole union of the groups. Smaller time and smaller input state give a smaller output under this same $\xi$. Taking probabilities proves the assertion even though the domains of the unqueried bits change.

Certificates and exit mass

To control exits at steps with $p_{b-1}<\eta$, we consider bands of comparable exit probabilities. We will show that each survival within a band certifies one fixed increasing event using only that step’s newly queried positive bits. The next lemma bounds how many such disjoint certificates can occur.

An increasing Boolean event is a family $\mathcal A\subseteq2^V$ closed under taking supersets. A positive certificate for $\mathcal A$ is a set $I$ with $I\in\mathcal A$: setting the coordinates in $I$ to one already forces the event, whatever the other bits are.

Lemma 9 (Disjoint-query certificates). Let $V_0$ be finite, let its bits be independent Bernoulli random variables, and let $\mathcal A\subseteq2^{V_0}$ be increasing with failure probability $\delta>0$. An adaptive procedure queries each coordinate at most once and divides its queries into transactions. The next query, transaction boundaries, and stopping decisions depend only on the transcript and, if desired, an independent auxiliary seed. Suppose the number of transactions has a deterministic finite bound. A transaction may be declared successful only if the positive bits queried within that transaction alone form a certificate for $\mathcal A$. Then \[ \mathbb E[\text{number of successful transactions}] \le\log(1/\delta). \tag{20}\] Here and below $\log$ denotes the natural logarithm.

Proof. Condition on the auxiliary seed, if present. Conditional on every possible query transcript, all unqueried bits retain their joint original product law: the transcript specifies values only at the coordinates it queries. This follows by induction over the successive, predictably chosen queries.

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

Suppose the next query is $e\in V$, whose success probability is $q_e$. Write $V'=V\setminus\{e\}$, and let $Z'$ be the ratio after that query. The one-coordinate identity \[p_I(V)=(1-q_e)p_I(V')+q_e p_{I\cup\{e\}}(V')\] holds conditional on the full current transcript. In particular, the denominator $p(V')$ is the same for either answer, so the exact expected decrement and its logarithmic bound are \[\begin{align*} \mathbb E[Z-Z'\mid\text{current transcript}] &=Z\left(1-\frac{p(V)}{p(V')}\right)\\ &=Z\left(1-e^{-(\log p(V')-\log p(V))}\right) \le\log p(V')-\log p(V). \tag{21}\end{align*}\] The last inequality uses $0\le Z\le1$ and $1-e^{-x}\le x$ for $x\ge0$.

At the end of a successful transaction, the certificate forces $p_I(V)=0$, so $Z=0$. At every other transaction end, $0\le Z\le1$. Thus its success indicator is at most its realized net decrement $1-Z_{\rm end}$. Summing (21) over its queries and taking conditional expectations bounds its success probability by the expected increase of $\log p(V)$. Reset $I$ to the empty set for the next transaction, but keep the depleted $V$. The logarithmic increments then telescope across all transactions. Their total is at most $0-\log p(V_0)=\log(1/\delta)$.

This summation also covers adaptive stopping: there are at most $|V_0|$ queries and a bounded number of transactions, so one may pad every stopped sequence with zero increments and sum a deterministic finite number of conditional identities. No stopping-time limit is required. ◻

Lemma 10 (Exit mass). Every nonloop $d$ exits its $h$-th nominal path by the end of the reverse computation, and \[ \mathbb P(\text{$d$ exits at a step with }p_{b-1}<\eta\mid H,D)<\tfrac12. \tag{22}\] Consequently, \[ \sum_{b=a_h}^{0} \mathbb E\bigl[\mathbf 1_{\{d\in X_h(b)\}}p_{b-1}^{2}\mid H,D\bigr] \ge\frac{\eta}{2}. \tag{23}\]

Proof. Fix $p_0>0$ and consider steps, before exit, whose conditional 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, since the exit probabilities are predictable. Condition on a possible transcript there, with time $k_0$ and input state $S^0$. On the fresh bits in $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 $\delta$ is at least $p_0$.

Treat the queries within each subsequent step of the block as one transaction. If that step does not exit, its own positive queried bits alone certify $\mathcal A$. Here is the reason that earlier positive answers are unnecessary. Hold this step’s actual incoming state $S$ fixed, and let $I$ consist only of its queried positives. Write $c^I_e=\mathbf 1_{\{e\in I\}}$. Evaluating $\mathcal G_k(c^I,S)$, with every other guard bit set to zero, gives the same output as the actual step. Inductively in $j$, the new $N_j$ is unchanged, all positive guard additions outside $N_j$ were queried and belong to $I$, and omitted additions inside $N_j$ are already spanned. Previously queried coordinates are outside the current domains. Finally $k\le k_0$ and $S\subseteq S^0$ coordinatewise, so \[\mathcal G_k(c^I,S) \subseteq\mathcal G_{k_0}(c^I,S^0).\] Non-exit in the actual step therefore implies $I\in\mathcal A$. The incoming state is held fixed in this comparison; no earlier state is recomputed after previous positive bits are erased.

All transactions consume distinct coordinates. Lemma 9 bounds the conditional expected number of non-exit steps in this block by $\log(1/\delta)\le\log(1/p_0)$. There is at most one exit step. Thus, also without conditioning on the entry transcript, the expected number of steps in this range is at most $\log(1/p_0)+1$. Summing their conditional exit probabilities bounds the probability of exit in this range by \[2p_0\bigl(\log(1/p_0)+1\bigr).\] For $p_0=2^{-(\ell+1)}$, sum this bound over $\ell\ge12$ to obtain \[ \sum_{\ell=12}^{\infty} 2^{-\ell}\bigl((\ell+1)\log2+1\bigr) =2^{-11}(14\log2+1)<\tfrac12. \tag{24}\] An exit at a step with conditional probability zero has probability zero, since there are finitely many steps. Also $X_h(a_h-1)=L$, so every nonloop exits. This proves (22).

The total exit mass at steps having $p_{b-1}\ge\eta$ is at least $1/2$. For those steps $p_{b-1}^{2}\ge\eta p_{b-1}$, and $\mathbf 1_{\{d\in X_h(b)\}}p_{b-1}$ has expectation equal to the probability of exit at that step. Summing gives (23). ◻

A hybrid transition

Lemma 10 supplies mass for squared exit probabilities. To use it, we compare the ordinary guard transition with a second transition that has the same conditional law but incorporates the test bits of departing labels. The joint exit of the two transitions will imply protection against the competitors in $K_{h,b}$.

Fix an endpoint $a_h+2\le b\le0$ and a pre-step transcript $\mathcal H_b$. Perform the ordinary step from $S=X(b)$ to $S'=X(b-1)$, obtaining its complete transcript $\mathcal H_{b-1}$. Both transitions start from the same frozen input $S$; the ordinary output $S'$ determines which source supplies each hybrid bit: \[ \begin{array}{c|c|c} \text{coordinates }e & \text{ordinary guard-bit status} & \widetilde c_e\\ \hline G_j\cap S'_j & \text{unqueried} & \mathbf 1_{\{e\in C\}}\\[2pt] G_j\cap(S_j\setminus S'_j) & \text{queried in this step} & \mathbf 1_{\{e\in T\}} \end{array} \tag{25}\] Let $\widetilde N=\mathcal G_{b-1}(\widetilde c,S)$, and write $\widetilde A_j$ for its intermediate flats in (17).

Conditional on the complete ordinary-step transcript, the partition in (25) is fixed. The retained $C$-bits on $G_j\cap S'_j$ have never been queried, so all of them jointly retain their independent rate-$t$ laws. No $T$-bit has been queried, and the entire test mask is independent of the guard mask. Consequently the whole hybrid vector on the input domains has the fresh product law, conditional on $\mathcal H_{b-1}$. Its output law is the ordinary transition law determined by the earlier $\mathcal H_b$.

In particular, on $\{d\in X_h(b)\}$, $\mathbb P(d\notin\widetilde N_h\mid\mathcal H_{b-1})=p_{b-1}$. The tower property therefore gives \[\begin{align*} &\mathbb P(d\in X_h(b),\ d\notin X_h(b-1),\ d\notin\widetilde N_h \mid\mathcal H_b)\\ &\quad=\mathbb E\bigl[\mathbf 1_{\{d\in X_h(b)\}}\mathbf 1_{\{d\notin X_h(b-1)\}} p_{b-1}\mid\mathcal H_b\bigr] =\mathbf 1_{\{d\in X_h(b)\}}p_{b-1}^{2}. \tag{26}\end{align*}\] More generally, the ordinary and hybrid outputs are independent with the same law conditional on the pre-step transcript. This assertion is for one endpoint at a time. The same mask $T$ is reused at all endpoints, and no joint independence of the different hybrid experiments is asserted or needed.

The hybrid also has a deterministic containment property: \[ Q_h\bigl(F_{h-1}(b-2)+K_{h,b}\bigr)\subseteq\widetilde N_h. \tag{27}\] To prove it, induct over $j<h$. If $\widetilde A_{j-1}\supseteq F_{j-1}(b-2)$, monotonicity gives \[\widetilde N_j =Q_{j,b-1}(\widetilde A_{j-1}) \supseteq Q_{j,b-2}(F_{j-1}(b-2))=X_j(b-2).\] The retained guards in (25) include exactly $C_j\cap X_j(b-1)$, which are the guards used to form $F_j(b-2)$. Hence $\widetilde A_j\supseteq F_j(b-2)$. The hybrid additions also include every $T$-positive in $G_j\cap(X_j(b)\setminus X_j(b-1))$. Extensivity preserves the analogous test additions from earlier groups. Starting with $F_0(b-1)\supseteq F_0(b-2)$, the induction therefore proves \[\widetilde A_{h-1} \supseteq\mathop{\mathrm{cl}}\bigl(F_{h-1}(b-2)+K_{h,b}\bigr).\] The focal map $Q_{h,b-1}=Q_h$ is enabled, so another application of monotonicity proves (27). This is an inclusion for every completed assignment of the bits; it does not condition on the not-yet-exposed flat $F_{h-1}(b-2)$.

An ordinary exit at this step means that $d$ has birth $b$. If it also exits the hybrid, (27) gives its safety exclusion. Thus (26) implies \[ \begin{split} &\mathbb P\bigl(b_h(d)=b,\quad d\notin Q_h(F_{h-1}(b-2)+K_{h,b})\mid H,D\bigr)\\ &\hspace{25mm}\ge \mathbb E\bigl[\mathbf 1_{\{d\in X_h(b)\}}p_{b-1}^{2}\mid H,D\bigr] \qquad(a_h+2\le b\le0). \end{split} \tag{28}\] These bounds may be summed by linearity. For a fixed label the actual birth events at distinct endpoints are disjoint.

Lemma 11 (Safe sampled labels). For every listed group $h$, \[ \mathbb E[\sigma_h\mid H,D] \ge\frac{\eta}{4}|D_h\cap Y|-\frac{|D_h|}{\kappa}. \tag{29}\]

Proof. Apply Lemma 10 to each $d\in D_h\cap Y$. By Lemma 6, the only birth excluded from the range $a_h+2\le b\le0$ is the baseline birth $a_h$; a birth at $a_h+1$ is impossible. Since $p^2\le p$, the total discarded contribution is at most \[\sum_{d\in D_h\cap Y}\mathbb P(b_h(d)=a_h\mid H,D) =|D_h\cap Y\cap Q_h(L)| \le\mathop{\mathrm{r}}(Q_h(L))\le\frac{|D_h|}{\kappa}.\] Here $Y$ is independent in the matroid, and the last inequality is the generator bound of Lemma 8. Summing (28) over labels and valid birth times therefore gives a pre-parity expected safe count at least \[\frac{\eta}{2}|D_h\cap Y|-\frac{|D_h|}{\kappa}.\] The independent fair parity keeps each such label with probability $1/2$. Consequently the stronger lower bound $\eta|D_h\cap Y|/4-|D_h|/(2\kappa)$ holds, which implies (29). ◻

From safe samples to unobserved rank

We continue with the fixed matroid and hidden weight vector, suppressing them in all conditional expectations. The next step turns the safe sample estimate into rank available on labels outside the revealed mask. The paths themselves depend on that mask, so the argument needs a uniform bound on the sets that the paths can leave unspanned.

Write $O=D\cup C$. For a listed group $h$, let \[\mathcal B_h=\{b\in\mathbb Z:a_h+2\le b\le0, \ b\equiv\varepsilon\pmod 2\}, \qquad P_{h,b}=G_h\cap\bigl(X_h(b)\setminus X_h(b-1)\bigr) \quad(b\in\mathcal B_h).\] Put $P_{h,b}=\varnothing$ for other endpoints of the chosen parity, and define the nominal rank statistic \[ z_h=\sum_{b\in\mathcal B_h} \mathop{\mathrm{r}}\bigl(P_{h,b}\setminus O\mid X_h(b-2)\cup K_{h,b}\bigr). \tag{30}\] This statistic measures rank before thinning by the focal mask $T_h$ and before replacing $X_h$ by the final path $\widehat F$. The result needed for the final accounting is the following estimate.

Lemma 12 (Sample-to-rank transfer). Fix $H$. For a true group $U_i$, define $z_i=z_h$ and $\sigma_i=\sigma_h$ if the group is listed with index $h$, and set both quantities to zero if it is unlisted. If $n_i\ge\kappa$, then \[ \mathbb E[z_i\mid H] \ge\frac{\gamma|Y_i|-2^{-23}n_i}{\kappa}, \qquad \gamma=\frac\eta{16}=2^{-16}. \tag{31}\]

We first relate $z_h$ to the safe sampled count $\sigma_h$. Choose enough unsacrificed labels to witness the rank in each summand of (30). A safe sample spanned by these witnesses over its summand’s base can be charged to their rank by the density bound. Every other safe sample belongs to a residual set contained in the revealed mask. The main task will be to bound this residual uniformly over the masks that determine it.

For each summand choose a basis extension $Z_b\subseteq P_{h,b}\setminus O$ over $X_h(b-2)\cup K_{h,b}$. Thus \[ \sum_b|Z_b|=z_h, \qquad P_{h,b}\setminus O \subseteq\mathop{\mathrm{cl}}\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr). \tag{32}\] The sets $Z_b$ are disjoint, since the birth sets $P_{h,b}$ are disjoint. We may choose them by a fixed label order. Set \[ \mathcal R_h= \bigcup_{b\in\mathcal B_h} \left(P_{h,b}\setminus \mathop{\mathrm{cl}}\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr)\right). \tag{33}\] By (32), $\mathcal R_h\subseteq O$.

There is a deterministic comparison with the safe count from Section 4: \[ \sigma_h\le\kappa z_h+|\mathcal R_h|. \tag{34}\] Indeed, fix $b\in\mathcal B_h$ and put $Q'_b=Q_h(F_{h-1}(b-2)\cup K_{h,b})$. Since $b-2\ge a_h$, monotonicity of the density map gives \[X_h(b-2)=Q_h(F_{h-1}(b-2))\subseteq Q'_b, \qquad K_{h,b}\subseteq Q'_b.\] A safe sample at $b$ outside $\mathcal R_h$ belongs to $D_h\cap(\mathop{\mathrm{cl}}(Q'_b\cup Z_b)\setminus Q'_b)$. The residual density inequality (10) bounds the number of these samples by $\kappa\mathop{\mathrm{r}}(Z_b\mid Q'_b)\le\kappa|Z_b|$. Summing proves (34).

Counting marked pivots

The selected set $\mathcal R_h$ depends on the focal group’s mask. We control it by constructing, before those bits are revealed, a small family containing every possible such residual with $z_h\le |G_h|/\kappa$. The following combinatorial lemma supplies a bound that does not depend on the number of times at which a path can change.

Lemma 13 (Marked pivots). Let $M$ be any finite matroid, and let $V$ be a set of $n$ nonloops. Let $s\ge0$ be an integer. Fix an ordered sequence of labeled old occurrences, each with a mark in $\{0,1\}$, whose labels span $E$. Also fix at most $s$ labeled movable occurrences. Repetitions of labels are allowed in both sequences. Insert the movable occurrences into the old sequence in any order and positions, and give each movable occurrence either mark. For $f\in V$, its pivot is the first occurrence after whose insertion $f$ is spanned; record that occurrence’s mark. The number of resulting vectors of $n$ marks is at most \[ 4^s\sum_{\ell=0}^{s}\binom n\ell, \tag{35}\] where $\binom n\ell=0$ for $\ell>n$.

Proof. We first bound the possible bases retained by greedy processing of an interleaving. Remove every old occurrence whose label is spanned by its old predecessors. This leaves the span after every old prefix unchanged. Such an occurrence remains redundant after any insertions, so its removal preserves all pivot marks. The surviving old labels form an ordered basis $b_1,\ldots,b_r$ of $M$. Write $B_j=\{b_1,\ldots,b_j\}$, and let $A$ denote all specified movable occurrences, with rank interpreted through their labels.

For each old position define \[\Delta_j= \mathop{\mathrm{r}}(A\mid B_{j-1})-\mathop{\mathrm{r}}(A\mid B_j) =1-\mathop{\mathrm{r}}(\{b_j\}\mid B_{j-1}\cup A)\in\{0,1\}.\] These numbers are fixed before any insertions are chosen, and $\sum_j\Delta_j=\mathop{\mathrm{r}}(A)\le s$. If $\Delta_j=0$, then $b_j$ increases rank even after all of $A$ has been adjoined to $B_{j-1}$, and hence it increases rank in every interleaving. Thus greedy processing of an interleaving can omit old occurrences only at the at most $s$ positions with $\Delta_j=1$. There are at most $2^s$ choices of omitted old occurrences and at most $2^s$ choices of retained movable occurrences. Consequently the retained greedy basis, regarded as a collection of occurrences, has at most $4^s$ possibilities.

Fix one such basis $J$. We next identify each pivot from a spanning subset of $J$, independently of how the other occurrences were inserted. For every $f\in V$ there is a unique minimal subset $S_f\subseteq J$ that spans $f$. To verify uniqueness using only matroid rank, suppose $S,T\subseteq J$ both span $f$. Submodularity applied to $S\cup\{f\}$ and $T\cup\{f\}$ gives \[|S|+|T|\ge |S\cup T|+\mathop{\mathrm{r}}((S\cap T)\cup\{f\}),\] so $S\cap T$ also spans $f$. Intersecting the finitely many spanning subsets proves the assertion. The support $S_f$ is nonempty because $f$ is a nonloop. At every prefix, the retained greedy occurrences span exactly the same flat as the full prefix. It follows that the pivot of $f$ is the last occurrence of $S_f$ in the interleaving.

It remains to count the possible marks of these last support members. For this fixed $J$, assign its retained old occurrences, in their prescribed order, fixed absolute scores $2^{s+1},2^{2(s+1)},\ldots$, with positive sign for mark $1$ and negative sign for mark $0$. There are at least $s$ unused integer powers of $2$ before the first old score and between successive old scores; reserve another $s$ powers after the last. Every order of the retained movable occurrences can therefore be represented by assigning them distinct unused powers in the appropriate gaps, in that order, with either sign according to their marks. If no old occurrence is retained, simply use distinct powers for the movable occurrences. Every absolute score then exceeds the sum of all preceding absolute scores.

Let the signed scores of the retained movable occurrences be real variables, at most $s$ in number. For each $f$, the sum of scores over $S_f$ is an affine function of these variables, whose constant term is the sum of the fixed old scores in $S_f$. At the representations just constructed this sum is nonzero, and its sign is precisely the mark of the last member of $S_f$. Thus every pivot-mark vector for $J$ is a strict sign pattern of $n$ affine functions in dimension at most $s$.

The remaining estimate is the classical region bound for affine hyperplane arrangements; see Schläfli (Schläfli 1901, sec. 16, pp. 39–40). We include the recurrence and its degenerate cases: $n$ affine functions in dimension $d$ have at most $\sum_{\ell=0}^{d}\binom n\ell$ strict sign patterns. A prescribed strict pattern defines an open convex region. Adding a proper affine hyperplane splits at most as many existing regions as there are regions of the induced arrangement on that hyperplane, giving the recurrence $N(n,d)\le N(n-1,d)+N(n-1,d-1)$, with $N(0,d)=1$ and $N(n,0)\le1$. A nonzero constant has a fixed sign; an identically zero function yields no all-strict patterns. Coincident hyperplanes and degenerate restrictions cannot increase the recurrence bound. Induction gives the displayed binomial sum. Applying this to each of the at most $4^s$ bases proves (35). In particular, all movable orders, positions, and marks have already been counted, with no additional permutation or timeline factor. ◻

Encoding residual sets

We now apply the counting bound twice to describe the residuals. The first marked sequence tests whether a label has a valid nominal birth of the chosen parity. Among labels passing that test, the second tests whether, in that layer, the label remains outside the span of the preceding flat, competing test labels, and rank witnesses. Their intersection is exactly the residual set. Counting both tests uniformly before exposing the focal group’s bits is what permits a later union bound despite the dependence of the actual residual on those bits.

Lemma 14 (A uniform family of residuals). Fix $H$ and a true group $U_i$ of size $n=n_i\ge\kappa$. Condition also on the parity and on the $D,C,T$ bits outside $U_i$, but do not condition on their bits in $U_i$ or on whether $U_i$ is listed. There is a deterministic family $\mathfrak R_i\subseteq 2^{U_i}$ with \[ |\mathfrak R_i|\le \exp\left(\frac{1000\log\kappa}{\kappa}\,n\right) \tag{36}\] such that, whenever this group is listed and $z_h\le n/\kappa$, every residual (33) obtained from witnesses (32) belongs to $\mathfrak R_i$.

Proof. If $U_i$ is listed, its index must be one plus the number of listed lower-weight groups. Denote this now-fixed index by $h$, whether or not the focal group is actually listed. The lower-group paths, $F(k):=F_{h-1}(k)$, and all $K_{h,b}$ are fixed by the conditioning. No $D,C,T$ bit on $U_i$ enters this incoming path or these competition sets. Write $a=a_h$ and $q=\lfloor n/\kappa\rfloor$.

On any actual listed outcome, Lemma 8 supplies a set $J_h\subseteq U_i$ of at most $q$ density generators and an insertion time $\tau(g)$ for each $g\in J_h$ such that \[ X_h(k)=\mathop{\mathrm{cl}}\bigl(F(k)\cup\{g\in J_h:\tau(g)\le k\}\bigr). \tag{37}\] All insertion times can be taken between $a$ and $0$. When $z_h\le n/\kappa$, the witness union $Z=\bigcup_b Z_b$ has at most $q$ labels. We allow every choice of these two subsets of $U_i$, then use two marked sequences to encode the residual. An element chosen for both subsets is treated as two distinct occurrences, one for each role.

For the first sequence, advance through integer times from $a-2$ to $1$. At time $k$ take as old occurrences a fixed label-ordered listing of $F(k)$; mark all occurrences in this block by $1$ exactly when $k\in\mathcal B_h$. These old slots, including their labels, order, and marks, are fixed by the conditioning and span $E$, since $F(0)=E$. For the actual path, insert each $g\in J_h$ at its time $\tau(g)$, after that time’s old block, with the same mark as the block. After processing time $k$, the generated flat is exactly $X_h(k)$ by (37). Hence the set receiving mark $1$ among the tested labels $U_i$ is precisely \[ \bigcup_{b\in\mathcal B_h} P_{h,b}. \tag{38}\]

The second sequence runs through layers of the chosen parity. Choose the unique $b_0\in\{a-2,a-1\}$ with $b_0\equiv\varepsilon\pmod2$, and then take successive endpoints $b_0+2,b_0+4,\ldots,b_1$, where $b_1\in\{0,1\}$ has the chosen parity. The initial span is $L=X_h(b_0)$. For each layer $(b-2,b]$ use the following two phases:

Insert a fixed listing of $K_{h,b}$ as old occurrences with mark $0$, followed by the movable witnesses $Z_b$, also with mark $0$. Here $Z_b=\varnothing$ if $b\notin\mathcal B_h$.
Insert a fixed listing of $F(b)$ as old occurrences with mark $1$, followed by the movable density generators whose insertion times satisfy $b-2<\tau(g)\le b$, also with mark $1$.

Again the old slots, their order, and their marks are fixed; their labels span $E$ by the final endpoint. Only the density and witness occurrences move when the focal mask changes.

The two phases are designed to give the following sequence of spans: \[X_h(b-2) \xrightarrow[\text{mark }0]{\text{phase (i)}} \mathop{\mathrm{cl}}\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr) \xrightarrow[\text{mark }1]{\text{phase (ii)}} X_h(b).\] We verify these identities before interpreting the pivot marks. Suppose the generated flat at the preceding endpoint is $X_h(b-2)$. At the end of phase (i) it is exactly \[ \mathop{\mathrm{cl}}\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr). \tag{39}\] The inclusions $K_{h,b}\subseteq F(b)$ and $Z_b\subseteq X_h(b)$, together with (37), show that the flat at the end of phase (ii) is exactly $X_h(b)$. This proves the endpoint assertion by induction from $b_0$. Density generators originally inserted at $b-1$ have been postponed to phase (ii). They affect the intermediate span, but the endpoints and the explicit span (39) remain exact.

Now restrict attention to a label passing the first test, with valid birth $b$. It is outside $X_h(b-1)$ and hence outside $X_h(b-2)$, so its second-sequence pivot occurs in this layer. Its second mark is $1$ exactly when it is not spanned at the end of phase (i). By (39), this is exactly its membership in $\mathcal R_h$. Thus the residual is the intersection of the two sets of labels receiving mark $1$. Phase (ii) can also span labels born at $b-1$, which explains why the first test is needed: the second mark alone need not describe a valid birth of the chosen parity.

We now define $\mathfrak R_i$ without using the focal bits: for every pair of subsets $J,Z\subseteq U_i$ of size at most $q$, include every intersection of two marked-pivot sets obtained from the fixed old sequences just described, allowing arbitrary placements, orders, and marks of the specified movable occurrences. The first sequence uses only the $J$ occurrences; the second uses both roles. This definition may include intersections that do not arise from valid paths or witnesses, which only increases the family. The preceding construction shows that it includes every required actual residual.

Let $S_d(n)=\sum_{\ell=0}^{d}\binom n\ell$. There are at most $S_q(n)^2$ subset choices. Each sequence has at most $2q$ movable occurrences, so Lemma 13 gives \[ |\mathfrak R_i| \le S_q(n)^2\bigl(4^{2q}S_{2q}(n)\bigr)^2. \tag{40}\] This estimate includes all ways of assigning labels to times or layers. To bound it with the floors intact, for $0<\alpha\le1/2$ note that \[\alpha^{\alpha n}S_{\lfloor\alpha n\rfloor}(n) \le\sum_{\ell=0}^{\lfloor\alpha n\rfloor} \binom n\ell\alpha^\ell \le(1+\alpha)^n\le e^{\alpha n}.\] Use $q\le n/\kappa$ and $2q\le\lfloor2n/\kappa\rfloor$, with $\alpha=1/\kappa$ and $\alpha=2/\kappa$, respectively, in (40). This yields \[\log|\mathfrak R_i| \le\frac n\kappa \bigl(6\log\kappa+6+4\log2\bigr) \le\frac{1000\log\kappa}{\kappa}\,n,\] as claimed. All labels tested here are nonloops by the initial candidate filter, and the argument uses no representability property of the matroid. ◻

Completing the sample-to-rank estimate

The residual family is fixed before the focal mask is exposed. We can therefore bound the chance that any large member lies entirely in $O$, even though the actual residual is chosen using that mask.

Proof of Lemma 12. Put $n=n_i$. On the unlisted branch $D\cap U_i$ is empty, so Lemma 11, with both sides extended by zero on that branch, can be averaged over $D$. Since each label belongs to $D$ with probability $1/4$, it gives \[ \mathbb E[\sigma_i\mid H] \ge\frac\eta{16}|Y_i|-\frac{n}{4\kappa} \ge\gamma|Y_i|-\frac n\kappa. \tag{41}\]

Use the conditioning in Lemma 14. Within $U_i$, the events $\{e\in O\}$ remain independent across labels, each with probability \[p_O=1-(1-1/4)(1-t)=\frac14+\frac34t\le\frac12.\] Thus, for each fixed $R_0\in\mathfrak R_i$, $\mathbb P(R_0\subseteq O)\le2^{-|R_0|}$ under this conditioning. Let $\delta=2^{-26}$ and let $\mathcal E_i$ be the event that some $R_0\in\mathfrak R_i$ satisfies $R_0\subseteq O$ and $|R_0|>\delta n$. The union bound, without conditioning on listing, gives \[\begin{align*} \mathbb P(\mathcal E_i\mid H,\varepsilon, \text{masks outside }U_i) &\le\exp\left(\frac{1000\log\kappa}{\kappa}n -\delta n\log2\right)\\ &=2^{-(2^{-26}-100000\,2^{-100})n} \le2^{-2^{-27}n} \le2^{-2^{73}}<2^{-26}. \tag{42}\end{align*}\] Here we used $\kappa=2^{100}$ and $n\ge\kappa$; in particular the bound already holds at the smallest analyzed group size.

Define an error variable $e_i$ as follows. On a listed outcome with $z_i\le n/\kappa$, choose the witnesses in (32) and set $e_i=|\mathcal R_h|$. Set $e_i=0$ on all other outcomes. In its nonzero branch, $\mathcal R_h\in\mathfrak R_i$ and $\mathcal R_h\subseteq O$, so \[e_i\le\delta n+n\mathbf 1_{\{\mathcal E_i\}}, \qquad \mathbb E[e_i\mid H]\le2\delta n=2^{-25}n.\] The latter bound follows first under the conditioning of (42), then by averaging that conditioning away. No independence is asserted for the selected residual itself.

In every outcome, \[\sigma_i\le\kappa z_i+e_i.\] For listed outcomes with $z_i\le n/\kappa$ this is (34); for listed outcomes with $z_i>n/\kappa$ it follows from $\sigma_i\le n<\kappa z_i$; for unlisted outcomes both statistics vanish. Taking expectations and using (41) gives \[\kappa\mathbb E[z_i\mid H] \ge\gamma|Y_i|-(\kappa^{-1}+2^{-25})n \ge\gamma|Y_i|-2^{-23}n,\] which proves (31). ◻

Rank and payoff for every arrival order

We now pass from the nominal rank guarantee of Lemma 12 to the actual greedy reward. A rank statistic on the final layers will give a lower bound for every arrival order with all coins fixed. We then compare final and nominal layers using one generator budget over the entire auxiliary timeline. Only after these deterministic comparisons do we average over the independent test thinning and the other masks.

A simultaneous rank lower bound

Fix all weights and coins. For a listed group $h$, write $S_{h,b}=P_{h,b}\setminus O$, and define the order-independent statistic \[ \lambda_h=\sum_b\mathop{\mathrm{r}}\bigl(T_h\cap S_{h,b}\mid \widehat F(b-2)+K_{h,b}\bigr). \tag{43}\] Sums over $b$ use the chosen parity; terms outside the finite nontrivial range are zero. Each summand measures the rank left among tested, unobserved labels of group $h$ after contracting the preceding final flat and all lower-weight test competitors. It depends on the coins but not on the arrival order. Let $N_{\ge h}(\pi)$ be the number of accepted labels whose rounded weight is at least that of $G_h$.

Lemma 15 (Order-uniform rank bound). For each realization of all coins and every permutation $\pi$, \[ N_{\ge h}(\pi)\ge\lambda_h. \tag{44}\]

Proof. At endpoint $b$, let $F=\widehat F(b-2)$ and let $E_b$ be the entire eligible set of that layer. Whatever the arrival order or the interleaving with other layers, its final greedy set $B_b$ is a basis of $E_b$ over $F$. Partition $B_b=L_b\sqcup H_b$ into selected labels of strictly lower weight than $G_h$ and the remaining labels. Independence and spanning give \[|H_b|=\mathop{\mathrm{r}}(H_b\mid F+L_b)=\mathop{\mathrm{r}}(E_b\mid F+L_b).\] Every element of $T_h\cap S_{h,b}$ outside $F$ is eligible. Those in $F$ contribute no rank. Also $L_b\subseteq K_{h,b}$, because each lower-weight accepted label is test-positive and has nominal birth $b$ in a lower listed group. Thus \[|H_b|\ge\mathop{\mathrm{r}}(T_h\cap S_{h,b}\mid F+L_b) \ge\mathop{\mathrm{r}}(T_h\cap S_{h,b}\mid F+K_{h,b}).\] Sum over the layers to prove (44). Including unselected or sacrificed labels in $K_{h,b}$ only weakens this bound. ◻

One budget for later path expansions

Lemma 16 (Telescoping rank cost). For each listed group $h$, the nominal statistic $z_h$ satisfies \[ \sum_b\mathop{\mathrm{r}}(S_{h,b}\mid\widehat F(b-2)+K_{h,b})\ge z_h-c_h, \qquad c_h=|C_h|+\sum_{j>h}\bigl(|C_j|+|D_j|/\kappa\bigr). \tag{45}\]

Proof. Choose the generator sets of Lemma 8 and put \[J=C_h\cup\bigcup_{j>h}(C_j\cup J_j).\] This single set satisfies $|J|\le c_h$ and, for every integer $k$, \[ X_h(k)\subseteq\widehat F(k)\subseteq\mathop{\mathrm{cl}}(X_h(k)+J). \tag{46}\] Indeed the first group’s guards are contained in $C_h$; at each later group, its whole density path uses portions of $J_j$, and its guards are contained in $C_j$. Induction over groups proves the second inclusion for all times at once. The set $J$ may depend on the realized masks.

At endpoint $b$, abbreviate $A=X_h(b-2)+K_{h,b}$ and $S'=S_{h,b}$. The conditioning set in the left side of (45) lies between $A$ and $\mathop{\mathrm{cl}}(A+J)$. The resulting rank loss is at most \[\begin{align*} \mathop{\mathrm{r}}(S'\mid A)-\mathop{\mathrm{r}}(S'\mid A+J) &=\mathop{\mathrm{r}}(J\mid A)-\mathop{\mathrm{r}}(J\mid A+S')\\ &\le\mathop{\mathrm{r}}(J\mid X_h(b-2))-\mathop{\mathrm{r}}(J\mid X_h(b)). \tag{47}\end{align*}\] The inequality follows from two applications of decreasing conditional rank along the nested sets \[X_h(b-2)\subseteq A\subseteq A+S'\subseteq X_h(b):\] the last inclusion follows from $K_{h,b}\subseteq F_{h-1}(b)$ and $P_{h,b}\subseteq X_h(b)$. Specifically, $\mathop{\mathrm{r}}(J\mid A)\le\mathop{\mathrm{r}}(J\mid X_h(b-2))$ and $\mathop{\mathrm{r}}(J\mid A+S')\ge\mathop{\mathrm{r}}(J\mid X_h(b))$. Summing the right side of (47) over the chosen parity telescopes to at most $\mathop{\mathrm{r}}(J)\le |J|$. Missing endpoints may be added, since all differences are nonnegative. This proves (45); neither independence of $J$ nor a separate budget for each layer is required. ◻

Independent thinning and group estimates

The two preceding lemmas apply simultaneously to every realization and arrival order. We now average the focal group’s test bits, which played no role in constructing its paths or lower-weight competition sets.

Lemma 17 (Independent test thinning). For a listed group $h$, let $\mathcal F_{-h}$ be generated by $H,D,C$, the parity $\varepsilon$, and all test-mask memberships outside $G_h$. Then \[ \mathbb E[\lambda_h\mid\mathcal F_{-h}] \ge t\sum_b\mathop{\mathrm{r}}(S_{h,b}\mid\widehat F(b-2)+K_{h,b}) \ge t(z_h-c_h). \tag{48}\]

Proof. The group $G_h$ is determined by $H,D$ and the fixed weights. All paths depend on $H,D,C$ and not on $T$. The birth sets $P_{h,b}$ also use the parity; $O=D\cup C$ omits $T$, and $K_{h,b}$ uses only lower groups’ test bits. Thus these sets, as well as $z_h$ and $c_h$, are $\mathcal F_{-h}$-measurable, while the bits of $T_h$ remain independent Bernoulli bits of rate $t$.

Conditional on $\mathcal F_{-h}$, choose a fixed independent witness for each unthinned rank in (48). Its intersection with $T_h$ is still independent over the same base and has expected size $t$ times its size. Linearity proves the first inequality, and Lemma 16 proves the second. No selected order is conditioned upon. ◻

Return to true weight indices. For a listed true group $U_i=G_h$, let $\lambda_i=\lambda_h$ and $c_i=c_h$; if it is unlisted, set both to zero, as with $z_i$. Conditional on $H$, dominate the cost pointwise by counts on all true groups, listed or not: \[c_i\le |C\cap U_i|+ \sum_{\ell>i}\left(|C\cap U_\ell|+\frac{|D\cap U_\ell|}{\kappa}\right).\] Only then take expectations. The mask probabilities are unchanged under this conditioning, so \[ \mathbb E[c_i\mid H]\le t n_i+(t+1/\kappa)\sum_{\ell>i}n_\ell. \tag{49}\] The exact density-mask contribution would be $1/(4\kappa)$; the larger coefficient is convenient. Lemmas 12 and 17 now imply, for every true group of size $n_i\ge\kappa$, \[ \mathbb E[\lambda_i\mid H]\ge\frac t\kappa \left(\gamma|Y_i|-(2^{-23}+t\kappa)n_i -(1+t\kappa)\sum_{\ell>i}n_\ell\right). \tag{50}\] Although the different $\lambda_i$ may depend on one another’s test bits, each separate thinning calculation is valid. Their expectations can be summed without asserting independence.

The weighted sum and the final constant

Let $A_{\mathrm{main}}(R,\pi)$ be the main rule’s accepted set and let $\mathcal A(H)=\{i:n_i\ge\kappa\}$ be the analyzed true groups. For a true weight index $i$, let $N_i(\pi)$ count accepts of weight at least $B^i$. Lemma 15, with $\lambda_i=0$ on unlisted groups, gives $\lambda_i\le N_i(\pi)$ simultaneously for every $\pi$. Each accepted weight $B^\ell$ contributes at most $\sum_{i\le\ell}B^i=B^\ell B/(B-1)<2B^\ell$ to the cumulative weighted counts. Hence the pointwise inequality is \[ \min_\pi u(A_{\mathrm{main}}(R,\pi)) \ge\frac12\sum_{i\in\mathcal A(H)} B^i\lambda_i. \tag{51}\] The order has been minimized before any expectation is taken.

Multiply (50) by $B^i$ and sum over analyzed groups. The higher-weight cost is bounded using \[\sum_{i\in\mathcal A(H)}B^i\sum_{\ell>i}n_\ell \le\sum_\ell n_\ell\sum_{i<\ell}B^i =\frac1{B-1}\sum_\ell B^\ell n_\ell.\] With the constants in (4), \[ 2^{-23}+t\kappa+\frac{1+t\kappa}{B-1}<2^{-21}. \tag{52}\] For example $t\kappa=2^{-40}$ and the fractional term is less than $2^{-30}$; these bounds already give the displayed strict inequality. Combining with (51) yields \[ \mathbb E\left[\min_\pi u(A_{\mathrm{main}}(R,\pi))\,\middle|\,H\right] \ge\frac{t}{2\kappa}\left( \gamma\sum_{i\in\mathcal A(H)}B^i|Y_i|-2^{-21}u(U)\right). \tag{53}\]

Suppose $W>0$, so $m_*>0$. Ignoring the smaller true groups loses at most \[ \sum_{i\notin\mathcal A(H)}B^i|Y_i| \le\kappa\sum_{B^i\le m_*}B^i<2\kappa m_*. \tag{54}\] If $m_*\le W/(8\kappa)$, Lemma 4 and (54) give \[\mathbb E_H\sum_{i\in\mathcal A(H)}B^i|Y_i|\ge W/4, \qquad \mathbb E_H u(U)\le W.\] Since $\gamma=2^{-16}$, we have $\gamma/4-2^{-21}=7\cdot2^{-21}\ge\gamma/8$. Therefore \[ \mathbb E\big[\min_\pi u(A_{\mathrm{main}}(R,\pi))\big] \ge \frac{t\gamma}{16\kappa}W. \tag{55}\] If instead $m_*>W/(8\kappa)$, the maximum branch gives more than $W/(32\kappa)$ by (6).

Proof of Proposition 2 and Theorem 1. Choose the two branches with equal probability. In the first case above, the main branch contributes at least $t\gamma W/(32\kappa)$ after mixing. In the second case, the maximum branch contributes more than $W/(64\kappa)$, which is larger than the same target. The minimum over orders is taken separately for every complete seed, including the branch; the fair mixture is therefore valid against branch-dependent orders. True accepted weights dominate their rounded weights. By (5), the resulting fixed-vector reward fraction is \[\frac{t\gamma}{32\kappa B} =2^{-140-16-5-100-32}=2^{-293}.\] When $W=0$, the benchmark is zero and the conclusion is immediate. Feasibility and measurability follow from Lemma 7 and the analogous immediate properties of the maximum branch. This proves Proposition 2. The revealed mask is selected from the initial seed, independently of the weights, so Lemma 3 proves Theorem 1, with slack in its announced constant.

The construction covers empty ground sets, loops, rank zero, ties, and zero values as specified above. Each realized weight vector is finite, even when the distributions have unbounded support. Only the expected optimum needs to be finite; loop values, which can never be accepted, need no separate moment condition. ◻

An order-oblivious secretary consequence

The fixed-vector guarantee also gives a secretary rule with a random observation prefix and an adversarial suffix. This follows the order-oblivious prefix/suffix form introduced by Azar, Kleinberg, and Weinberg (Azar et al. 2014, Definition 1, Section 3). Their definition permits a possibly random rejected prefix and an adversarially ordered suffix; it does not explicitly specify visibility of the rule’s entire seed. We state that information pattern separately here.

The mechanism is the sacrificed observation mask of Proposition 2. Within either branch, a binomial prefix length chosen independently of the permutation reproduces that branch’s product-mask law. After observing that set, the rule uses predrawn random coordinates to reconstruct the remaining source coins from their conditional law. The expected minimum over all orders then accommodates any rearrangement of the suffix.

Corollary 18 (Order-oblivious selection with full-seed visibility). For each known finite labeled matroid $M=(E,\mathcal I)$, there is one measurable randomized online rule $\mathcal S_M$ with the following property. Fix any vector $w\in[0,\infty)^E$ of finite nonnegative weights before all rule and arrival randomness. Without knowing $w$, the rule draws its complete initial seed $Q$, independently of a uniformly random permutation $\sigma$ of $E$, and fixes a possibly random prefix length $K$ before any arrival. It observes the first $K$ label–weight pairs of $\sigma$ in order and rejects those labels.

After this ordered prefix is observed and before any suffix arrival, an adversary may know $M$, the entire fixed vector $w$, the ordered prefix, and the complete seed $Q$, including $K$, the branch choice, and unused coins. It may choose any measurable permutation $\tau$ of the remaining labels as a function of this information. The rule is not told the future suffix order and decides irrevocably at each suffix arrival while maintaining an independent set. Writing $A_{\mathcal S}$ for its accepted set, for every such adversary, \[ \mathbb E\left[\sum_{e\in A_{\mathcal S}}w_e\right] \ge 2^{-293}\mathop{\mathrm{OPT}}_M(w). \tag{56}\] The expectation is over the rule seed and random prefix, and over any adversary randomization. The adversary cannot alter the random-prefix law or choose the weights after observing the seed or prefix.

Proof. Let $R$ denote the complete source seed of Proposition 2, including the independent fair branch choice $J$. In the maximum branch the sacrificed mask has independent membership rate $p_{\mathrm{max}}=1/2$. In the main branch it is $B_0=H\cup D\cup C$, so its rate is \[p_{\mathrm{main}} =1-(1-1/2)(1-1/4)(1-t) =\frac58+3\,2^{-143}, \qquad t=2^{-140}.\] The test mask $T$ is not sacrificed. Both rates are independent of $w$ and lie strictly between zero and one.

Let $n=|E|$. Draw $J$ and then $K\mid J\sim\operatorname{Bin}(n,p_J)$ as part of $Q$ before arrivals, independently of $\sigma$. Write $P=\{\sigma_1,\ldots,\sigma_K\}$ for the prefix set. For each fixed $p\subseteq E$, \[ \mathbb P(P=p\mid J) =\frac{\mathbb P(K=|p|\mid J)}{\binom n{|p|}} =p_J^{|p|}(1-p_J)^{n-|p|}. \tag{57}\] Thus $P\mid J$ has exactly the product law of the source sacrificed mask. This statement averages over $K$: conditional on $K$, the set is uniform of that fixed size, and no product-law assertion is made conditional on the complete secretary seed.

After the prefix, reconstruct $R$ from its source conditional law given $J$ and $B_0=P$. In the maximum branch set its fair mask equal to $P$. In the main branch set $(H_e,D_e,C_e)=(0,0,0)$ for $e\notin P$; for each $e\in P$, independently use the original product law of this triple conditioned on being nonzero. Each of its seven probabilities is the corresponding original triple probability divided by $p_{\mathrm{main}}$. Keep the source laws of $T$, parity, unused branch coins, and all other coins. All conditioning events have positive probability. Multiplying this conditional kernel by (57) recovers exactly the source joint law of the branch and complete seed $R$, with $B_0(R)=P$.

This reconstruction requires no concealed later randomness. The initial seed $Q$ predraws independent uniform coordinates for the finite conditional kernels and the remaining source coins. After the prefix, evaluate the kernels by fixed interval partitions using only its label set $P$, not its weights. Hence the derived $R$ is a function of $(Q,P)$ and is known to the adversary. The extra information in $Q$ may reveal more than $R$; the pointwise comparison below allows this.

Initialize the hidden-weight rule using $R$ and the observed vector $w|_P$. Virtually feed it the prefix in its observed order. Every prefix label is forced to be rejected, and this replay includes any internal state changes on rejected arrivals. Then feed it each suffix label and weight as that label arrives. No unseen suffix weight or future suffix order is supplied. For the concatenated permutation $\pi=(\sigma_1,\ldots,\sigma_K,\tau)$, induction on arrivals gives exactly the accepted set $A(w,R,\pi)$ of the hidden rule. For every realization, including when $\tau$ depends on all of $Q$ and the ordered prefix, \[\sum_{e\in A_{\mathcal S}}w_e =\sum_{e\in A(w,R,\pi)}w_e \ge \min_{\pi'}\sum_{e\in A(w,R,\pi')}w_e.\] The marginal law of $R$ is the source law and $w$ was fixed before the randomness. Averaging this pointwise inequality and applying Proposition 2 proves (56) without any additional loss.

Feasibility follows from the hidden rule’s feasibility for every arrival prefix and permutation. For fixed finite $M$, the mask kernels have finite support and their interval-partition realizations are Borel measurable; composition with the measurable source decisions therefore gives a measurable rule. The minimum is over finitely many measurable rewards, and feasibility bounds each reward by the finite $\mathop{\mathrm{OPT}}_M(w)$. The cases $K=0$, $K=n$, empty ground sets, loops, rank zero, ties, and zero weights are covered by the same construction and the source conventions. ◻

The construction uses a known finite labeled matroid and numerical weights, and supplies a finite measurable rule. Its computational cost is not bounded here. Its distinguishing feature is the order guarantee: after the observation prefix, the suffix may depend on the weights and every coin in the rule’s initial seed.

For ordinary uniformly random arrivals, recent results give much larger constants with stronger computational guarantees. Abdi, Banihashem, Hajiaghayi, and Mittal give a polynomial-time $1/64$-competitive ordinal rule for known matroids (Abdi et al. 2026, Corollary 1.4). Their Theorem 6.1 also gives a reduction from single-sample prophet inequalities to the ordinary secretary problem, recording Fu et al.’s attribution of this implication to Wenzheng Li’s 2023 personal communication. Singla (Singla 2026, Theorem 3.1) and Huang (Huang 2026, Theorem 1) give ordinal rules selecting each element of a fixed optimum with probability at least $1/4$ and $1/e$, respectively, even when the matroid is accessed only through independence queries on arrived elements. These results use uniformly random arrivals throughout. Corollary 18 instead applies after arbitrary full-seed adversarial rearrangement of the unobserved suffix, with no additional loss from the fixed-vector guarantee.

Abdi, Hamed, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal. 2026. On the Strong Matroid Secretary Conjecture and Beyond. https://arxiv.org/abs/2609.19118v1.

Azar, Pablo D., Robert Kleinberg, and S. Matthew Weinberg. 2014. “Prophet Inequalities with Limited Information.” Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’14, 1358–77. https://doi.org/10.1137/1.9781611973402.100.

Babaioff, Moshe, Nicole Immorlica, and Robert Kleinberg. 2007. “Matroids, Secretary Problems, and Online Mechanisms.” Proceedings of the Eighteenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’07, 434–43. https://www.microsoft.com/en-us/research/publication/matroids-secretary-problems-and-online-mechanisms/.

Caramanis, Constantine, Paul Dütting, Matthew Faw, et al. 2022. “Single-Sample Prophet Inequalities via Greedy-Ordered Selection.” Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’22, 1298–325. https://doi.org/10.1137/1.9781611977073.54.

Edmonds, Jack. 1965. “Minimum Partition of a Matroid into Independent Subsets.” Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics 69B (1–2): 67–72. https://doi.org/10.6028/jres.069B.004.

Feldman, Moran, Ola Svensson, and Rico Zenklusen. 2015. “A Simple $O(\log\log(\mathrm{rank}))$-Competitive Algorithm for the Matroid Secretary Problem.” Proceedings of the Twenty-Sixth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’15, 1189–201. https://doi.org/10.1137/1.9781611973730.79.

Feldman, Moran, Ola Svensson, and Rico Zenklusen. 2016. “Online Contention Resolution Schemes.” Proceedings of the Twenty-Seventh Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’16, 1014–33. https://doi.org/10.1137/1.9781611974331.ch72.

Feldman, Moran, Ola Svensson, and Rico Zenklusen. 2026. “Nearly Tight Sample Complexity for Matroid Online Contention Resolution.” Proceedings of the 2026 Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’26, 4692–711. https://doi.org/10.1137/1.9781611978971.171.

Fu, Hu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. 2024. “Sample-Based Matroid Prophet Inequalities.” Proceedings of the 25th ACM Conference on Economics and Computation, EC ’24. https://doi.org/10.1145/3670865.3673506.

Huang, Zhiyi. 2026. Settling the Matroid Secretary Problem. https://arxiv.org/abs/2609.30421v1.

Kleinberg, Robert, and S. Matthew Weinberg. 2012. “Matroid Prophet Inequalities.” Proceedings of the 44th Annual ACM Symposium on Theory of Computing, STOC ’12, 123–36. https://doi.org/10.1145/2213977.2213991.

Krengel, Ulrich, and Louis Sucheston. 1977. “Semiamarts and Finite Values.” Bulletin of the American Mathematical Society 83 (4): 745–47. https://doi.org/10.1090/S0002-9904-1977-14378-4.

Lachish, Oded. 2014. “$O(\log\log\mathrm{rank})$ Competitive Ratio for the Matroid Secretary Problem.” Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’14, 326–35. https://doi.org/10.1109/FOCS.2014.42.

Rubinstein, Aviad, Jack Z. Wang, and S. Matthew Weinberg. 2020. “Optimal Single-Choice Prophet Inequalities from Samples.” 11th Innovations in Theoretical Computer Science Conference, Leibniz international proceedings in informatics, vol. 151: 60:1–10. https://doi.org/10.4230/LIPIcs.ITCS.2020.60.

Santiago, Richard, Ivan Sergeev, and Rico Zenklusen. 2025. “Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid.” Mathematical Programming 210: 815–46. https://doi.org/10.1007/s10107-024-02177-x.

Schläfli, L. 1901. “Ueber die Zahl der Teile, in welche die $n$fache Totalität durch eine beliebige Menge $(n-1)$facher linearer Kontinua geteilt wird.” Chap. 16 in Theorie Der Vielfachen Kontinuität, edited by J. H. Graf. Georg & Co. https://doi.org/10.1007/978-3-0348-5118-3_18.

Singla, Sahil. 2026. The Matroid Secretary Conjecture Is True. https://arxiv.org/abs/2609.14555v2.

Soto, José A. 2013. “Matroid Secretary Problem in the Random-Assignment Model.” SIAM Journal on Computing 42 (1): 178–211. https://doi.org/10.1137/110852061.

LEVEL 1 COMPLETE!

You read 12,591 words and 877 formulas. Your math teacher would be proud.
Converted from the LaTeX source. Something look off? The original PDF is the real thing.

Back to game page

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600