1 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
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.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 \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 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
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 7.1 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 [12]. Kleinberg and Weinberg proved the same 1/2 guarantee for arbitrary matroid constraints when the distributions are known [11]. 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 [2]. In the single-choice setting, Rubinstein, Wang, and Weinberg obtained the optimal one-sample reward fraction 1/2 [14]. Caramanis et al. developed greedy-ordered selection and a pointwise sample-pair framework for single-sample guarantees under structured feasibility constraints [4]. 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 [3]. In that problem the weights are fixed and the arrival order is uniformly random. Lachish [13] and Feldman, Svensson, and Zenklusen [6] 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 [6, 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 [17, 10]. 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 [9]. Feldman, Svensson, and Zenklusen subsequently improved the sample dependence on the ground-set size and rank [8]. 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 [7, Section 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 [1, Theorem 1.3]. Their order is fixed independently of the samples, online values, and internal random coins. Theorem 1.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 [5]. Soto used principal partitions and their uniformly dense minors for secretary selection in the random-assignment model [18]; Santiago, Sergeev, and Zenklusen subsequently developed that approach without advance knowledge of the matroid [15]. 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 [6, Section 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.
2 A fixed-vector formulation
Throughout, M=(E,\mathcal I) is a finite labeled matroid. For X\subseteq E, its rank \rk(X) is the maximum size of an independent subset of X, and \cl(X)=\{e\in E:\rk(X\cup\{e\})=\rk(X)\} is its closure. A flat equals its closure; X spans A when A\subseteq\cl(X). Write L=\cl(\varnothing) for the set of loops, and put
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.
The minimum in (2.1) 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 [2, Section 3]. Related sample/value symmetries appear in the paired-draw analyses of Rubinstein, Wang, and Weinberg [14, Section 3] and Caramanis et al. [4, Sections 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 2.2 (One-sample simulation). A measurable fixed-vector rule satisfying (2.1) yields a measurable one-sample rule with the same competitive ratio against the adversary of Theorem 1.1.
Proof. Draw its entire seed independently of the sample and value vectors S,V. For analysis, define
Given any seed, the choices of which copies to use are fixed. The mutual independence and matching laws of S_e,V_e imply
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.1) 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 \OPT_M(V), whose expectation is finite.
2.1 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:
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 \rk(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 \rk(Z\mid P) and spans all of Z over P.
3 Constructing the fixed-vector rule
We construct the rule of Proposition 2.1 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.
3.1 Rounding and a maximum branch
Fix the constants
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=\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
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
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.
3.2 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 2.2, 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
The full set U is used for analysis; the candidate test itself is computable as soon as the weight of e is known.
Lemma 3.1 (Candidate mass). The set Y is independent, Y\subseteq U, and
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\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
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.
3.3 Density expansions
For a listed group h and a flat P, let Q_h(P) be the largest flat maximizing
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 3.5 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 [15, Section 3.1, Equation (1)]. We prove the needed monotonicity and residual-rank bounds directly.
Lemma 3.2 (Density expansion). The largest maximizer in (3.6) exists, the map Q_h is increasing, and P\subseteq Q_h(P). If Q=Q_h(P), then for every set Z,
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 (2.2). 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 \cl(Q\cup Q') is feasible at P'. Optimality gives one inequality and supermodularity the reverse:
Equality in the two optimality comparisons shows that \cl(Q\cup Q') is also a maximizer at P'. Its largest maximizer contains Q, as claimed. Finally compare Q with the feasible flat \cl(Q+Z) in (3.6). The difference of their ranks is \rk(Z\mid Q), giving (3.7).
3.4 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
In increasing group order, form its nominal and guarded paths
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 3.3 (Path properties). The paths increase with k and satisfy
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
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 (3.9) 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.
3.5 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 [6, Section 3]; here the nested flats come from the guarded density paths.
At arrival of a label e, perform the following operations.
- 1.
Reject if e\in H\cup D\cup C, if its candidate test fails, or if its rounded weight is not listed.
- 2.
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{3.10} - 3.
Let A_b be the previously accepted labels assigned to this layer. Accept e exactly when \rk(\{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 3.3, 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.
Figure 1: 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 3.4 (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 3.3, 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.
3.6 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 3.5 (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
In particular \rk(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
By monotonicity, P_k\subseteq X_h(k). It is feasible in the maximization defining X_h(k), whence
The flat R_k=\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.
4 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
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
These are analysis quantities; the online rule does not compute them. Our objective is Lemma 4.3: 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 (4.2).
4.1 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:
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
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
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
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 (4.3) 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
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.
4.2 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 4.1 (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
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
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
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
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 (4.7) 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 4.2 (Exit mass). Every nonloop d exits its h-th nominal path by the end of the reverse computation, and
Consequently,
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
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=\ind{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
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 4.1 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
For p_0=2^{-(\ell+1)}, sum this bound over \ell\ge12 to obtain
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 (4.8).
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 \ind{d\in X_h(b)}p_{b-1} has expectation equal to the probability of exit at that step. Summing gives (4.9).
4.3 A hybrid transition
Lemma 4.2 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:
Let \widetilde N=\mathcal G_{b-1}(\widetilde c,S), and write \widetilde A_j for its intermediate flats in (4.3).
Conditional on the complete ordinary-step transcript, the partition in (4.11) 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)\}, \Prob(d\notin\widetilde N_h\mid\mathcal H_{b-1})=p_{b-1}. The tower property therefore gives
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:
To prove it, induct over j<h. If \widetilde A_{j-1}\supseteq F_{j-1}(b-2), monotonicity gives
The retained guards in (4.11) 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
The focal map Q_{h,b-1}=Q_h is enabled, so another application of monotonicity proves (4.13). 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, (4.13) gives its safety exclusion. Thus (4.12) implies
These bounds may be summed by linearity. For a fixed label the actual birth events at distinct endpoints are disjoint.
Lemma 4.3 (Safe sampled labels). For every listed group h,
Proof. Apply Lemma 4.2 to each d\in D_h\cap Y. By Lemma 3.3, 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
Here Y is independent in the matroid, and the last inequality is the generator bound of Lemma 3.5. Summing (4.14) over labels and valid birth times therefore gives a pre-parity expected safe count at least
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 (4.15).
5 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
Put P_{h,b}=\varnothing for other endpoints of the chosen parity, and define the nominal rank statistic
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 5.1 (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
We first relate z_h to the safe sampled count \sigma_h. Choose enough unsacrificed labels to witness the rank in each summand of (5.1). 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
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
By (5.3), \mathcal R_h\subseteq O.
There is a deterministic comparison with the safe count from Section 4:
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
A safe sample at b outside \mathcal R_h belongs to D_h\cap(\cl(Q'_b\cup Z_b)\setminus Q'_b). The residual density inequality (3.7) bounds the number of these samples by \kappa\rk(Z_b\mid Q'_b)\le\kappa|Z_b|. Summing proves (5.5).
5.1 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 5.2 (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
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
These numbers are fixed before any insertions are chosen, and \sum_j\Delta_j=\rk(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
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 [16, Section 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 (5.6). In particular, all movable orders, positions, and marks have already been counted, with no additional permutation or timeline factor.
5.2 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 5.3 (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
such that, whenever this group is listed and z_h\le n/\kappa, every residual (5.4) obtained from witnesses (5.3) 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 3.5 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
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 (5.8). Hence the set receiving mark 1 among the tested labels U_i is precisely
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:
- (i)
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.
- (ii)
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:
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
The inclusions K_{h,b}\subseteq F(b) and Z_b\subseteq X_h(b), together with (5.8), 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 (5.10) 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 (5.10), 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 5.2 gives
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
Use q\le n/\kappa and 2q\le\lfloor2n/\kappa\rfloor, with \alpha=1/\kappa and \alpha=2/\kappa, respectively, in (5.11). This yields
as claimed. All labels tested here are nonloops by the initial candidate filter, and the argument uses no representability property of the matroid.
5.3 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 5.1. Put n=n_i. On the unlisted branch D\cap U_i is empty, so Lemma 4.3, 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
Use the conditioning in Lemma 5.3. Within U_i, the events \{e\in O\} remain independent across labels, each with probability
Thus, for each fixed R_0\in\mathfrak R_i, \Prob(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
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 (5.3) 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
The latter bound follows first under the conditioning of (5.13), then by averaging that conditioning away. No independence is asserted for the selected residual itself.
In every outcome,
For listed outcomes with z_i\le n/\kappa this is (5.5); 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 (5.12) gives
which proves (5.2).
6 Rank and payoff for every arrival order
We now pass from the nominal rank guarantee of Lemma 5.1 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.
6.1 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
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 6.1 (Order-uniform rank bound). For each realization of all coins and every permutation \pi,
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
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
Sum over the layers to prove (6.2). Including unselected or sacrificed labels in K_{h,b} only weakens this bound.
6.2 One budget for later path expansions
Lemma 6.2 (Telescoping rank cost). For each listed group h, the nominal statistic z_h satisfies
Proof. Choose the generator sets of Lemma 3.5 and put
This single set satisfies |J|\le c_h and, for every integer k,
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 (6.3) lies between A and \cl(A+J). The resulting rank loss is at most
The inequality follows from two applications of decreasing conditional rank along the nested sets
the last inclusion follows from K_{h,b}\subseteq F_{h-1}(b) and P_{h,b}\subseteq X_h(b). Specifically, \rk(J\mid A)\le\rk(J\mid X_h(b-2)) and \rk(J\mid A+S')\ge\rk(J\mid X_h(b)). Summing the right side of (6.5) over the chosen parity telescopes to at most \rk(J)\le |J|. Missing endpoints may be added, since all differences are nonnegative. This proves (6.3); neither independence of J nor a separate budget for each layer is required.
6.3 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 6.3 (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
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 (6.6). 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 6.2 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:
Only then take expectations. The mask probabilities are unchanged under this conditioning, so
The exact density-mask contribution would be 1/(4\kappa); the larger coefficient is convenient. Lemmas 5.1 and 6.3 now imply, for every true group of size n_i\ge\kappa,
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.
6.4 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 6.1, 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
The order has been minimized before any expectation is taken.
Multiply (6.8) by B^i and sum over analyzed groups. The higher-weight cost is bounded using
With the constants in (3.1),
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 (6.9) yields
Suppose W>0, so m_*>0. Ignoring the smaller true groups loses at most
If m_*\le W/(8\kappa), Lemma 3.1 and (6.12) give
Since \gamma=2^{-16}, we have \gamma/4-2^{-21}=7\cdot2^{-21}\ge\gamma/8. Therefore
If instead m_*>W/(8\kappa), the maximum branch gives more than W/(32\kappa) by (3.3).
Proof of Proposition 2.1 and Theorem 1.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 (3.2), the resulting fixed-vector reward fraction is
When W=0, the benchmark is zero and the conclusion is immediate. Feasibility and measurability follow from Lemma 3.4 and the analogous immediate properties of the maximum branch. This proves Proposition 2.1. The revealed mask is selected from the initial seed, independently of the weights, so Lemma 2.2 proves Theorem 1.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.
7 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 [2, 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.1. 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 7.1 (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,
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.1, 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
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,
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 (7.2) 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,
The marginal law of R is the source law and w was fixed before the randomness. Averaging this pointwise inequality and applying Proposition 2.1 proves (7.1) 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 \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 [1, 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 [17, Theorem 3.1] and Huang [10, 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 7.1 instead applies after arbitrary full-seed adversarial rearrangement of the unobserved suffix, with no additional loss from the fixed-vector guarantee.
References
- [1]Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal. On the Strong Matroid Secretary Conjecture and Beyond. 2026. Preprint, version 1, September 16, 2026; arXiv:2609.19118v1. arXiv:2609.19118, https://arxiv.org/abs/2609.19118v1.
- [2]Pablo D. Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet Inequalities with Limited Information. In Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1358–1377, 2014. Full version: arXiv:1307.3736v1. doi:10.1137/1.9781611973402.100.
- [3]Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, Secretary Problems, and Online Mechanisms. In Proceedings of the Eighteenth Annual ACM–SIAM Symposium on Discrete Algorithms, pages 434–443, 2007. https://www.microsoft.com/en-us/research/publication/matroids-secretary-problems-and-online-mechanisms/.
- [4]Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuser. Single-Sample Prophet Inequalities via Greedy-Ordered Selection. In Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1298–1325, 2022. Revised full version: arXiv:2111.03174v2, March 15, 2024. doi:10.1137/1.9781611977073.54.
- [5]Jack Edmonds. 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, 1965. doi:10.6028/jres.069B.004. doi:10.6028/jres.069B.004.
- [6]Moran Feldman, Ola Svensson, and Rico Zenklusen. A Simple O(\log\log(\mathrm{rank}))-Competitive Algorithm for the Matroid Secretary Problem. In Proceedings of the Twenty-Sixth Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1189–1201, 2015. Full version: arXiv:1404.4473v2, July 4, 2014. doi:10.1137/1.9781611973730.79.
- [7]Moran Feldman, Ola Svensson, and Rico Zenklusen. Online Contention Resolution Schemes. In Proceedings of the Twenty-Seventh Annual ACM–SIAM Symposium on Discrete Algorithms, pages 1014–1033, 2016. Full version: arXiv:1508.00142v2, October 14, 2015. doi:10.1137/1.9781611974331.ch72.
- [8]Moran Feldman, Ola Svensson, and Rico Zenklusen. Nearly Tight Sample Complexity for Matroid Online Contention Resolution. In Proceedings of the 2026 Annual ACM–SIAM Symposium on Discrete Algorithms, pages 4692–4711, 2026. Full version: arXiv:2507.09507v1, 2025. doi:10.1137/1.9781611978971.171.
- [9]Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Sample-Based Matroid Prophet Inequalities. In Proceedings of the 25th ACM Conference on Economics and Computation, 2024. Full version: arXiv:2406.12799v1. doi:10.1145/3670865.3673506.
- [10]Zhiyi Huang. Settling the Matroid Secretary Problem. 2026. Preprint, September 24, 2026; arXiv:2609.30421v1. arXiv:2609.30421, https://arxiv.org/abs/2609.30421v1.
- [11]Robert Kleinberg and S. Matthew Weinberg. Matroid Prophet Inequalities. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 123–136, 2012. Full version: arXiv:1201.4764v1. doi:10.1145/2213977.2213991.
- [12]Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745–747, 1977. doi:10.1090/S0002-9904-1977-14378-4. doi:10.1090/S0002-9904-1977-14378-4.
- [13]Oded Lachish. O(\log\log\mathrm{rank}) Competitive Ratio for the Matroid Secretary Problem. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 326–335, 2014. Full version: arXiv:1403.7343v4, September 2, 2014. doi:10.1109/FOCS.2014.42.
- [14]Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal Single-Choice Prophet Inequalities from Samples. In 11th Innovations in Theoretical Computer Science Conference, pages 60:1–60:10, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. Corrected full version: arXiv:1911.07945v2, September 10, 2025. doi:10.4230/LIPIcs.ITCS.2020.60.
- [15]Richard Santiago, Ivan Sergeev, and Rico Zenklusen. Constant-competitiveness for random assignment Matroid secretary without knowing the Matroid. Mathematical Programming, 210:815–846, 2025. doi:10.1007/s10107-024-02177-x. doi:10.1007/s10107-024-02177-x.
- [16]L. Schläfli. Ueber die Zahl der Teile, in welche die nfache Totalität durch eine beliebige Menge (n-1)facher linearer Kontinua geteilt wird. In J. H. Graf, editor, Theorie der vielfachen Kontinuität, pages 39–42, Georg & Co., 1901. Digital reproduction: Birkhäuser, 2013; doi:10.1007/978-3-0348-5118-3_18. doi:10.1007/978-3-0348-5118-3_18.
- [17]Sahil Singla. The Matroid Secretary Conjecture Is True. 2026. Preprint, first posted September 13, 2026; revised September 29, 2026. arXiv:2609.14555v2. arXiv:2609.14555, https://arxiv.org/abs/2609.14555v2.
- [18]José A. Soto. Matroid Secretary Problem in the Random-Assignment Model. SIAM Journal on Computing, 42(1):178–211, 2013. Preprint version: arXiv:1007.2152v1, 2010. doi:10.1137/110852061.