Introduction
The classic secretary problem [26 , 54 ] asks us to select the largest of n n n distinct values revealed in uniformly random order, with immediate and irrevocable decisions. Rejecting roughly the first n / e n/e n / e values and then selecting the next value larger than all earlier ones gives the asymptotically optimal success probability 1 / e 1/e 1/ e . Motivated by applications in auction design, Hajiaghayi, Kleinberg, and Parkes [38 ] and Kleinberg [45 ] studied the generalization in which up to r r r values may be selected. Babaioff, Immorlica, and Kleinberg [11 ] , with Kempe in the journal version [13 ] , introduced the matroid secretary problem : fixed nonnegative values arrive in uniformly random order, and the selected elements must form an independent set of a matroid. Does such a constraint make online selection any harder than choosing a single element?
Matroids are natural constraints for this question. Offline, decreasing-value greedy finds a maximum-value independent set; indeed, among downward-closed systems, matroids are exactly those for which greedy is optimal for every nonnegative value assignment [27 ] . An algorithm is c c c -competitive, for c ≥ 1 c \ge1 c ≥ 1 , if its expected value is at least 1 / c 1/c 1/ c times the offline optimum.
The matroid secretary conjecture [11 ] asks whether a universal constant suffices for every matroid; its strong form asks for the optimal constant e e e , matching rank one. Before the results presented here, the best general guarantee was O ( log log r ) O(\log\log r) O ( log log r ) , where r r r is the matroid rank [51 , 32 ] . This bound had stood since 2014, despite constant guarantees for graphic [11 ] , laminar [43 ] , and transversal [23 ] matroids, among many other classes (see Table 1). Natural greedy and partition-based approaches also face provable barriers [7 , 2 ] .
A related question concerns the information needed for online selection. In a matroid prophet inequality , the values are independent draws from known distributions, and the arrival order may be any fixed order. Kleinberg and Weinberg [50 ] gave a 2-competitive algorithm for every matroid, matching the classical single-element prophet inequality [49 ] . In the single-sample version [3 ] , the distributions are unknown and the algorithm receives only one independent sample from each. For rank-one matroids, one sample per distribution already suffices for the optimal ratio 2 [62 ] . For general matroids, however, constant ratios were known only with polylogarithmically many samples per distribution [29 , 34 ] . Does one sample suffice for a constant competitive ratio, or even for the optimal ratio 2? A positive answer would also resolve the matroid secretary conjecture for known matroids, by Li’s reduction [29 ] (Appendix § 13 ).
We resolve both problems with optimal ratios e e e and 2, matching the rank-one guarantees. Since natural greedy rules that compare arrivals with a fixed sample can fail (Appendix § 9 ), our algorithms maintain a reference state whose greedy solution contains every accepted element, updating it even after rejections to preserve an exact distributional invariant. Our secretary algorithms use only ordinal information: the relative order of observed values. Moreover, our optimal algorithm accepts each element of the canonical optimum8 independently with probability 1 / e 1/e 1/ e . Such a per-element guarantee of 1 / c 1/c 1/ c , called c c c -probability-competitiveness , implies ordinary c c c -competitiveness.
Results
Theorem 1.1 (Optimal matroid secretary; informal Theorem 6.1 ). For every n n n -element matroid revealed online, there is an ordinal secretary algorithm that accepts the elements of the canonical optimum independently, each with probability 1 / e 1/e 1/ e . Knowing only n n n in advance, it uses an expected polynomial number of independence queries on subsets of arrived elements.
Our second result considers the standard single-sample prophet model with an oblivious arrival order: the matroid and one independent sample per element are given before arrivals.
Theorem 1.2 (Optimal single-sample matroid prophet inequality; informal Theorem 3.1 ). For every known matroid and independent nonnegative value distributions, one independent sample from each distribution suffices for a 2-competitive algorithm using comparisons and O ( n 2 ) O(n^2) O ( n 2 ) independence queries. The arrival order may be any fixed order independent of the samples, values, and algorithmic randomness; the algorithm need not know that order.
More strongly, its accepted elements and values are distributed exactly as an independent half-sample of the canonical optimum of fresh independent values, so it obtains exactly half the expected offline optimum.
A short combinatorial argument proves the original matroid secretary conjecture (§ 2 ).
Theorem 1.3 (Combinatorial matroid secretary; informal Theorem 2.2 ). For every n n n -element matroid revealed online, there is an ordinal secretary algorithm that accepts each element of the canonical optimum with probability at least 1 / 4 1/4 1/4 . Knowing only n n n in advance, it uses O ( n 2 ) O(n^2) O ( n 2 ) independence queries on subsets of arrived elements.
Characterizing online acceptance distributions. For a known matroid, we also show that a finite polytope exactly characterizes the conditional accepted-set distributions of ordinal secretary algorithms (Theorem 4.1). Its continuous-time version turns algorithm design into distribution design: every family satisfying its constraints is realized online. Constructing one such family already resolves the strong matroid secretary conjecture; we then give an efficient implementation (Theorems 5.2 and 6.1 ). The same characterization also gives exact LPs for two benchmarks among ordinal algorithms (§ 4.2 ): the optimal per-element selection probability (probability competitiveness ) and the best expected-value fraction (ordinal competitiveness ). These differ even on uniform matroids: for rank k k k and n ≥ 2 k n \ge2k n ≥ 2 k , the first is 1 − Θ ( log k / k ) 1-\Theta(\sqrt{\log k/k}) 1 − Θ ( log k / k ) as k → ∞ k \to\infty k → ∞ , whereas ordinal algorithms achieve expected-value fraction 1 − O ( k − 1 / 2 ) 1-O(k^{-1/2}) 1 − O ( k − 1/2 ) (Theorem 7.1 ). The matching lower bound resolves a question of Soto, Turkieltaub, and Verdugo [66 ] .
Finite-size guarantees and extensions. For linear matroids known in advance, one can beat 1 / e 1/e 1/ e for every finite n ≥ 2 n \ge2 n ≥ 2 : a separate construction selects each optimum element with the classical rank-one success probability for n n n elements (Theorem 7.2 ). Computations on small matroids suggest the same finite-size comparison for ordinal competitiveness more generally (Appendix § 11 ). Beyond a single matroid, combining our reference-set method with the preprocessing of Feldman, Svensson, and Zenklusen [33 ] gives ratio 8 k 2 ( k + 1 ) 8k^2(k+1) 8 k 2 ( k + 1 ) for intersections of k k k matroids (Theorem 7.3 ), avoiding the exponential dependence on k k k in their general combination bound.
Technical overview
Inserting an optimum element into a greedy solution displaces at most one element, its exchange partner . If this partner were fixed independently of a uniformly random processing order, then with probability 1 / 2 1/2 1/2 the optimum element would precede it and could be accepted safely. But the partner depends on the algorithm’s state, which depends on the order. Instead, our algorithms maintain a reference state whose greedy solution contains every accepted element, and update it even after rejections so that the state seen by any fixed element, its snapshot , has an explicit distribution.
Reversible updates (§ 2 ). The combinatorial algorithm of Theorem 1.3 first rejects a random half-sample, which becomes the reference set. It then tries to insert each real arrival and, interleaved with these, to delete each sample element, updating only when greedy membership of every previously processed element is preserved. This test is symmetric, so every update can be undone: for any fixed processing order, the updates merely permute the equally likely initial samples. Hence each snapshot is uniform and independent of the processing order, and conditioning on it fixes the exchange partner without biasing their relative order. An optimum element is a real arrival with probability 1 / 2 1/2 1/2 and is then accepted with probability at least 1 / 2 1/2 1/2 , giving 1 / 4 1/4 1/4 .
Exchangeable values (§ 3 ). The prophet algorithm of Theorem 1.2 stores one value per element, initially its sample, and each arrival proposes replacing its sample by its real value. If the update would remove a processed element from the greedy basis, that element’s acceptance blocks it and its rejection forces it; otherwise a fair coin decides. The arrival is accepted if the update occurs and it belongs to the new basis. By exchangeability of sample and real values, the stored values remain a fresh product draw, and the accepted set a half-sample of its processed greedy elements.
Distributions as algorithms (§ 4 ). For the optimal ratio e e e , we reverse the approach: design the accepted-set distributions first, and then realize them online. In a continuous-time formulation, two linear conditions characterize which distributions are realizable: capacity , which prevents moving more probability mass than a state contains, and consistency , which ensures that the transitions produce the prescribed distributions. Every feasible family is realized by an explicit rule (Theorem 4.4 ), so it suffices to construct one.
Survivor distributions (§ 5 ). We construct this family from an offline experiment with independent auxiliary arrival times: sample each element independently with probability 1 / e 1/e 1/ e , and then thin the sample’s greedy solution to obtain the survivors . The thinning probabilities are motivated by the rank-one analysis and preserve every sampled global optimum element. The survivors therefore form an independent set and include each optimum element independently with probability 1 / e 1/e 1/ e . The main obstacle is showing that this family is feasible. Consistency follows from a direct calculation as time advances. The crux is capacity: for every possible preceding accepted set, there must be enough probability mass to support the next acceptance. We prove it by induction after removing the largest element, comparing the survivor experiment with the same experiment in the matroid contracted by the arriving element. The rule realizing this family (Algorithm 3) already resolves the strong matroid secretary conjecture (Theorem 5.2 ).
From proof to efficient algorithm (§ 6 ). This rule needs probabilities of entire survivor sets, which we do not know how to compute efficiently. We therefore turn the capacity proof into a sampler: inductive comparisons become recursive calls, and unused mass becomes rejection. The sampler needs the auxiliary randomness conditioned on the accepted set, so we maintain a sample of it, one coordinate per element. Forward updates make new acceptances survive; reverse updates prevent old rejections from surviving. A continuous snapshot argument shows these updates keep the sample correctly distributed, giving an expected-polynomial-time algorithm (Theorem 1.1 ).
Related work and roadmap
Matroid secretary and related models. For general matroids, the guarantee improved from O ( log r ) O(\log r) O ( log r ) [11 ] to O ( log r ) O(\sqrt{\log r}) O ( log r ) [19 ] and then to O ( log log r ) O(\log\log r) O ( log log r ) [51 , 32 ] ; Table 1 lists progress on special classes. Constant guarantees were known in models that weaken the adversary: free-order secretary [44 , 3 ] , where the algorithm chooses the order; randomly assigned values [65 , 37 ] ; and prophet secretary [28 ] , with known value distributions.
Sample-based prophet inequalities. Beyond rank one [62 ] , single-sample guarantees were known for several matroid classes and matchings [18 ] . For general matroids, [29 ] obtained ratio 4 + ε 4+\varepsilon 4 + ε using O ε ( log 4 n ) O_{\varepsilon}(\log^{4} n) O ε ( log 4 n ) samples per distribution. Feldman, Svensson, and Zenklusen [34 ] reduced this to O ε ( log n + log r log 2 log r ) O_{\varepsilon}(\log n+\log r\log^{2}\log r) O ε ( log n + log r log 2 log r ) samples with the same ratio. Both handle an almighty adversary, which sees the samples, values, and algorithmic randomness before choosing the order. We assume an oblivious order. Complementing Li’s reduction, Azar, Kleinberg, and Weinberg [3 ] convert order-oblivious secretary algorithms, whose guarantee survives an arbitrary order after a random initial sample, into single-sample prophet algorithms with the same ratio.
Table 1. Earlier guarantees and our optimal general-matroid ratio. P denotes a per-element probability guarantee. Some results require advance knowledge of the matroid or its representation. Parameters μ \mu μ and γ ( M ) \gamma(\mathcal{M}) γ ( M ) are defined in the cited works.
LP and distributional approaches. Buchbinder, Jain, and Singh [14 ] give finite LP characterizations for classical and multiple-choice secretary problems; Chan, Chen, and Jiang [17 ] develop continuous LPs for these variants. These LPs track only the number of accepted elements, which suffices under cardinality constraints; for general matroids, feasibility depends on the accepted set itself, so our polytope tracks distributions over accepted sets. Random-order contention resolution [6 , 55 ] provides related per-element guarantees, and Dughmi [25 ] establishes an equivalence between matroid secretary and correlated random-order contention resolution. Aminian, Niazadeh, and Nuti [5 ] study stationary online contention resolution schemes, whose output distribution is independent of arrival order. Our characterization instead conditions on the observed elements and their relative value order, averaging over the arrival order.
Concurrent and subsequent work. The linear-matroid guarantee, including the finite-size probabilities in Theorem 7.2 , was obtained independently in [9 ] . Building on Singla’s preprint [64 ] , Chan, Lin, and Wang [20 ] improved the general-matroid competitive ratio from 4 to ≈ 3.1462. OpenAI [58 ] subsequently obtained a constant-competitive single-sample matroid prophet inequality against the stronger almighty adversary.
Roadmap. § 2 and § 3 prove the 4-competitive secretary and optimal single-sample prophet guarantees. § 4 to § 6 develop the polyhedral characterization, the optimal survivor distributions, and their efficient implementation, respectively. § 7 gives finite-size results and extensions. AI models played a material role in developing the main algorithmic guarantees; the AI methodology statement describes this role. The appendices contain examples, deferred proofs, and computations.
Matroid Secretary via Reversible Updates
We begin with a combinatorial 4-probability-competitive algorithm for matroid secretary. Its proof illustrates two ideas that will recur: protect irrevocable decisions through a changing greedy solution, and make the updates to a reference state reversible, so that they preserve a useful distribution.
Preliminaries
Fix a matroid M = ( V , I ) \mathcal{M}=(V,\mathcal{I}) M = ( V , I ) with nonnegative values v e v_e v e . Ties are broken by a fixed order of element labels, independent of arrival order; “larger” and “smaller” refer to this tie-broken value order. Write T + e = T ∪ { e } T+e=T\cup\{e\} T + e = T ∪ { e } , T − e = T ∖ { e } T-e=T\setminus\{e\} T − e = T ∖ { e } , and v ( A ) = ∑ e ∈ A v e v(A)=\sum_{e\in A}v_e v ( A ) = ∑ e ∈ A v e . For T ⊆ V T\subseteq V T ⊆ V , let Greedy ( T ) \operatorname{Greedy}(T) Greedy ( T ) be the output of greedy, which scans T T T in decreasing value order and adds each element that keeps the current set independent. Greedy includes zero-valued elements whenever possible , so Greedy ( T ) \operatorname{Greedy}(T) Greedy ( T ) is a basis of the restriction to T T T ; this does not change the optimum value.
The rank of T T T is the largest size of an independent subset of T T T . An element is spanned by T T T if adding it does not increase the rank; the closure cl ( T ) \operatorname{cl}(T) cl ( T ) is the set of all such elements, and an element spanned by ∅ \varnothing ∅ is a loop . The elements greedy selects from a prefix P P P of its scan span P P P , so an element is selected precisely when the elements preceding it do not span it, and greedy selects exactly rank ( P ) \operatorname{rank}(P) rank ( P ) elements from P P P . We use the following standard consequences [27 , 16 , 63 ] .
Lemma 2.1 (Greedy monotonicity and one-element sensitivity). With fixed tie-breaking, the following properties hold.
(i) If e ∈ T ⊆ V e\in T\subseteq V e ∈ T ⊆ V and e ∈ Greedy ( V ) e\in\operatorname{Greedy}(V) e ∈ Greedy ( V ) , then e ∈ Greedy ( T ) e\in\operatorname{Greedy}(T) e ∈ Greedy ( T ) . More generally, reducing other values while keeping a selected element’s value fixed does not remove it from greedy.
(ii) For e ∉ T e\notin T e ∈ / T , the set Greedy ( T + e ) \operatorname{Greedy}(T+e) Greedy ( T + e ) is either Greedy ( T ) \operatorname{Greedy}(T) Greedy ( T ) , Greedy ( T ) + e \operatorname{Greedy}(T)+e Greedy ( T ) + e , or ( Greedy ( T ) − f ) + e (\operatorname{Greedy}(T)-f)+e ( Greedy ( T ) − f ) + e for one f ∈ Greedy ( T ) f\in\operatorname{Greedy}(T) f ∈ Greedy ( T ) .
(iii) Changing one value on a fixed ground set either leaves the greedy basis unchanged or exchanges that element with one other element. An increase can only bring the changed element into the basis; a decrease can only remove it.
Proof. For (i), restricting the ground set or reducing other values can only shrink the selected element’s predecessor set. A subset cannot span an element that the larger set did not span.
For (ii), inserting e e e into the scan can only add a predecessor to each old element. Thus no old element can enter greedy, and the only possible new member is e e e . Greedy returns bases of T T T and T + e T+e T + e , whose ranks differ by at most one, giving the three possibilities. For (iii), increasing the value of e e e shrinks its predecessor set and can only add e e e to the others’, so only e e e can enter and only other elements can leave; since both bases have the same size, any change is one exchange. A decrease is symmetric.
The algorithm
Model. The n = ∣ V ∣ n = |V| n = ∣ V ∣ elements arrive in a uniformly random order. On each arrival, the algorithm observes the element and its value and must irrevocably accept or reject it before the next arrival. The accepted set must be independent. The number n n n is known; values and the matroid are otherwise unknown, and independence queries may involve only observed elements. A c c c -probability-competitive algorithm accepts each e ∈ Greedy ( V ) e \in\operatorname{Greedy}(V) e ∈ Greedy ( V ) with probability at least 1 / c 1/c 1/ c . An algorithm is ordinal if it uses values only through their tie-broken order.
Algorithm. The algorithm first rejects and stores a random initial sample S S S , with ∣ S ∣ ∼ Bin ( n , 1 / 2 ) |S| \sim\operatorname{Bin}(n,1/2) ∣ S ∣ ∼ Bin ( n , 1/2 ) ; call the remaining arrivals real . It then runs n n n processing steps, each either receives the next real arrival or internally processes the next stored sample element. Its reference state is a configuration C ⊆ V C \subseteq V C ⊆ V , initially S S S ; it also maintains the set F F F of processed elements, initially empty. A sample element enters F F F only when internally processed and remains rejected. Write C ⊕ e C \oplus e C ⊕ e for adding e e e to C C C if absent and removing it if present, so ( C ⊕ e ) ⊕ e = C (C \oplus e) \oplus e = C ( C ⊕ e ) ⊕ e = C . Processing e e e proposes C ′ = C ⊕ e C' = C \oplus e C ′ = C ⊕ e , a deletion for a sample element and an insertion for a real arrival. The update occurs exactly when it passes the preservation test : the greedy membership of every element of F F F remains unchanged.
Table 1 (PDF p. 7).
Only the step processing e e e can change its membership in C C C , so immediately before that step e ∈ C e \in C e ∈ C if and only if e ∈ S e \in S e ∈ S . At a sample processing step, therefore, e ∉ C ′ e \notin C' e ∈ / C ′ and cannot be accepted in step 2(a). All queried sets consist of observed elements.
The preservation test on all of F F F protects earlier acceptances. Its symmetry also makes each configuration update reversible : with e e e and F F F fixed, it swaps C C C and C ′ C' C ′ when the test passes and leaves both unchanged otherwise. Thus, for a fixed processing order, the updates permute the possible configurations. As a result, the configuration before any fixed element is processed is a uniformly random subset of V V V , independent of the processing order (Corollary 2.5). Appendix § 9 illustrates this mechanism and explains why natural greedy alternatives fail.
Theorem 2.2. Algorithm 1 always returns an independent set and accepts each e ∈ Greedy ( V ) e \in\operatorname{Greedy}(V) e ∈ Greedy ( V ) with probability at least 1 / 4 1/4 1/4 . It is ordinal and uses O ( n 2 ) O(n^2) O ( n 2 ) independence queries.
Lemma 2.3 (Feasibility). After every processing step , A L G ⊆ Greedy ( C ) ∩ F \mathrm{ALG} \subseteq\operatorname{Greedy}(C) \cap F ALG ⊆ Greedy ( C ) ∩ F .
Proof. The inclusion holds initially, since A L G = F = ∅ \mathrm{ALG} = F = \varnothing ALG = F = ∅ . If a step’s preservation test fails, C C C and A L G \mathrm{ALG} ALG are unchanged and F F F only grows. If it passes, every previous acceptance lies in F F F , so it stays in the greedy solution, and a new acceptance lies in Greedy ( C ′ ) \operatorname{Greedy}(C') Greedy ( C ′ ) and is then added to F F F .
The snapshot lemma
Let Π \Pi Π be the processing order. For each e ∈ V e \in V e ∈ V , the snapshot C e C_e C e is the configuration immediately before processing e e e .
Lemma 2.4 (Snapshot lemma). Fix an element e e e and a processing order π \pi π . For every T ⊆ V T \subseteq V T ⊆ V , exactly one initial sample set S ⊆ V S \subseteq V S ⊆ V gives C e = T C_e = T C e = T .
Proof. Fix the processing order and consider a step before e e e . Let f f f be the element processed at this step and F F F the set processed before it. Both f f f and F F F are determined by the fixed order.
At this step, the algorithm either leaves the configuration C C C unchanged or replaces it by C ⊕ f C \oplus f C ⊕ f . The test Greedy ( C ) ∩ F = Greedy ( C ⊕ f ) ∩ F \operatorname{Greedy}(C) \cap F = \operatorname{Greedy}(C \oplus f) \cap F Greedy ( C ) ∩ F = Greedy ( C ⊕ f ) ∩ F has the same answer at C C C and C ⊕ f C \oplus f C ⊕ f : the two sides are simply interchanged. If it passes, starting from C C C gives C ⊕ f C \oplus f C ⊕ f , and starting from C ⊕ f C \oplus f C ⊕ f gives C C C . If it fails, each of these two configurations stays unchanged. Thus each step maps configurations bijectively onto themselves and is its own inverse; this is the reversibility of the updates.
Consequently, given the configuration D D D immediately after this step, we can recover the preceding configuration explicitly. Compare Greedy ( D ) ∩ F \operatorname{Greedy}(D) \cap F Greedy ( D ) ∩ F and Greedy ( D ⊕ f ) ∩ F \operatorname{Greedy}(D \oplus f) \cap F Greedy ( D ⊕ f ) ∩ F . If they are equal, the preceding configuration was D ⊕ f D \oplus f D ⊕ f ; otherwise it was D D D . These are the only two possible predecessors, since this step can change only the membership of f f f , and the test selects exactly one of them.
Now start from the prescribed snapshot T T T immediately before e e e and undo the preceding steps from last to first by the above rule. This determines a unique configuration S S S before the first step, which must be the initial sample. Conversely, running the algorithm forward from S S S reverses each reconstruction step and reaches T T T , so S S S indeed gives C e = T C_e = T C e = T .
The reconstruction does not require the accepted set: every test uses only the current configuration, the current element, and the processed set determined by the fixed order.
Corollary 2.5 (Snapshot independence). For each fixed e ∈ V e \in V e ∈ V , the snapshot C e C_e C e is a uniformly random subset of V V V , independent of the uniformly random processing order Π \Pi Π .
Proof. Fix T ⊆ V T \subseteq V T ⊆ V and a permutation π \pi π . By Lemma 2.4 , there is exactly one initial sample S 0 S_0 S 0 giving C e = T C_e = T C e = T under order π \pi π . Exactly one bit vector and arrival order produce ( S 0 , π ) (S_0,\pi) ( S 0 , π ) : X i = 1 { π ( i ) ∈ S 0 } X_i = 1\{\pi(i) \in S_0\} X i = 1 { π ( i ) ∈ S 0 } , and the arrival order lists S 0 S_0 S 0 first and then V ∖ S 0 V \setminus S_0 V ∖ S 0 , each in its order within π \pi π . This choice has probability 2 − n / n ! 2^{-n}/n! 2 − n / n ! . Hence Pr [ C e = T , Π = π ] = 1 / ( 2 n n ! ) \Pr[C_e = T,\Pi= \pi] = 1/(2^n n!) Pr [ C e = T , Π = π ] = 1/ ( 2 n n !) , which proves the claim.
The competitive guarantee
Proof of Theorem 2.2 . By Lemma 2.3 , A L G \mathrm{ALG} ALG lies in a greedy basis and is independent. Fix e ∈ Greedy ( V ) e \in\operatorname{Greedy}(V) e ∈ Greedy ( V ) and condition on C e = T C_e = T C e = T with e ∉ T e \notin T e ∈ / T . Since only e e e ’s own step changes its membership in the configuration, e ∉ S e \notin S e ∈ / S , so e e e is processed at its real arrival. By Lemma 2.1 (i), e ∈ Greedy ( T + e ) e \in\operatorname{Greedy}(T + e) e ∈ Greedy ( T + e ) , so it is accepted whenever the preservation test passes.
If inserting e e e removes no element, the preservation test passes. Otherwise, Lemma 2.1 (ii) gives a unique displaced f f f with Greedy ( T + e ) = ( Greedy ( T ) − f ) + e \operatorname{Greedy}(T + e) = (\operatorname{Greedy}(T) - f) + e Greedy ( T + e ) = ( Greedy ( T ) − f ) + e . Since e ∉ F e \notin F e ∈ / F , the test passes precisely when f ∉ F f \notin F f ∈ / F , or equivalently when e e e precedes f f f in Π \Pi Π . The partner f f f is determined by T T T , while conditional on C e = T C_e = T C e = T , the order Π \Pi Π remains uniform by Corollary 2.5. Hence e e e precedes f f f with probability 1 / 2 1/2 1/2 . In either case, Pr [ e ∈ A L G ∣ C e = T ] ≥ 1 / 2 \Pr[e \in\mathrm{ALG} \mid C_e = T] \ge1/2 Pr [ e ∈ ALG ∣ C e = T ] ≥ 1/2 . Finally, Pr [ e ∉ C e ] = Pr [ e ∉ S ] = 1 / 2 \Pr[e \notin C_e] = \Pr[e \notin S] = 1/2 Pr [ e ∈ / C e ] = Pr [ e ∈ / S ] = 1/2 . Averaging over these snapshots gives Pr [ e ∈ A L G ] ≥ 1 / 4 \Pr[e \in\mathrm{ALG}] \ge1/4 Pr [ e ∈ ALG ] ≥ 1/4 .
The algorithm uses only comparisons and independence queries on observed sets, with at most two greedy scans of at most n n n queries at each of the n n n steps.
Single-Sample Matroid Prophet Inequalities
We next obtain the optimal 2-competitive single-sample matroid prophet inequality. As in § 2 , we prove feasibility, a snapshot lemma, and snapshot independence; exchangeability of sample and real values now replaces reversibility. The invariant has two parts: the configuration keeps its initial product distribution, and, conditional on it, each processed greedy element is accepted independently with probability 1 / 2 1/2 1/2 .
The algorithm
Model. Fix a matroid M = ( V , I ) \mathcal{M} = (V, \mathcal{I}) M = ( V , I ) with n = ∣ V ∣ n = |V| n = ∣ V ∣ elements. Each element e e e has a nonnegative real value R e R_e R e drawn independently from an unknown distribution D e D_e D e . Before the arrivals, the algorithm receives one sample S e ∼ D e S_e \sim D_e S e ∼ D e for each e ∈ V e \in V e ∈ V . These samples are mutually independent and independent of all real values. The matroid is given by an independence oracle on all subsets of V V V . The real values arrive in an arbitrary fixed order π \pi π , independent of the samples, real values, and algorithmic randomness. The algorithm need not know π \pi π in advance. It must immediately accept or reject each arrival, and its accepted set must be independent.
Algorithm. The reference state is again a configuration : C C C assigns each f ∈ V f \in V f ∈ V a value C ( f ) ∈ { S f , R f } C(f) \in\{S_f, R_f\} C ( f ) ∈ { S f , R f } , initially C ( f ) = S f C(f) = S_f C ( f ) = S f . Once R e R_e R e is revealed, write C ⊕ e C \oplus e C ⊕ e for switching coordinate e e e between its sample and real values, leaving the other coordinates unchanged. Thus ( C ⊕ e ) ⊕ e = C (C \oplus e) \oplus e = C ( C ⊕ e ) ⊕ e = C . If the values are equal, C ⊕ e C \oplus e C ⊕ e changes nothing numerically, but the analysis distinguishes the copies. Only processing e e e changes its coordinate, so when e e e arrives, C ( e ) = S e C(e) = S_e C ( e ) = S e and C ⊕ e C \oplus e C ⊕ e installs R e R_e R e . Write Greedy ( C ) \operatorname{Greedy}(C) Greedy ( C ) for the greedy basis of V V V with values C ( f ) C(f) C ( f ) and the fixed tie-breaking from § 2 .
Maintain the configuration C C C , the accepted set A L G \mathrm{ALG} ALG , and the processed set F F F . The default is to update with probability 1 / 2 1/2 1/2 . If the update would remove a processed element from the greedy basis, its earlier decision determines the outcome: an acceptance blocks the update, and a rejection forces it. Accept the arriving element exactly when the update occurs and it belongs to the new basis.
Algorithm 2 Single-Sample Matroid Prophet
Initialize A L G = F = ∅ \mathrm{ALG} = F = \varnothing ALG = F = ∅ , C ( f ) = S f C(f) = S_f C ( f ) = S f for every f ∈ V f \in V f ∈ V , and B = Greedy ( C ) B = \operatorname{Greedy}(C) B = Greedy ( C ) .
For each arriving element e e e , when R e R_e R e is revealed:
Set C ′ = C ⊕ e C' = C \oplus e C ′ = C ⊕ e and compute B ′ = Greedy ( C ′ ) B' = \operatorname{Greedy}(C') B ′ = Greedy ( C ′ ) .
Draw a fresh independent fair bit Z Z Z . If ( B ∖ B ′ ) ∩ F = { f } (B \setminus B') \cap F = \{f\} ( B ∖ B ′ ) ∩ F = { f } , set Z ← 1 { f ∉ A L G } Z \gets1\{f \notin\mathrm{ALG}\} Z ← 1 { f ∈ / ALG } .
If Z = 1 Z = 1 Z = 1 , set C ← C ′ C \gets C' C ← C ′ and B ← B ′ B \gets B' B ← B ′ . Update even without acceptance
If Z = 1 Z = 1 Z = 1 and e ∈ B ′ e \in B' e ∈ B ′ , set A L G ← A L G + e \mathrm{ALG} \gets\mathrm{ALG} + e ALG ← ALG + e . Accept e e e
Set F ← F + e F \gets F + e F ← F + e . Record every processed element
Return A L G \mathrm{ALG} ALG .
By Lemma 2.1 (iii), ( B ∖ B ′ ) ∩ F (B \setminus B') \cap F ( B ∖ B ′ ) ∩ F has at most one element. The override in step 2 applies only to a processed element leaving the basis, not one reentering it.
Theorem 3.1. Algorithm 2 always returns an independent set and satisfies
E [ ∑ e ∈ A L G R e ] = 1 2 E [ max I ∈ I ∑ e ∈ I R e ] . \mathbb{E}\left[\sum_{e \in\mathrm{ALG}} R_e\right] = \frac{1}{2}\mathbb{E}\left[\max_{I \in\mathcal{I}}\sum_{e \in I} R_e\right]. E [ e ∈ ALG ∑ R e ] = 2 1 E [ I ∈ I max e ∈ I ∑ R e ] . It uses O ( n 2 ) O(n^2) O ( n 2 ) independence queries and no distributional knowledge beyond the given samples. More strongly, the selected elements and their values have exactly the distribution obtained by drawing Y ∼ ∏ e ∈ V D e Y \sim\prod_{e \in V} D_e Y ∼ ∏ e ∈ V D e and retaining each ( e , Y e ) (e,Y_e) ( e , Y e ) with e ∈ Greedy ( Y ) e \in\operatorname{Greedy}(Y) e ∈ Greedy ( Y ) independently with probability 1 / 2 1/2 1/2 .
The ratio 2 is optimal even for rank-one matroids with known distributions, by the classical prophet inequality [49 ] .
Lemma 3.2 (Feasibility). After every arrival,
A L G ⊆ Greedy ( C ) ∩ F , C ( e ) = R e for every e ∈ A L G . \mathrm{ALG} \subseteq\operatorname{Greedy}(C) \cap F,\qquad C(e) = R_e \quad\text{for every } e \in\mathrm{ALG}. ALG ⊆ Greedy ( C ) ∩ F , C ( e ) = R e for every e ∈ ALG . Proof. The statements hold initially. Any earlier acceptance removed by an update would belong to ( B ∖ B ′ ) ∩ F (B \setminus B') \cap F ( B ∖ B ′ ) ∩ F , and the override blocks exactly such an update. Thus every update preserves earlier acceptances. A newly accepted element belongs to B ′ B' B ′ and has its real value in C C C . Later steps leave its coordinate unchanged. Every arrival is added to F F F .
The snapshot lemma
As in § 2 , the snapshot C e C_e C e is the configuration that e e e faces, immediately before it is processed. Two independent draws from the same distribution can equivalently be generated by drawing their unordered pair and then assigning its entries to sample and real by a fair coin. For the next lemma, fix the arrival order and, for each e e e , the unordered pair 0 ≤ ℓ e ≤ u e 0 \le\ell_e \le u_e 0 ≤ ℓ e ≤ u e . The assignments of each pair’s entries to S e S_e S e and R e R_e R e remain independent fair coins; the algorithm’s fresh coins also remain random and are independent of these assignments. The pairs are fixed only for analysis; the algorithm does not know them before the corresponding arrivals.
Let the bit ξ e \xi_e ξ e record which endpoint currently supplies C ( e ) C(e) C ( e ) : zero means ℓ e \ell_e ℓ e and one means u e u_e u e . Distinguish the endpoint copies even when their numerical values are equal. Initially, ξ \xi ξ is uniform on { 0 , 1 } V \{0,1\}^V { 0 , 1 } V . A performed update at e e e in step 3 flips ξ e \xi_e ξ e , installing its real value. For fixed value pairs, ξ \xi ξ determines the configuration C C C , and in particular each snapshot C e C_e C e . An independent half-sample of a set is obtained by retaining each element independently with probability 1 / 2 1/2 1/2 .
Lemma 3.3 (Snapshot lemma). Fix the value pairs and arrival order. After any fixed prefix, let C C C , F F F , and ξ \xi ξ denote the current configuration, processed set, and endpoint vector. Then ξ \xi ξ is uniform on { 0 , 1 } V \{0,1\}^V { 0 , 1 } V , and conditional on ξ \xi ξ , the accepted set is an independent half-sample of Greedy ( C ) ∩ F \operatorname{Greedy}(C) \cap F Greedy ( C ) ∩ F .
Proof. Induct on the processed prefix. Initially, ξ \xi ξ is uniform and F = A L G = ∅ F = \mathrm{ALG} = \varnothing F = ALG = ∅ . Let e e e be the next element. Condition only on the current coordinates ξ − e = ( ξ f ) f ≠ e \xi_{-e} = (\xi_f)_{f \ne e} ξ − e = ( ξ f ) f = e , averaging over the preceding execution rather than fixing its decisions. Let B 0 B_0 B 0 and B 1 B_1 B 1 be the greedy bases of the configuration given by ξ − e \xi_{-e} ξ − e together with C ( e ) = ℓ e C(e) = \ell_e C ( e ) = ℓ e or C ( e ) = u e C(e) = u_e C ( e ) = u e , respectively. Both are determined by ξ − e \xi_{-e} ξ − e , and the algorithm’s current and proposed bases are B = B ξ e B = B_{\xi_e} B = B ξ e and B ′ = B 1 − ξ e B' = B_{1-\xi_e} B ′ = B 1 − ξ e . The induction hypothesis makes ξ e \xi_e ξ e fair and specifies the conditional accepted-set distribution in each orientation. Write ξ e ′ \xi'_e ξ e ′ for this bit after processing e e e . We split the analysis into two cases. Case 1: B 0 ∩ F = B 1 ∩ F B_0 \cap F = B_1 \cap F B 0 ∩ F = B 1 ∩ F . Write P = B 0 ∩ F = B 1 ∩ F P = B_0 \cap F = B_1 \cap F P = B 0 ∩ F = B 1 ∩ F . The old accepted set is an independent half-sample of P P P , independent of ξ e \xi_e ξ e . No processed element would leave the basis, so step 2 does not override the fresh fair bit Z Z Z . Step 3 flips ξ e \xi_e ξ e when Z = 1 Z = 1 Z = 1 and leaves it unchanged when Z = 0 Z = 0 Z = 0 . Thus
ξ e ′ = ( ξ e + Z ) mod 2. \xi'_e = (\xi_e + Z) \mathbin{\operatorname{mod}} 2. ξ e ′ = ( ξ e + Z ) mod 2.
The bits ξ e ′ \xi'_e ξ e ′ and Z Z Z are independent and fair, and both are independent of the old accepted set. Earlier acceptances are unchanged, and e e e is accepted exactly when Z = 1 Z = 1 Z = 1 and e ∈ B ξ e ′ e \in B_{\xi'_e} e ∈ B ξ e ′ . Thus, conditional on the new endpoint vector, the accepted set is an independent half-sample of B ξ e ′ ∩ ( F + e ) B_{\xi'_e} \cap(F + e) B ξ e ′ ∩ ( F + e ) .
Case 2: B 0 ∩ F ≠ B 1 ∩ F B_0 \cap F \ne B_1 \cap F B 0 ∩ F = B 1 ∩ F . By Lemma 2.1 (iii), increasing e e e ’s value from ℓ e \ell_e ℓ e to u e u_e u e exchanges a unique processed element f ∈ F f \in F f ∈ F for e e e : B 1 = B 0 − f + e B_1 = B_0 - f + e B 1 = B 0 − f + e . Put P = ( B 0 ∩ F ) − f = B 1 ∩ F P = (B_0 \cap F) - f = B_1 \cap F P = ( B 0 ∩ F ) − f = B 1 ∩ F , the processed elements common to both bases. By induction, the accepted subset of P P P is an independent half-sample of P P P in both orientations. Condition on this subset; then ξ e \xi_e ξ e remains fair, and only e e e and f f f remain to be tracked.
If ξ e = 0 \xi_e = 0 ξ e = 0 , the current basis is B 0 ∋ f B_0 \ni f B 0 ∋ f , and by induction f f f was accepted with probability 1 / 2 1/2 1/2 , even under this conditioning. The update would install u e u_e u e and remove the processed f f f , so step 2 overrides Z Z Z : acceptance of f f f blocks the update, while rejection of f f f forces it, and then e ∈ B 1 e \in B_1 e ∈ B 1 is accepted. If ξ e = 1 \xi_e = 1 ξ e = 1 , the current basis is B 1 ∌ f B_1 \not\ni f B 1 ∋ f , so f f f was rejected by feasibility. The update would install ℓ e \ell_e ℓ e and remove only the unprocessed e e e , so the fresh bit Z Z Z decides. Either way e e e is rejected: with Z = 0 Z = 0 Z = 0 nothing changes, and with Z = 1 Z = 1 Z = 1 the new basis B 0 B_0 B 0 excludes e e e . Hence each row below has probability 1 / 4 1/4 1/4 , conditional on the accepted subset of P P P .
Table 2.
Each new basis appears in two rows, so ξ e ′ \xi'_e ξ e ′ is fair. Given the new basis, its unique member of { e , f } \{e,f\} { e , f } is accepted in exactly one of those rows, hence with probability 1 / 2 1/2 1/2 . These probabilities hold for every accepted subset of P P P . Thus conditioning on the new basis leaves that subset an independent half-sample of P P P , independent of this additional acceptance. This gives the required distribution on B ξ e ′ ∩ ( F + e ) B_{\xi'_e} \cap(F + e) B ξ e ′ ∩ ( F + e ) .
In both cases, ξ e ′ \xi'_e ξ e ′ is fair conditional on the unchanged coordinates ξ − e \xi_{-e} ξ − e . Hence the full endpoint vector remains uniform, with the required conditional accepted-set distribution.
Corollary 3.4 (Snapshot independence). In the original sampling model, after every fixed prefix, C ∼ ∏ e ∈ V D e C \sim\prod_{e \in V} D_e C ∼ ∏ e ∈ V D e . Conditional on C = w C = w C = w , the accepted set is an independent half-sample of Greedy ( w ) ∩ F \operatorname{Greedy}(w) \cap F Greedy ( w ) ∩ F . In particular, every snapshot C e C_e C e has this product distribution for every fixed arrival order.
Proof. Generate the sample and real values as described before Lemma 3.3 ; conditional on the value pairs, the lemma applies. Averaging over the pairs gives C ∼ ∏ e ∈ V D e C \sim\prod_{e \in V} D_e C ∼ ∏ e ∈ V D e . The conditional accepted-set distribution from the lemma depends on the pairs and orientations only through the numerical configuration C C C : it is an independent half-sample of Greedy ( C ) ∩ F \operatorname{Greedy}(C) \cap F Greedy ( C ) ∩ F . It therefore persists after averaging over the pairs, even when some endpoint values are equal. ∎
The competitive guarantee
Proof of Theorem 3.1 . At the final prefix, F = V F = V F = V . By Corollary 3.4 , ( C , A L G ) (C, \mathrm{ALG}) ( C , ALG ) has the same joint distribution as a fresh product draw Y Y Y together with an independent half-sample T T T of G r e e d y ( Y ) \mathrm{Greedy}(Y) Greedy ( Y ) . By Lemma 3.2 , every accepted element has its real value stored in C C C . Consequently,
{ ( e , R e ) : e ∈ A L G } = d { ( e , Y e ) : e ∈ T } . \{(e, R_e) : e \in\mathrm{ALG}\} \overset{\mathrm{d}}{=} \{(e, Y_e) : e \in T\}. {( e , R e ) : e ∈ ALG } = d {( e , Y e ) : e ∈ T } .
Taking expected total values, which are nonnegative, and using greedy optimality gives the claimed expected-value identity. The distributional identity uses a fresh draw Y Y Y ; the output need not be a half-sample of the optimum of the realized values ( R e ) e ∈ V (R_e)_{e \in V} ( R e ) e ∈ V .
Every decision uses only the samples, the current real value, earlier observations, and fair coins, so no distributional knowledge is needed. Since the algorithm stores B B B , it computes one new greedy basis per arrival: at most n + 1 n + 1 n + 1 greedy scans, hence n ( n + 1 ) n(n + 1) n ( n + 1 ) independence queries.
Polyhedral Characterization of Ordinal Secretary Algorithms
The preceding sections construct algorithms by preserving suitable distributions. We now characterize exactly the accepted-set distributions achievable by ordinal secretary algorithms on a fixed known matroid: they form a finite polytope, and every feasible point yields an online algorithm. Constraints on the terminal distribution , the accepted-set distribution after all arrivals, give exact LPs over ordinal algorithms, which we use to study small matroids (§ 7.1 and Appendix § 11 ). Analytically, the continuous-time version reduces the design of our optimal algorithm to constructing feasible distributions (§ 5 and § 6 ).
Fix a matroid M = ( V , I ) \mathcal{M} = (V, \mathcal{I}) M = ( V , I ) with n n n elements and positive rank. Values are fixed and nonnegative, arrivals form a uniformly random permutation, and ties are broken by a fixed order of labels. An algorithm is ordinal if it uses values only through the tie-broken order among observed elements; it may otherwise use its entire history and internal randomness. The characterization allows advance knowledge of the matroid; the family in § 5 uses only its observed restriction.
Distributions and feasible transitions
We describe an ordinal algorithm by two families of numbers: the distribution of its accepted set given the elements observed so far, and the probability mass it moves at each arrival. Since an ordinal algorithm sees only the relative order of values, both are indexed by ordered sets. An ordered set O O O is a subset of V V V equipped with its decreasing-value order, not its arrival order. We use the same symbol for its underlying set, and O − e O-e O − e inherits the restricted order. Write ω \omega ω for a full value order, identified with the ordered set V V V , and Greedy ( O ) \operatorname{Greedy}(O) Greedy ( O ) for the greedy basis under the order of O O O .
Write A L G m \mathrm{ALG}_m ALG m for the set accepted after the first m m m arrivals. For an ordered set O O O of size m m m , the accepted-set distribution μ O \mu_O μ O is the intended conditional distribution of A L G m \mathrm{ALG}_m ALG m , with probabilities
μ O ( A ) = Pr [ A L G m = A ∣ the first m arrivals form O ] . (1) \mu_O(A) = \Pr[\mathrm{ALG}_m = A \mid\text{the first }m\text{ arrivals form }O]. \tag*{(1)} μ O ( A ) = Pr [ ALG m = A ∣ the first m arrivals form O ] . (1)
It averages over the uniform arrival order on O O O and the algorithm’s randomness, and is the same for every full value order extending O O O , since an ordinal algorithm cannot see unobserved comparisons.
For e ∈ O e \in O e ∈ O and A ⊆ O − e A \subseteq O-e A ⊆ O − e , the accepting mass y O , e ( A ) y_{O,e}(A) y O , e ( A ) is the probability that the previous accepted set is A A A and e e e is accepted, conditional on the first ∣ O ∣ |O| ∣ O ∣ arrivals forming O O O and the last arrival being e e e . Thus y O , e ( A ) y_{O,e}(A) y O , e ( A ) is the probability mass moved from A A A to A + e A+e A + e . Using these joint probabilities, rather than acceptance probabilities, keeps the constraints linear; the corresponding acceptance rule from accepted set A A A is
q O , e ( A ) = y O , e ( A ) μ O − e ( A ) , with 0 / 0 = 0. (2) q_{O,e}(A)=\frac{y_{O,e}(A)}{\mu_{O-e}(A)},\qquad\text{with }0/0=0. \tag*{(2)} q O , e ( A ) = μ O − e ( A ) y O , e ( A ) , with 0/0 = 0. (2)
All entries outside their stated supports are zero. Two linear conditions constrain these numbers.
Capacity. Only available mass can be moved, and an accepted extension must remain independent. Hence, for e ∈ O e\in O e ∈ O and A ⊆ O − e A\subseteq O-e A ⊆ O − e ,
0 ≤ y O , e ( A ) ≤ μ O − e ( A ) , y O , e ( A ) = 0 if A + e ∉ I . (3) 0\le y_{O,e}(A)\le\mu_{O-e}(A),\qquad y_{O,e}(A)=0\text{ if }A+e\notin\mathcal{I}. \tag*{(3)} 0 ≤ y O , e ( A ) ≤ μ O − e ( A ) , y O , e ( A ) = 0 if A + e ∈ / I . (3)
Consistency. Conditional on the first ∣ O ∣ |O| ∣ O ∣ arrivals forming O O O , the last element is uniform in O O O . To finish with a particular set A A A , an element e ∉ A e\notin A e ∈ / A must be rejected from A A A , whereas e ∈ A e\in A e ∈ A must be accepted from A − e A-e A − e . Therefore, for every nonempty O O O and A ⊆ O A\subseteq O A ⊆ O ,
μ O ( A ) = 1 ∣ O ∣ [ ∑ e ∈ O ∖ A ( μ O − e ( A ) − y O , e ( A ) ) + ∑ e ∈ A y O , e ( A − e ) ] . (4) \mu_O(A)=\frac{1}{|O|}\left[\sum_{e\in O\setminus A}\left(\mu_{O-e}(A)-y_{O,e}(A)\right)+\sum_{e\in A}y_{O,e}(A-e)\right]. \tag*{(4)} μ O ( A ) = ∣ O ∣ 1 e ∈ O ∖ A ∑ ( μ O − e ( A ) − y O , e ( A ) ) + e ∈ A ∑ y O , e ( A − e ) . (4)
This equation enforces irreversibility. For example, in rank one, the family that always places all mass on the best observed element cannot satisfy it: accepting a first element leaves no way to replace it when a larger element arrives.
Let P ( M ) \mathcal{P}(\mathcal{M}) P ( M ) be the polytope of families ( μ , y ) (\mu,y) ( μ , y ) with μ O \mu_O μ O supported on independent subsets of O O O and satisfying
μ ∅ ( ∅ ) = 1 , μ O ( A ) ≥ 0 , ∑ A ⊆ O μ O ( A ) = 1 for every O , capacity x r e f ‘ ( 3 ) ‘ , consistency x r e f ‘ ( 4 ) ‘ . (5) \begin{aligned}
\mu_{\varnothing}(\varnothing)&=1,\qquad\mu_O(A)\ge0,\qquad\sum_{A\subseteq O}\mu_O(A)=1\quad\text{for every }O,\\
&\text{capacity }{xref}`(3)`,\\
&\text{consistency }{xref}`(4)`. \tag*{(5)}
\end{aligned} μ ∅ ( ∅ ) = 1 , μ O ( A ) ≥ 0 , A ⊆ O ∑ μ O ( A ) = 1 for every O , capacity x r e f ‘ ( 3 ) ‘ , consistency x r e f ‘ ( 4 ) ‘. (5)
Theorem 4.1 (Exact characterization). The points of P ( M ) \mathcal{P}(\mathcal{M}) P ( M ) are exactly the accepted-set distributions and accepting masses of ordinal algorithms. Every point ( μ , y ) (\mu,y) ( μ , y ) is realized by the rule (2) , which uses only the observed ordered set, the current arrival, and the previously accepted set.
Proof. For necessity, fix an ordinal algorithm and a full value order. Conditional on the preceding observed set being O − e O-e O − e , learning that the next arrival is e e e does not change the uniform order of those preceding arrivals or the distribution of past internal randomness. The preceding accepted set therefore has distribution μ O − e \mu_{O-e} μ O − e . Its accepting masses satisfy capacity, and averaging the two possible transitions to each A A A over the uniform last arrival gives consistency. Normalization and independent support are immediate.
Conversely, fix ( μ , y ) ∈ P ( M ) (\mu,y)\in\mathcal{P}(\mathcal{M}) ( μ , y ) ∈ P ( M ) and apply (2) at each arrival. Capacity makes this a feasible probability and preserves independence. Induct on m m m to prove that the conditional distribution after m m m arrivals is μ O \mu_O μ O . The claim is immediate for m = 0 m=0 m = 0 . Conditional on a nonempty observed set O O O and last arrival e e e , the induction hypothesis gives preceding distribution μ O − e \mu_{O-e} μ O − e . The rule moves exactly y O , e ( B ) y_{O,e}(B) y O , e ( B ) from each B B B to B + e B+e B + e , including when μ O − e ( B ) = 0 \mu_{O-e}(B)=0 μ O − e ( B ) = 0 , since then capacity forces y O , e ( B ) = 0 y_{O,e}(B)=0 y O , e ( B ) = 0 . Averaging over e e e gives μ O ( A ) \mu_O(A) μ O ( A ) by (4) . This also proves that every accepting mass is the prescribed y O , e ( B ) y_{O,e}(B) y O , e ( B ) . ∎
Thus an ordinal algorithm gains nothing from remembering the arrival order of earlier elements: the rule (2) realizes its accepted-set distributions using only O O O , e e e , and A A A . This justifies indexing the variables by ordered sets rather than arrival sequences. For example, Algorithm 1 induces a feasible point whose terminal distribution includes every optimum element with probability at least 1 / 4 1/4 1/4 .
Remark (Scope of the realization theorem). The proof of Theorem 4.1 applies to any known downward-closed feasibility family, with “independent” replaced by “feasible.” The matroid-specific work lies in constructing distributions that satisfy capacity and consistency, and in implementing them efficiently (Lemmas 5.3 and 6.2 ). The prefix objective in Corollary 4.3 uses greedy optimality and is stated only for matroids.
Optimal competitive guarantees
Both competitive guarantees below can be expressed as linear constraints on the terminal distributions μ ω \mu_\omega μ ω , the distributions of the final accepted set A L G n \mathrm{ALG}_n ALG n for each full value order ω \omega ω . Thus Theorem 4.1 turns the search for optimal ordinal algorithms into linear programs.
Let ρ ( M ) \rho(\mathcal{M}) ρ ( M ) be the infimum probability-competitive ratio among ordinal algorithms for the known matroid M \mathcal{M} M . Equivalently, 1 / ρ ( M ) 1/\rho(\mathcal{M}) 1/ ρ ( M ) is the largest fraction γ \gamma γ for which one such algorithm selects every element of Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) with probability at least γ \gamma γ , for every value assignment. The per-element guarantee therefore gives the LP
maximize γ subject to γ ≥ 0 , ( μ , y ) ∈ P ( M ) , ∑ A ⊆ V e ∈ A μ ω ( A ) ≥ γ for every ω , e ∈ Greedy ( ω ) . (6) \begin{aligned}
\text{maximize}\quad& \gamma\\
\text{subject to}\quad& \gamma\ge0,\qquad(\mu,y) \in\mathcal{P}(\mathcal{M}), \\
& \sum_{\substack{A\subseteq V\\ e\in A}} \mu_\omega(A) \ge\gamma
\qquad\text{for every }\omega,\ e\in\operatorname{Greedy}(\omega). \tag*{(6)}
\end{aligned} maximize subject to γ γ ≥ 0 , ( μ , y ) ∈ P ( M ) , A ⊆ V e ∈ A ∑ μ ω ( A ) ≥ γ for every ω , e ∈ Greedy ( ω ) . (6)
Corollary 4.2 (Probability competitiveness). The value of (6) is 1 / ρ ( M ) 1/\rho(\mathcal{M}) 1/ ρ ( M ) , and an optimum is attained. A feasible point of value γ > 0 \gamma>0 γ > 0 yields a ( 1 / γ ) (1/\gamma) ( 1/ γ ) -probability-competitive algorithm by (2) .
Proof. Both directions follow from Theorem 4.1 and the terminal inclusion constraints. The feasible region is nonempty and compact: all entries and γ \gamma γ lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Its optimum is positive: accepting the element at a uniform arrival position, if it is a nonloop, gives 1 / n 1/n 1/ n .
The expected-value objective leads to a similar LP. Let ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) be the infimum expected-value competitive ratio among ordinal algorithms, the ordinal competitive ratio . Following [66 ] , consider each prefix P P P of the decreasing-value order ω \omega ω , consisting of its largest elements. The prefix constraints below require the algorithm to select, in expectation, a γ \gamma γ fraction of the maximum feasible number of elements from every such prefix.
Corollary 4.3 (Ordinal competitiveness). The largest expected-value fraction γ = 1 / ρ o r d ( M ) \gamma=1/\rho_{\mathrm{ord}}(\mathcal{M}) γ = 1/ ρ ord ( M ) achievable by an ordinal algorithm is the value of (6) with its terminal constraints replaced by
∑ A ⊆ V ∣ A ∩ P ∣ μ ω ( A ) ≥ γ rank ( P ) for every full order ω and prefix P of ω . (7) \sum_{A\subseteq V} |A\cap P|\,\mu_\omega(A) \ge\gamma\operatorname{rank}(P)
\qquad\text{for every full order }\omega\text{ and prefix }P\text{ of }\omega. \tag*{(7)} A ⊆ V ∑ ∣ A ∩ P ∣ μ ω ( A ) ≥ γ rank ( P ) for every full order ω and prefix P of ω . (7) An optimum is attained and is realized by (2) .
Proof. For a fixed order, nonnegative values are nonnegative combinations of prefix indicators, and ∣ Greedy ( ω ) ∩ P ∣ = rank ( P ) |\operatorname{Greedy}(\omega)\cap P|=\operatorname{rank}(P) ∣ Greedy ( ω ) ∩ P ∣ = rank ( P ) by greedy. Thus the prefix inequalities imply the expected-value guarantee. Conversely, approximate a prefix indicator by strictly ordered values with the same order; the algorithm’s distribution stays fixed, so the guarantee implies the prefix inequality in the limit. This is the prefix characterization of Soto, Turkieltaub, and Verdugo [66 ] . Apply Theorem 4.1; compactness is as above.
The probability constraints imply the prefix constraints by summing over Greedy ( ω ) ∩ P \operatorname{Greedy}(\omega) \cap P Greedy ( ω ) ∩ P , so ρ o r d ( M ) ≤ ρ ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) \le\rho(\mathcal{M}) ρ ord ( M ) ≤ ρ ( M ) . § 7.1 applies these programs to special classes. For our optimal construction, we now pass to continuous time, where the distributions also vary with time.
Continuous-time acceptance distributions
For the construction in § 5 and § 6 , it is convenient to express the characterization of Theorem 4.1 in continuous time. In the continuous-time model , each element e e e arrives at an independent uniform time T e ∈ [ 0 , 1 ] T_e \in[0,1] T e ∈ [ 0 , 1 ] . The algorithm observes this time when e e e arrives and immediately accepts or rejects e e e , using only observations so far and independent private randomness. When n n n is known, any algorithm in this model can be simulated in the ordinary secretary model: independently sample and sort n n n uniform times, and reveal the next time to the algorithm at each arrival. Conversely, an ordinary secretary algorithm can ignore the times. The same capacity and consistency principles therefore apply, now averaging over the last arrival’s time as well as its identity.
For 0 < t < 1 0 < t < 1 0 < t < 1 , the accepted-set distribution D O , t \mathcal{D}_{O,t} D O , t is the intended distribution of the accepted set, conditional on precisely the ordered set O O O having arrived by t t t . The accepting mass z O , e , t ( A ) z_{O,e,t}(A) z O , e , t ( A ) is the joint probability that the previous accepted set is A A A and e e e is accepted, conditional on e e e arriving at time t t t with preceding observed set O − e O-e O − e .9 These are the continuous-time counterparts of μ O \mu_O μ O and y O , e y_{O,e} y O , e ; as before, they are shared by all full value orders extending O O O . Each D O , t \mathcal{D}_{O,t} D O , t is a probability distribution on independent subsets of O O O , with D ∅ , t ( ∅ ) = 1 \mathcal{D}_{\varnothing,t}(\varnothing)=1 D ∅ , t ( ∅ ) = 1 . We define D O , 1 \mathcal{D}_{O,1} D O , 1 by continuity. In particular, D V , 1 \mathcal{D}_{V,1} D V , 1 is the terminal distribution, since all elements have arrived by time 1 1 1 .
Capacity. For e ∈ O e \in O e ∈ O and A ⊆ O − e A \subseteq O-e A ⊆ O − e , the measurable accepting masses must satisfy
0 ≤ z O , e , t ( A ) ≤ D O − e , t ( A ) , z O , e , t ( A ) = 0 if A + e ∉ I . (8) 0 \le z_{O,e,t}(A) \le\mathcal{D}_{O-e,t}(A), \qquad z_{O,e,t}(A)=0 \ \text{if } A+e \notin\mathcal{I}. \tag*{(8)} 0 ≤ z O , e , t ( A ) ≤ D O − e , t ( A ) , z O , e , t ( A ) = 0 if A + e ∈ / I . (8)
Consistency. Averaging over the last arrival gives, for m = ∣ O ∣ > 0 m=|O|>0 m = ∣ O ∣ > 0 , A ⊆ O A \subseteq O A ⊆ O , and 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 ,
t m D O , t ( A ) = ∫ 0 t u m − 1 [ ∑ e ∈ O ∖ A ( D O − e , u ( A ) − z O , e , u ( A ) ) + ∑ e ∈ A z O , e , u ( A − e ) ] d u . (9) t^m\mathcal{D}_{O,t}(A)=\int_0^t u^{m-1}\left[\sum_{e\in O\setminus A}\left(\mathcal{D}_{O-e,u}(A)-z_{O,e,u}(A)\right)+\sum_{e\in A}z_{O,e,u}(A-e)\right]\,du. \tag*{(9)} t m D O , t ( A ) = ∫ 0 t u m − 1 e ∈ O ∖ A ∑ ( D O − e , u ( A ) − z O , e , u ( A ) ) + e ∈ A ∑ z O , e , u ( A − e ) d u . (9)
Theorem 4.4 (Continuous-time realization). The accepted-set distributions D O , t \mathcal{D}_{O,t} D O , t and accepting masses z O , e , t ( A ) z_{O,e,t}(A) z O , e , t ( A ) are realizable by an ordinal algorithm in the continuous-time model if and only if they satisfy capacity (8) and consistency (9). Call such a family feasible; every feasible family is realized by accepting the current arrival e e e at time t t t , from accepted set A A A , with probability
q O , e , t ( A ) = z O , e , t ( A ) D O − e , t ( A ) , with 0 / 0 = 0. (10) q_{O,e,t}(A)=\frac{z_{O,e,t}(A)}{\mathcal{D}_{O-e,t}(A)}, \qquad\text{with } 0/0=0. \tag*{(10)} q O , e , t ( A ) = D O − e , t ( A ) z O , e , t ( A ) , with 0/0 = 0. (10)
Proof. Necessity of capacity is as in the discrete formulation.
For consistency, fix a nonempty O O O , let m = ∣ O ∣ m=|O| m = ∣ O ∣ , and condition on precisely O O O having arrived by t t t . Under this conditioning, its arrival times are independent uniforms on [ 0 , t ] [0,t] [ 0 , t ] . For a specified element e ∈ O e \in O e ∈ O to be last at time u u u , its own arrival time contributes density 1 / t 1/t 1/ t , while all other m − 1 m-1 m − 1 arrival times must be at most u u u , an event of probability ( u / t ) m − 1 (u/t)^{m-1} ( u / t ) m − 1 . Thus the joint density of the last identity e e e and its time u u u is ( 1 / t ) ( u / t ) m − 1 = u m − 1 / t m (1/t)(u/t)^{m-1}=u^{m-1}/t^m ( 1/ t ) ( u / t ) m − 1 = u m − 1 / t m . Conditional on this last arrival, the preceding arrival times are independent uniforms on [ 0 , u ] [0,u] [ 0 , u ] . The observations before u u u therefore have the same distribution as when precisely O − e O-e O − e has arrived by u u u . Since decisions cannot depend on future arrivals, the accepted set immediately before e e e arrives has distribution D O − e , u \mathcal{D}_{O-e,u} D O − e , u .
Fix A ⊆ O A \subseteq O A ⊆ O . If e ∉ A e \notin A e ∈ / A , ending in A A A requires the preceding accepted set to be A A A and e e e to be rejected. This has probability D O − e , u ( A ) − z O , e , u ( A ) \mathcal{D}_{O-e,u}(A)-z_{O,e,u}(A) D O − e , u ( A ) − z O , e , u ( A ) . If e ∈ A e \in A e ∈ A , the preceding set must be A − e A-e A − e and e e e must be accepted, with probability z O , e , u ( A − e ) z_{O,e,u}(A-e) z O , e , u ( A − e ) . Summing over the last element e e e , integrating over its time u ∈ [ 0 , t ] u \in[0,t] u ∈ [ 0 , t ] , and multiplying by t m t^m t m gives (9) .
Conversely, use (10) , which is feasible by capacity. Induct on ∣ O ∣ |O| ∣ O ∣ , starting from the empty set. Once the preceding distributions are realized, the joint masses are D O − e , u ( A ) q O , e , u ( A ) = z O , e , u ( A ) \mathcal{D}_{O-e,u}(A)q_{O,e,u}(A)=z_{O,e,u}(A) D O − e , u ( A ) q O , e , u ( A ) = z O , e , u ( A ) . The same last-arrival calculation gives (9) , so the resulting distribution is D O , t \mathcal{D}_{O,t} D O , t . Continuity gives the terminal distribution at t = 1 t=1 t = 1 .
If the distributions and masses depend only on n n n , the current time, the observed order, and the arrived matroid restriction, so does the realizing rule. The next two sections construct such a family and implement it efficiently.
A Feasible Family with Guarantee 1 / e 1/e 1/ e
We now construct a feasible family for § 4.3 in two steps. First, an offline experiment on an ordered set O O O at horizon t t t defines the survivor distribution D O , t \mathcal{D}_{O,t} D O , t over independent sets, our target accepted-set distribution. The experiment is not an online selection rule: its auxiliary arrival times are independent of actual arrivals, and its survival decisions are not online acceptances. Second, we prescribe accepting masses z O , e , t ( A ) z_{O,e,t}(A) z O , e , t ( A ) and prove capacity and consistency. Theorem 4.4 then gives an online algorithm whose accepted set, conditional on precisely O O O having arrived by t t t , has distribution D O , t \mathcal{D}_{O,t} D O , t . The resulting guarantee already resolves the strong matroid secretary conjecture. § 6 gives an efficient implementation without evaluating probabilities of entire survivor sets.
The survivor distributions
Motivation from rank one. Fix p ∈ [ 1 / e , 1 ) p \in[1/e,1) p ∈ [ 1/ e , 1 ) throughout. The classical single-item secretary rule in the continuous-time model rejects arrivals before p p p , then selects the first subsequent element larger than all earlier arrivals. Suppose e e e arrives at t > p t>p t > p , is larger than every predecessor, and has at least one predecessor. It is selected exactly when the largest predecessor arrived before p p p . Conditional on the predecessor set and t t t , the largest predecessor’s arrival time is uniform on [ 0 , t ] [0,t] [ 0 , t ] . Hence e e e is selected with probability p / t p/t p / t .10 This averages over earlier arrival times; it is not conditional on having made no selection.
For a matroid, let O O O contain the elements observed up to and including the current arrival e e e , ordered by value. Call e e e eligible if e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) , or equivalently if the larger observed elements do not span it. This generalizes being larger than all predecessors in rank one. We target acceptance probability p / t p/t p / t for each eligible arrival at t > p t>p t > p , conditional on O O O , e e e , and t t t but averaged over earlier arrival times and decisions. By greedy monotonicity (Lemma 2.1 (i)), every global optimum element is eligible whenever it arrives, giving the target selection probability
∫ p 1 p t d t = p ln ( 1 / p ) . (11) \int_{p}^{1} \frac{p}{t}\,\mathrm{d}t = p\ln(1/p). \tag*{(11)} ∫ p 1 t p d t = p ln ( 1/ p ) . (11)
This is maximized at p = 1 / e p = 1/e p = 1/ e . The challenge is to achieve these probabilities while keeping the accepted set independent. We first construct a survivor set, always independent in M \mathcal{M} M , with these inclusion probabilities, then realize its distribution online as an accepted-set distribution.
Definition 5.1 (Survivor distribution D O , t \mathcal{D}_{O,t} D O , t ). For an ordered set O O O and horizon t ∈ [ p , 1 ] t \in[p,1] t ∈ [ p , 1 ] , perform the following offline survivor experiment :
Draw independent auxiliary times T e ′ ∼ Unif [ 0 , t ] T'_e \sim\operatorname{Unif}[0,t] T e ′ ∼ Unif [ 0 , t ] for e ∈ O e \in O e ∈ O . Set E = { e ∈ O : T e ′ ≤ p } E = \{e \in O : T'_e \le p\} E = { e ∈ O : T e ′ ≤ p } . Call these elements early and the others late .
For each e ∈ O e \in O e ∈ O , let its capped spanning time σ e \sigma_e σ e be the first time u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] when the larger elements already present in the survivor experiment span e e e . These are the elements { f ∈ O : f ≻ e , T f ′ ≤ u } \{f \in O : f \succ e, T'_f \le u\} { f ∈ O : f ≻ e , T f ′ ≤ u } , where f ≻ e f \succ e f ≻ e means that f f f is larger in the tie-broken value order. Set σ e = t \sigma_e = t σ e = t if they never span e e e by t t t .
Conditional on all auxiliary times, each early element e e e survives independently with probability ln ( σ e / p ) \ln(\sigma_e/p) ln ( σ e / p ) , its conditional survival probability . No late element survives.
The surviving elements form the survivor set , with distribution D O , t \mathcal{D}_{O,t} D O , t and output probabilities D O , t ( A ) \mathcal{D}_{O,t}(A) D O , t ( A ) . For 0 < t ≤ p 0 < t \le p 0 < t ≤ p or O = ∅ O = \varnothing O = ∅ , D O , t \mathcal{D}_{O,t} D O , t is the point mass at ∅ \varnothing ∅ .
We choose the logarithm in step 3 to reproduce the rank-one integral (11) , stopped when larger elements span e e e : an eligible arrival at time u > p u > p u > p should be accepted with probability p / u p/u p / u , and e e e remains eligible until σ e \sigma_e σ e . At horizon 1, the larger elements’ auxiliary times fix σ e \sigma_e σ e but not T e ′ T'_e T e ′ , so e e e is still early with probability p p p . Its survival probability is therefore p ln ( σ e / p ) = ∫ p σ e ( p / u ) d u p\ln(\sigma_e/p) = \int_p^{\sigma_e} (p/u)\,\mathrm{d}u p ln ( σ e / p ) = ∫ p σ e ( p / u ) d u : early sampling supplies the factor p p p , and step 3 the logarithm.
In step 2, all larger elements present contribute to spanning, whether or not they survive. Since p ≤ σ e ≤ 1 p \le\sigma_e \le1 p ≤ σ e ≤ 1 and p ≥ 1 / e p \ge1/e p ≥ 1/ e , the conditional survival probabilities lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] . An early element outside Greedy ( E ) \operatorname{Greedy}(E) Greedy ( E ) has σ e = p \sigma_e = p σ e = p and cannot survive. Thus the survivor set is a subset of Greedy ( E ) \operatorname{Greedy}(E) Greedy ( E ) and is independent.
The accepting masses z O , e , t z_{O,e,t} z O , e , t . Recall from § 4.3 that z O , e , t ( A ) z_{O,e,t}(A) z O , e , t ( A ) specifies the joint probability of the preceding accepted set being A A A and accepting e e e , conditional on the observed ordered set O O O and the arrival of e e e at time t t t . For a nonloop e e e , the contraction M / e \mathcal{M}/e M / e has independent sets A ⊆ V − e A \subseteq V-e A ⊆ V − e with A + e ∈ I A+e \in\mathcal{I} A + e ∈ I . A set S S S spans f ≠ e f \ne e f = e in M / e \mathcal{M}/e M / e exactly when S + e S+e S + e spans f f f in M \mathcal{M} M . For any ordered set T ⊆ V − e T \subseteq V-e T ⊆ V − e , let D T , t , e \mathcal{D}_{T,t,e} D T , t , e denote the survivor distribution on T T T in M / e \mathcal{M}/e M / e , with the restricted value order. To determine whether f f f is spanned, this experiment adds e e e to the larger elements present, regardless of how e e e compares with f f f .
Every output A A A can be extended by e e e . We therefore use the contracted survivor distribution to allocate the target probability p / t p/t p / t among feasible predecessor sets:
z O , e , t ( A ) = { p t D O − e , t , e ( A ) , t > p and e ∈ Greedy ( O ) , 0 , otherwise . (12) z_{O,e,t}(A) =
\begin{cases}
\frac{p}{t}\mathcal{D}_{O-e,t,e}(A), & t > p \text{ and } e \in\operatorname{Greedy}(O),\\
0, & \text{otherwise}.
\end{cases} \tag*{(12)} z O , e , t ( A ) = { t p D O − e , t , e ( A ) , 0 , t > p and e ∈ Greedy ( O ) , otherwise . (12)
For an eligible arrival at t > p t > p t > p , summing over predecessor sets gives ∑ A z O , e , t ( A ) = p / t \sum_A z_{O,e,t}(A) = p/t ∑ A z O , e , t ( A ) = p / t , matching the rank-one target. This choice will also give consistency in § 5.3 : with auxiliary times fixed, an early e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) has conditional survival probability ln ( t / p ) \ln(t/p) ln ( t / p ) , with derivative 1 / t 1/t 1/ t . Averaging over auxiliary times gives the z z z -terms in (9) . The realizing rule divides z O , e , t ( A ) z_{O,e,t}(A) z O , e , t ( A ) by D O − e , t ( A ) D_{O-e,t}(A) D O − e , t ( A ) to obtain the acceptance probability from set A A A , as in (10) ; capacity bounds it by 1 1 1 .
Theorem 5.2 (Feasible survivor distributions). With z z z given by (12) , the survivor distributions satisfy capacity (8) and consistency (9) . Hence Algorithm 3 is ordinal and accepts the elements of Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) independently, each with probability p ln ( 1 / p ) p\ln(1/p) p ln ( 1/ p ) , which equals 1 / e 1/e 1/ e for p = 1 / e p=1/e p = 1/ e .
Algorithm 3 Survival secretary rule
Initialize A L G = ∅ \mathrm{ALG} = \varnothing ALG = ∅ , and generate arrival times in the continuous-time model (§ 4.3 ).
When e e e arrives at time t t t , let O O O be the arrived set, including e e e . If t > p t > p t > p and e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) , accept e e e with probability
p t ⋅ D O − e , t , e ( A L G ) D O − e , t ( A L G ) \frac{p}{t} \cdot\frac{D_{O-e,t,e}(\mathrm{ALG})}{D_{O-e,t}(\mathrm{ALG})} t p ⋅ D O − e , t ( ALG ) D O − e , t , e ( ALG )
(with 0 / 0 = 0 0/0=0 0/0 = 0 ),
and reject it otherwise. On acceptance, set A L G ← A L G + e \mathrm{ALG} \leftarrow\mathrm{ALG}+e ALG ← ALG + e .
Why this resolves the strong conjecture. For t ∈ [ p , 1 ] t \in[p,1] t ∈ [ p , 1 ] and every e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) , the larger elements never span e e e , so σ e = t \sigma_e=t σ e = t regardless of the auxiliary times. Conditional on being early, e e e survives with the fixed probability ln ( t / p ) \ln(t/p) ln ( t / p ) . The early indicators are independent, each with probability p / t p/t p / t , and the survival coins are independent. Thus the optimum elements survive independently, each with probability ( p / t ) ln ( t / p ) (p/t)\ln(t/p) ( p / t ) ln ( t / p ) .
At t = 1 t=1 t = 1 and p = 1 / e p=1/e p = 1/ e , an optimum element survives surely when early, giving independent inclusion with probability 1 / e 1/e 1/ e . Once capacity and consistency are proved in § 5.2 and § 5.3 , Theorem 4.4 transfers this guarantee to an ordinal online algorithm. Observe that the algorithm may also accept elements outside Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) .
Continuous-time capacity
For an ordered set O O O and a nonloop e ∉ O e \notin O e ∈ / O , we need to show that
D O , t ( A ) ≥ p t D O , t , e ( A ) ( A ⊆ O , t ∈ [ p , 1 ] ) . (13) D_{O,t}(A) \ge\frac{p}{t}D_{O,t,e}(A) \qquad(A \subseteq O,\ t \in[p,1]). \tag*{(13)} D O , t ( A ) ≥ t p D O , t , e ( A ) ( A ⊆ O , t ∈ [ p , 1 ]) . (13)
Applied to the predecessor set, this says that the mass prescribed for accepting e e e is available in each state A A A .
To prove this, we would like to induct on ∣ O ∣ |O| ∣ O ∣ , removing its largest element f f f after conditioning on its auxiliary arrival time. We handle f f f ’s survival separately and apply induction to O − f O-f O − f . However, simply deleting f f f would change the remaining elements’ spanning times: once present, f f f contributes to spanning smaller elements whether or not it survives. We therefore strengthen the induction hypothesis to allow background elements with fixed auxiliary arrival times.
Background elements. Choose some elements of V ∖ O V \setminus O V ∖ O and assign them fixed auxiliary arrival times in [ 0 , t ] [0,t] [ 0 , t ] . For u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] , let H u H_u H u be those whose auxiliary times are at most u u u , and write H = ( H u ) u ∈ [ p , t ] H=(H_u)_{u\in[p,t]} H = ( H u ) u ∈ [ p , t ] for this background schedule . Background elements contribute to spanning once present, regardless of their values, but are not candidates for survival.
For each f ∈ O f \in O f ∈ O , its spanning time is now the first u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] at which
H u ∪ { f ′ ∈ O : f ′ ≻ f , T f ′ ′ ≤ u } H_u \cup\{f' \in O: f' \succ f,\ T_{f'}' \le u\} H u ∪ { f ′ ∈ O : f ′ ≻ f , T f ′ ′ ≤ u }
spans f f f , or t t t if this never occurs. All other parts of the survivor experiment are unchanged. Denote its distribution by D O , t , H \mathcal{D}_{O,t,H} D O , t , H : the background is fixed, while the auxiliary times of elements in O O O remain independent uniforms on [ 0 , t ] [0,t] [ 0 , t ] , and their survival coins remain random. Empty background is omitted from the notation. A constant background H u = { e } H_u = \{e\} H u = { e } is denoted by e e e ; for a nonloop e e e , this gives the contracted experiment in M / e \mathcal{M}/e M / e .
Let σ a , H \sigma_{a,H} σ a , H be the first u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] at which H u H_u H u spans a a a , or t t t if this never occurs. For a ∉ O a \notin O a ∈ / O , write H a , u H^{a,u} H a , u for adding a a a to the background with auxiliary time u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] , and abbreviate H + a = H a , p H + a = H^{a,p} H + a = H a , p . If a a a is already in the background, keep the earlier of its old and new auxiliary times.
Lemma 5.3 (Capacity comparison). For every background schedule H H H disjoint from O O O , every e ∉ O e \notin O e ∈ / O (possibly already in the background, in which case H + e H + e H + e lowers its auxiliary time to p p p ), and every A ⊆ O A \subseteq O A ⊆ O ,
D O , t , H ( A ) ≥ p σ e , H D O , t , H + e ( A ) . (14) \mathcal{D}_{O,t,H}(A) \ge\frac{p}{\sigma_{e,H}}\mathcal{D}_{O,t,H+e}(A). \tag*{(14)} D O , t , H ( A ) ≥ σ e , H p D O , t , H + e ( A ) . (14)
With empty background and a nonloop e e e , σ e , H = t \sigma_{e,H} = t σ e , H = t , giving the desired capacity bound with factor p / t p/t p / t in (13) .
Proof. We induct on ∣ O ∣ |O| ∣ O ∣ , assuming the comparison for every smaller candidate set, every fixed background, and every element outside that set. The empty case is immediate: both experiments output ∅ \varnothing ∅ and p / σ e , H ≤ 1 p/\sigma_{e,H} \le1 p / σ e , H ≤ 1 .
Condition on the largest element. Let f f f be the largest element of O O O and fix A ⊆ O − f A \subseteq O - f A ⊆ O − f . To shorten the formulas, write P J ( A ) = D O − f , t , J ( A ) P_J(A) = \mathcal{D}_{O-f,t,J}(A) P J ( A ) = D O − f , t , J ( A ) for the smaller experiment with background J J J . The induction hypothesis applies to these distributions on O − f O - f O − f . The induction step must show
D O , t , H ( B ) ≥ p σ e , H D O , t , H + e ( B ) (15) \mathcal{D}_{O,t,H}(B) \ge\frac{p}{\sigma_{e,H}}\mathcal{D}_{O,t,H+e}(B) \tag*{(15)} D O , t , H ( B ) ≥ σ e , H p D O , t , H + e ( B ) (15)
for B = A B = A B = A and B = A + f B = A + f B = A + f .
We first express these probabilities by conditioning on f f f . Let
s 0 = σ f , H , s 1 = σ f , H + e ≤ s 0 . s_0 = \sigma_{f,H}, \qquad s_1 = \sigma_{f,H+e} \le s_0. s 0 = σ f , H , s 1 = σ f , H + e ≤ s 0 .
Since f f f is largest in O O O , its spanning time depends only on the background. If it is early, it survives with probability ln ( s 0 / p ) \ln(s_0/p) ln ( s 0 / p ) , while the remaining experiment has background H + f H + f H + f whether or not it survives: every early f f f is present throughout [ p , t ] [p,t] [ p , t ] . If its auxiliary arrival time is u > p u > p u > p , it cannot survive, and the remaining background is H f , u H^{f,u} H f , u . Hence
D O , t , H ( A + f ) = p t ln ( s 0 / p ) P H + f ( A ) . (16) \mathcal{D}_{O,t,H}(A + f) = \frac{p}{t}\ln(s_0/p)P_{H+f}(A). \tag*{(16)} D O , t , H ( A + f ) = t p ln ( s 0 / p ) P H + f ( A ) . (16)
D O , t , H ( A ) = p t ( 1 − ln ( s 0 / p ) ) P H + f ( A ) + 1 t ∫ p t P H f , u ( A ) d u . (17) \mathcal{D}_{O,t,H}(A) = \frac{p}{t}(1-\ln(s_0/p))P_{H+f}(A) + \frac{1}{t}\int_p^t P_{H^{f,u}}(A)\,du. \tag*{(17)} D O , t , H ( A ) = t p ( 1 − ln ( s 0 / p )) P H + f ( A ) + t 1 ∫ p t P H f , u ( A ) d u . (17)
Here p / t p/t p / t is the probability that f f f is early, and d u / t du/t d u / t that its auxiliary time lies in d u du d u . The same recurrences hold under H + e H + e H + e , with s 1 s_1 s 1 in place of s 0 s_0 s 0 . To prove (15) , we compare each expression with p / σ e , H p/\sigma_{e,H} p / σ e , H times its counterpart under H + e H + e H + e . Induction compares the P J ( A ) P_J(A) P J ( A ) terms, but its factors depend on spanning times in the modified backgrounds, which we compute next.
How the spanning times change. For any set S ⊆ V S \subseteq V S ⊆ V , closure exchange gives
f ∈ cl ( S + e ) ∖ cl ( S ) ⟺ e ∈ cl ( S + f ) ∖ cl ( S ) . f \in\operatorname{cl}(S+e) \setminus\operatorname{cl}(S) \Longleftrightarrow e \in\operatorname{cl}(S+f) \setminus\operatorname{cl}(S). f ∈ cl ( S + e ) ∖ cl ( S ) ⟺ e ∈ cl ( S + f ) ∖ cl ( S ) .
Both sides say that S + e S+e S + e , S + f S+f S + f , and S + e + f S+e+f S + e + f have rank rank ( S ) + 1 \operatorname{rank}(S)+1 rank ( S ) + 1 . Applied to S = H u S=H_u S = H u for u < t u<t u < t , this says that adding e e e newly spans f f f on exactly the same interval as adding f f f newly spans e e e . The former interval is [ s 1 , s 0 ) [s_1,s_0) [ s 1 , s 0 ) .
If s 0 = s 1 s_0=s_1 s 0 = s 1 , this interval is empty. Adding f f f to the background with any auxiliary time therefore leaves the capped spanning time of e e e unchanged. Apply induction on O − f O-f O − f , adding e e e to the backgrounds H + f H+f H + f and H f , u H^{f,u} H f , u . In both cases the comparison factor is p / σ e , H p/\sigma_{e,H} p / σ e , H . Since s 0 = s 1 s_0=s_1 s 0 = s 1 , the coefficients in the two recurrences agree and are nonnegative, proving (15) .
From now on, suppose s 1 < s 0 s_1<s_0 s 1 < s 0 . Equality of the two nonempty intervals gives
σ e , H = s 0 , σ e , H + f = s 1 . (18) \sigma_{e,H}=s_0,\qquad\sigma_{e,H+f}=s_1. \tag*{(18)} σ e , H = s 0 , σ e , H + f = s 1 . (18)
In H f , u H^{f,u} H f , u , the fixed auxiliary time of f f f is u u u , so it can help span e e e only from max { u , s 1 } \max\{u,s_1\} max { u , s 1 } onward; without that help the spanning time is s 0 s_0 s 0 . In H f , u + e H^{f,u}+e H f , u + e , the background spans f f f at s 1 s_1 s 1 or when f f f itself becomes present at u u u , whichever comes first. Consequently,
σ e , H f , u = min { s 0 , max { s 1 , u } } , σ f , H f , u + e = min { s 1 , u } . (19) \sigma_{e,H^{f,u}}=\min\{s_0,\max\{s_1,u\}\},\qquad\sigma_{f,H^{f,u}+e}=\min\{s_1,u\}. \tag*{(19)} σ e , H f , u = min { s 0 , max { s 1 , u }} , σ f , H f , u + e = min { s 1 , u } . (19)
Thus the required factor for the full experiment is p / s 0 p/s_0 p / s 0 , while the identities above determine the factors available from induction on O − f O-f O − f . We first prove the comparison for output A + f A+f A + f , and then for output A A A .
Outputs A + f A+f A + f containing f f f . Induction under H + f H+f H + f and (18) give P H + f ( A ) ≥ ( p / s 1 ) P H + e + f ( A ) P_{H+f}(A)\ge(p/s_1)P_{H+e+f}(A) P H + f ( A ) ≥ ( p / s 1 ) P H + e + f ( A ) . Therefore
D O , t , H ( A + f ) ≥ p 2 t s 1 ln ( s 0 / p ) P H + e + f ( A ) ≥ p 2 t s 0 ln ( s 1 / p ) P H + e + f ( A ) = p s 0 D O , t , H + e ( A + f ) . D_{O,t,H}(A+f)\ge\frac{p^2}{t s_1}\ln(s_0/p)P_{H+e+f}(A)\ge\frac{p^2}{t s_0}\ln(s_1/p)P_{H+e+f}(A)=\frac{p}{s_0}D_{O,t,H+e}(A+f). D O , t , H ( A + f ) ≥ t s 1 p 2 ln ( s 0 / p ) P H + e + f ( A ) ≥ t s 0 p 2 ln ( s 1 / p ) P H + e + f ( A ) = s 0 p D O , t , H + e ( A + f ) .
The second inequality uses s 1 ≤ s 0 s_1\le s_0 s 1 ≤ s 0 and nonnegativity of the logarithms. This proves the comparison in (15) for output A + f A+f A + f .
Outputs A A A without f f f : the early deficit. It remains to prove the comparison for output A A A . Subtracting p / s 0 p/s_0 p / s 0 times (17) under H + e H+e H + e from the recurrence under H H H , and multiplying by t t t , gives
t [ D O , t , H ( A ) − p s 0 D O , t , H + e ( A ) ] = E + ∫ p t [ P H f , u ( A ) − p s 0 P H f , u + e ( A ) ] d u , (20) t\left[D_{O,t,H}(A)-\frac{p}{s_0}D_{O,t,H+e}(A)\right]=\mathcal{E}+\int_p^t\left[P_{H^{f,u}}(A)-\frac{p}{s_0}P_{H^{f,u}+e}(A)\right]\,du, \tag*{(20)} t [ D O , t , H ( A ) − s 0 p D O , t , H + e ( A ) ] = E + ∫ p t [ P H f , u ( A ) − s 0 p P H f , u + e ( A ) ] d u , (20)
where E = p ( 1 − ln ( s 0 / p ) ) P H + f ( A ) − ( p 2 / s 0 ) ( 1 − ln ( s 1 / p ) ) P H + e + f ( A ) \mathcal{E}=p(1-\ln(s_0/p))P_{H+f}(A)-(p^2/s_0)(1-\ln(s_1/p))P_{H+e+f}(A) E = p ( 1 − ln ( s 0 / p )) P H + f ( A ) − ( p 2 / s 0 ) ( 1 − ln ( s 1 / p )) P H + e + f ( A ) is the contribution from early auxiliary arrivals of f f f ; the integral is the contribution from late arrivals. We must show that their sum is nonnegative. The early term may be negative: adding e e e makes an early f f f more likely to be absent from the output. We first bound this possible loss, then show that the late contribution compensates.
Since s 0 ≤ 1 s_0\le1 s 0 ≤ 1 and p ≥ 1 / e p\ge1/e p ≥ 1/ e , we have 1 − ln ( s 0 / p ) ≥ 0 1-\ln(s_0/p)\ge0 1 − ln ( s 0 / p ) ≥ 0 , so the induction bound P H + f ( A ) ≥ ( p / s 1 ) P H + e + f ( A ) P_{H+f}(A)\ge(p/s_1)P_{H+e+f}(A) P H + f ( A ) ≥ ( p / s 1 ) P H + e + f ( A ) gives
E ≥ p 2 P H + e + f ( A ) s 0 s 1 [ s 0 ( 1 − ln ( s 0 / p ) ) − s 1 ( 1 − ln ( s 1 / p ) ) ] = − p 2 P H + e + f ( A ) s 0 s 1 ∫ s 1 s 0 ln ( v / p ) d v . (21) \mathcal{E}\ge\frac{p^2P_{H+e+f}(A)}{s_0s_1}\left[s_0(1-\ln(s_0/p))-s_1(1-\ln(s_1/p))\right]=-\frac{p^2P_{H+e+f}(A)}{s_0s_1}\int_{s_1}^{s_0}\ln(v/p)\,dv. \tag*{(21)} E ≥ s 0 s 1 p 2 P H + e + f ( A ) [ s 0 ( 1 − ln ( s 0 / p )) − s 1 ( 1 − ln ( s 1 / p )) ] = − s 0 s 1 p 2 P H + e + f ( A ) ∫ s 1 s 0 ln ( v / p ) d v . (21)
using d d v [ v ( 1 − ln ( v / p ) ) ] = − ln ( v / p ) \frac{d}{dv}[v(1-\ln(v/p))]=-\ln(v/p) d v d [ v ( 1 − ln ( v / p ))] = − ln ( v / p ) . It therefore suffices to show that the integral in (20) satisfies
∫ p t [ P H f , u ( A ) − p s 0 P H f , u + e ( A ) ] d u ≥ p 2 P H + e + f ( A ) s 0 s 1 ∫ s 1 s 0 ln ( v / p ) d v . \int_{p}^{t}\left[P_{H^{f,u}}(A)-\frac{p}{s_0}P_{H^{f,u+e}}(A)\right]\,du \ge\frac{p^2P_{H+e+f}(A)}{s_0s_1}\int_{s_1}^{s_0}\ln(v/p)\,dv. ∫ p t [ P H f , u ( A ) − s 0 p P H f , u + e ( A ) ] d u ≥ s 0 s 1 p 2 P H + e + f ( A ) ∫ s 1 s 0 ln ( v / p ) d v .
The late surplus pays for the deficit. The required bound involves P H + e + f ( A ) P_{H+e+f}(A) P H + e + f ( A ) , so we compare the late probabilities to this same quantity. For p ≤ u ≤ s 0 p\le u\le s_0 p ≤ u ≤ s 0 , apply the induction hypothesis on O − f O-f O − f twice: first add e e e to the background with auxiliary time p p p , then change f f f ’s fixed auxiliary time from u u u to p p p , using the case where the added element already lies in the background. By (19) ,
P H f , u ( A ) ≥ p max { s 1 , u } P H f , u + e ( A ) and P H f , u + e ( A ) ≥ p min { s 1 , u } P H + e + f ( A ) . P_{H^{f,u}}(A)\ge\frac{p}{\max\{s_1,u\}}P_{H^{f,u+e}}(A)
\qquad\text{and}\qquad
P_{H^{f,u+e}}(A)\ge\frac{p}{\min\{s_1,u\}}P_{H+e+f}(A). P H f , u ( A ) ≥ max { s 1 , u } p P H f , u + e ( A ) and P H f , u + e ( A ) ≥ min { s 1 , u } p P H + e + f ( A ) .
Since max { s 1 , u } ≤ s 0 \max\{s_1,u\}\le s_0 max { s 1 , u } ≤ s 0 , the first bound leaves a nonnegative coefficient, so we may substitute the second:
P H f , u ( A ) − p s 0 P H f , u + e ( A ) ≥ ( p max { s 1 , u } − p s 0 ) p min { s 1 , u } P H + e + f ( A ) = p 2 P H + e + f ( A ) s 0 s 1 s 0 − max { s 1 , u } u . (22) \begin{aligned}
P_{H^{f,u}}(A)-\frac{p}{s_0}P_{H^{f,u+e}}(A)\ge\left(\frac{p}{\max\{s_1,u\}}-\frac{p}{s_0}\right)\frac{p}{\min\{s_1,u\}}P_{H+e+f}(A) \\
&=\frac{p^2P_{H+e+f}(A)}{s_0s_1}\frac{s_0-\max\{s_1,u\}}{u}. \tag*{(22)}
\end{aligned} P H f , u ( A ) − s 0 p P H f , u + e ( A ) ≥ ( max { s 1 , u } p − s 0 p ) min { s 1 , u } p P H + e + f ( A ) = s 0 s 1 p 2 P H + e + f ( A ) u s 0 − max { s 1 , u } . (22)
Here max { s 1 , u } min { s 1 , u } = s 1 u \max\{s_1,u\}\min\{s_1,u\}=s_1u max { s 1 , u } min { s 1 , u } = s 1 u . For u ≥ s 0 u\ge s_0 u ≥ s 0 , (19) instead gives σ e , H f , u = s 0 \sigma_{e,H^{f,u}}=s_0 σ e , H f , u = s 0 , so the induction hypothesis alone makes the same difference nonnegative. It remains to integrate this lower bound. Reversing the order of integration gives exactly the scalar integral required above:
∫ p s 0 s 0 − max { s 1 , u } u d u = ∫ p s 0 ∫ max { s 1 , u } s 0 1 u d v d u = ∫ s 1 s 0 ∫ p v 1 u d u d v = ∫ s 1 s 0 ln ( v / p ) d v . (23) \int_{p}^{s_0}\frac{s_0-\max\{s_1,u\}}{u}\,du
=\int_{p}^{s_0}\int_{\max\{s_1,u\}}^{s_0}\frac{1}{u}\,dv\,du
=\int_{s_1}^{s_0}\int_{p}^{v}\frac{1}{u}\,du\,dv
=\int_{s_1}^{s_0}\ln(v/p)\,dv. \tag*{(23)} ∫ p s 0 u s 0 − max { s 1 , u } d u = ∫ p s 0 ∫ m a x { s 1 , u } s 0 u 1 d v d u = ∫ s 1 s 0 ∫ p v u 1 d u d v = ∫ s 1 s 0 ln ( v / p ) d v . (23)
Both double integrals range over the region { ( u , v ) : p ≤ u ≤ v , s 1 ≤ v ≤ s 0 } \{(u,v):p\le u\le v,\ s_1\le v\le s_0\} {( u , v ) : p ≤ u ≤ v , s 1 ≤ v ≤ s 0 } . Integrating the lower bound in (22) over u ∈ [ p , s 0 ] u\in[p,s_0] u ∈ [ p , s 0 ] exactly cancels the negative lower bound in (21) . The remaining late contribution, from u ≥ s 0 u\ge s_0 u ≥ s 0 , is nonnegative. Hence the right side of (20) is nonnegative, proving the comparison in (15) for outputs without f f f and completing the induction. □
For an eligible arrival e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) at time t > p t>p t > p , apply Lemma 5.3 to O − e O-e O − e with empty background. Since e e e is a nonloop, σ e , ∅ = t \sigma_{e,\emptyset}=t σ e , ∅ = t , giving z O , e , t ( A ) = p t D O − e , t , e ( A ) ≤ D O − e , t ( A ) z_{O,e,t}(A)=\frac{p}{t}D_{O-e,t,e}(A)\le D_{O-e,t}(A) z O , e , t ( A ) = t p D O − e , t , e ( A ) ≤ D O − e , t ( A ) . All other accepting masses are zero, and the contracted experiment outputs only sets extendible by e e e . Thus (8) holds.
Remark (A constructive proof). The proof of Lemma 5.3 is constructive: § 6.4 turns each use of the induction hypothesis into a recursive call of the efficient implementation, and each lowered coefficient into a random rejection.
Continuous-time consistency
We verify consistency by increasing t t t while keeping O O O and p p p fixed. Multiplying D O , t ( A ) D_{O,t}(A) D O , t ( A ) by t ∣ O ∣ t^{|O|} t ∣ O ∣ removes the uniform-density factor, leaving an integral over [ 0 , t ] O [0,t]^O [ 0 , t ] O . For t > p t>p t > p , increasing t t t has two effects. The expanding integration domain contributes configurations with an auxiliary arrival at time t t t ; that element is late and cannot survive. For fixed auxiliary times inside the domain, each early e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) has conditional survival probability ln ( t / p ) \ln(t/p) ln ( t / p ) , which increases at rate 1 / t 1/t 1/ t . We compute both contributions and show that their sum gives the differential balance identity, then integrate.
Lemma 5.4 (Consistency). The survivor distributions and accepting masses satisfy (9) .
Proof. Fix O O O , let m = ∣ O ∣ > 0 m = |O| > 0 m = ∣ O ∣ > 0 , and fix A ⊆ O A \subseteq O A ⊆ O . First take p < t < 1 p < t < 1 p < t < 1 . For a vector of auxiliary arrival times x = ( x f ) f ∈ O ∈ [ 0 , t ] O x = (x_f)_{f\in O} \in[0,t]^O x = ( x f ) f ∈ O ∈ [ 0 , t ] O , let ψ A ( x , t ) \psi_A(x,t) ψ A ( x , t ) be the probability of survivor set A A A , averaging only over the survival coins. The vector has density t − m t^{-m} t − m , so
t m D O , t ( A ) = ∫ [ 0 , t ] O ψ A ( x , t ) d x . t^mD_{O,t}(A) = \int_{[0,t]^O} \psi_A(x,t)\,dx. t m D O , t ( A ) = ∫ [ 0 , t ] O ψ A ( x , t ) d x .
Expanding the integration domain. As t t t increases, new auxiliary-time vectors enter [ 0 , t ] O [0,t]^O [ 0 , t ] O . The contribution with x e = t x_e=t x e = t places e e e at the horizon. This late element cannot survive and changes no other conditional survival probability: any spanning time it reduces to t t t was already capped at t t t . The remaining experiment is therefore the one on O − e O-e O − e . Integrating over the other m − 1 m-1 m − 1 coordinates gives zero if e ∈ A e\in A e ∈ A , and t m − 1 D O − e , t ( A ) t^{m-1}D_{O-e,t}(A) t m − 1 D O − e , t ( A ) otherwise. Summing over e ∈ O e\in O e ∈ O gives t m − 1 ∑ e ∈ O ∖ A D O − e , t ( A ) t^{m-1}\sum_{e\in O\setminus A}D_{O-e,t}(A) t m − 1 ∑ e ∈ O ∖ A D O − e , t ( A ) .
Changing the survival probabilities. Fix the auxiliary times x x x , all strictly below t t t . An early element outside Greedy ( O ) \operatorname{Greedy}(O) Greedy ( O ) is already spanned before t t t , so its conditional survival probability is unchanged. For an early e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) , however, σ e = t \sigma_e=t σ e = t , so that probability is ln ( t / p ) \ln(t/p) ln ( t / p ) and increases at rate 1 / t 1/t 1/ t . Late elements never survive.
When e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) is early, the other survivors have the same conditional distribution as the experiment in M / e \mathcal{M}/e M / e with the same auxiliary times. Indeed, for f f f smaller than e e e , the larger elements determining its spanning time already include e e e from p p p . For f f f larger than e e e , adding e e e cannot make f f f spanned sooner: if the larger elements S S S present do not span f f f but S + e S+e S + e does, closure exchange implies that S + f S+f S + f spans e e e . All elements of S + f S+f S + f are larger than e e e , contrary to e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) . Thus the other spanning times and conditional survival probabilities agree with the contracted experiment, irrespective of the precise value of x e ∈ [ 0 , p ] x_e\in[0,p] x e ∈ [ 0 , p ] .
Conditional on x x x , ψ A ( x , t ) \psi_A(x,t) ψ A ( x , t ) is a product of Bernoulli probabilities. The factor for early e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) is ln ( t / p ) \ln(t/p) ln ( t / p ) if e ∈ A e\in A e ∈ A and 1 − ln ( t / p ) 1-\ln(t/p) 1 − ln ( t / p ) otherwise. Differentiating it gives + 1 / t +1/t + 1/ t or − 1 / t -1/t − 1/ t , multiplied by the probability that the other survivors are A − e A-e A − e or A A A , respectively.
For e ∈ A ∩ Greedy ( O ) e\in A\cap\operatorname{Greedy}(O) e ∈ A ∩ Greedy ( O ) , integrating this contribution gives
p ⋅ 1 t ⋅ t m − 1 D O − e , t , e ( A − e ) = t m − 1 z O , e , t ( A − e ) . p\cdot\frac{1}{t}\cdot t^{m-1}D_{O-e,t,e}(A-e)=t^{m-1}z_{O,e,t}(A-e). p ⋅ t 1 ⋅ t m − 1 D O − e , t , e ( A − e ) = t m − 1 z O , e , t ( A − e ) .
The three factors come from integrating the early coordinate x e ∈ [ 0 , p ] x_e\in[0,p] x e ∈ [ 0 , p ] , differentiating its conditional survival probability, and integrating the other coordinates. For e ∈ Greedy ( O ) ∖ A e\in\operatorname{Greedy}(O)\setminus A e ∈ Greedy ( O ) ∖ A , the contribution is instead − t m − 1 z O , e , t ( A ) -t^{m-1}z_{O,e,t}(A) − t m − 1 z O , e , t ( A ) . Elements outside Greedy ( O ) \operatorname{Greedy}(O) Greedy ( O ) contribute zero to this interior term and have z O , e , t = 0 z_{O,e,t}=0 z O , e , t = 0 . For e ∉ A e\notin A e ∈ / A , the boundary contribution and the negative contribution above combine to give t m − 1 ( D O − e , t ( A ) − z O , e , t ( A ) ) t^{m-1}(D_{O-e,t}(A)-z_{O,e,t}(A)) t m − 1 ( D O − e , t ( A ) − z O , e , t ( A )) , the rejected-arrival term. For e ∈ A e\in A e ∈ A , the positive contribution is the accepted-arrival term. Together,
d d t ( t m D O , t ( A ) ) = t m − 1 [ ∑ e ∈ O ∖ A ( D O − e , t ( A ) − z O , e , t ( A ) ) + ∑ e ∈ A z O , e , t ( A − e ) ] . \frac{d}{dt}\left(t^mD_{O,t}(A)\right)
=t^{m-1}\left[\sum_{e\in O\setminus A}\left(D_{O-e,t}(A)-z_{O,e,t}(A)\right)+\sum_{e\in A}z_{O,e,t}(A-e)\right]. d t d ( t m D O , t ( A ) ) = t m − 1 e ∈ O ∖ A ∑ ( D O − e , t ( A ) − z O , e , t ( A ) ) + e ∈ A ∑ z O , e , t ( A − e ) .
which is the differential form of (9) . For t < p t<p t < p , the survivor set is empty and all accepting masses vanish, so both sides equal m t m − 1 1 { A = ∅ } mt^{m-1}\mathbf{1}_{\{A=\varnothing\}} m t m − 1 1 { A = ∅ } .
Integrating the balance equation. For auxiliary times in [ 0 , s ] O [0,s]^O [ 0 , s ] O , increasing the horizon from s s s to t t t changes each conditional survival probability by at most ( t − s ) / p (t-s)/p ( t − s ) / p . A product of Bernoulli probabilities changes by at most the sum of the parameter changes. Comparing the integral over [ 0 , s ] O [0,s]^{O} [ 0 , s ] O with the added domain gives, for p ≤ s ≤ t ≤ 1 p \le s \le t \le1 p ≤ s ≤ t ≤ 1 ,
∣ t m D O , t ( A ) − s m D O , s ( A ) ∣ ≤ m p ( t − s ) s m + ( t m − s m ) . \left|t^{m}\mathcal{D}_{O,t}(A)-s^{m}\mathcal{D}_{O,s}(A)\right| \le\frac{m}{p}(t-s)s^{m}+(t^{m}-s^{m}). ∣ t m D O , t ( A ) − s m D O , s ( A ) ∣ ≤ p m ( t − s ) s m + ( t m − s m ) .
These bounds justify the differentiation above and show that increments of t m D O , t ( A ) t^{m}\mathcal{D}_{O,t}(A) t m D O , t ( A ) on [ p , 1 ] [p,1] [ p , 1 ] equal integrals of its derivative. On [ 0 , p ] [0,p] [ 0 , p ] , it equals t m 1 { A = ∅ } t^{m}\mathbf{1}\{A=\varnothing\} t m 1 { A = ∅ } , which is zero at 0 0 0 and agrees with the survivor experiment at p p p . Integrating the displayed differential identity from 0 0 0 to t t t therefore gives (9) for every 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 .
Proof of Theorem 5.2 . The experiments give measurable distributions on independent sets. Lemmas 5.3 and 5.4 verify capacity and consistency; Theorem 4.4 realizes them via (10) , which is exactly Algorithm 3. The rule uses only the observed value order, the current time, and the arrived matroid restriction; n n n suffices to simulate the arrival times. The terminal guarantee was established after the theorem.
Efficient Survival Simulation
Toward an efficient implementation. Fix p = 1 / e p=1/e p = 1/ e . We want to accept an eligible element e e e arriving at time t > p t>p t > p with probability
p t ⋅ D O , t , e ( A ) D O , t ( A ) . \frac{p}{t}\cdot\frac{\mathcal{D}_{O,t,e}(A)}{\mathcal{D}_{O,t}(A)}. t p ⋅ D O , t ( A ) D O , t , e ( A ) .
where O O O and A A A are the sets of observed and accepted elements before e e e ’s arrival. We do not know how to compute this probability efficiently. Instead, we sample a binary acceptance decision with this probability without computing it.
The inductive proof of Lemma 5.3 is almost a recursive algorithm for sampling such a decision. Its inductive step
conditions on the auxiliary time T f ′ T_f^{\prime} T f ′ (denoted by u u u in the proof) of the largest element f ∈ O f\in O f ∈ O , expressing both distributions as mixtures of survivor-set probabilities on O − f O-f O − f with modified backgrounds;
decreases selected nonnegative coefficients in the expression for D O , t ( A ) \mathcal{D}_{O,t}(A) D O , t ( A ) ; and
applies the induction hypothesis once or twice to each term in the expression for D O , t ( A ) \mathcal{D}_{O,t}(A) D O , t ( A ) , matching the terms for D O , t , e ( A ) \mathcal{D}_{O,t,e}(A) D O , t , e ( A ) up to the factor p / t p/t p / t .
The coefficient reductions in step 2 correspond to rejecting e e e with an appropriate probability. The uses of induction in step 3 become recursive calls on smaller candidate sets, with modified backgrounds and comparison factor p / σ e , H p/\sigma_{e,H} p / σ e , H . The main obstacle is step 1: it needs a sample of T f ′ T_f^{\prime} T f ′ given O O O , t t t , and the survivor set A A A , and an independent uniform sample does not suffice.
This motivates maintaining a configuration that encodes the experiment’s auxiliary times and survival coins, and whose survivor set equals the accepted set. If, conditional on the observed set at horizon t t t , these encoded values are independent and uniform as in the survivor experiment, then conditioning additionally on A A A gives exactly the sample of T f ′ T_f^{\prime} T f ′ needed above.
The natural source of randomness is the arrival times. However, using them directly as auxiliary times has two problems. First, an eligible element e e e accepted at time t > p t>p t > p cannot keep T e ′ = T e T_e^{\prime}=T_e T e ′ = T e , or it would be late and could not survive. We must make it early, adjusting the other coordinates without changing their survivors. Second, increasing the horizon can increase an early element’s survival probability. If a previously rejected element f f f would become a survivor, we cannot accept it retroactively; we must instead make it late, again adjusting the other coordinates. Forward and reverse procedures perform these two updates. Their probability transfers balance, preserving uniformity conditional on the observed set at each fixed horizon.
Computational model. We work in the randomized real RAM: exact arithmetic operations, comparisons, and independent uniform draws from [ 0 , 1 ] [0,1] [ 0 , 1 ] cost one unit each, as do evaluations of ln \ln ln and exp \exp exp , which go beyond the standard model. Independence queries are counted separately. All running-time bounds below are expected bounds in this model, not bit-complexity bounds.
Theorem 6.1 (Efficient realization). Algorithm 4 realizes the same survivor distributions and accepting masses as Algorithm 3 with p = 1 / e p = 1/e p = 1/ e . It is ordinal, uses only n n n and comparison and independence queries on arrived elements, and has expected polynomial arithmetic and independence-oracle complexity. Its terminal set has distribution D V , 1 \mathcal{D}_{V,1} D V , 1 ; in particular, the elements of Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) are accepted independently, each with probability 1 / e 1/e 1/ e .
Auxiliary configurations and update procedures
The auxiliary configuration is a vector with one coordinate X f ∈ [ 0 , t ] X_f \in[0,t] X f ∈ [ 0 , t ] per element f f f : if X f > p X_f > p X f > p , it specifies a late auxiliary arrival at X f X_f X f ; if X f ≤ p X_f \le p X f ≤ p , it specifies an early element and X f / p X_f/p X f / p is its survival coin. Lowercase x f x_f x f denotes a particular value of this coordinate. The exact auxiliary time of an early element is irrelevant, since it is present throughout [ p , t ] [p,t] [ p , t ] . A late element never survives, so its survival coin is irrelevant. Thus one coordinate suffices. For independent uniform coordinates on [ 0 , t ] [0,t] [ 0 , t ] , the early set and late auxiliary times have the same distribution as in Definition 5.1 . Conditional on them, the variables X f / p X_f/p X f / p for early elements are independent uniforms on [ 0 , 1 ] [0,1] [ 0 , 1 ] , providing the required survival randomness.
Given x ∈ [ 0 , t ] O x \in[0,t]^O x ∈ [ 0 , t ] O and a background schedule H H H , let σ f ( x ) \sigma_f(x) σ f ( x ) be the first time u ∈ [ p , t ] u \in[p,t] u ∈ [ p , t ] at which
H u ∪ { f ′ ∈ O : f ′ ≻ f , x f ′ ≤ u } H_u \cup\{f' \in O : f' \succ f,\ x_{f'} \le u\} H u ∪ { f ′ ∈ O : f ′ ≻ f , x f ′ ≤ u }
spans f f f , or t t t if this never occurs. As in Definition 5.1 , σ f ( x ) \sigma_f(x) σ f ( x ) is the capped spanning time of f f f . Note that σ f ( x ) \sigma_f(x) σ f ( x ) does not depend on x f x_f x f , and we suppress its dependence on O O O , t t t , and H H H . Further, write
g ( u ) = p ln u p , g ′ ( u ) = p u , g − 1 ( x ) = p exp ( x / p ) . g(u) = p \ln\frac{u}{p}, \qquad g'(u) = \frac{p}{u}, \qquad g^{-1}(x) = p\exp(x/p). g ( u ) = p ln p u , g ′ ( u ) = u p , g − 1 ( x ) = p exp ( x / p ) .
For p ≤ u ≤ 1 p \le u \le1 p ≤ u ≤ 1 , we have 0 ≤ g ( u ) ≤ g ( 1 ) = p 0 \le g(u) \le g(1) = p 0 ≤ g ( u ) ≤ g ( 1 ) = p . By the definition of the auxiliary configuration, f f f is early and the coin x f p \frac{x_f}{p} p x f is at most the survival probability ln ( σ f ( x ) / p ) \ln(\sigma_f(x)/p) ln ( σ f ( x ) / p ) if and only if x f ≤ g ( σ f ( x ) ) x_f \le g(\sigma_f(x)) x f ≤ g ( σ f ( x )) . Hence, the survivor set determined by configuration x x x is
A O , t , H ( x ) = { f ∈ O : x f ≤ g ( σ f ( x ) ) } . (24) \mathcal{A}_{O,t,H}(x) = \{f \in O : x_f \le g(\sigma_f(x))\}. \tag*{(24)} A O , t , H ( x ) = { f ∈ O : x f ≤ g ( σ f ( x ))} . (24)
We omit H H H when it is empty, and write e e e for constant background { e } \{e\} { e } , as in § 5 . For a uniform configuration on [ 0 , t ] O [0,t]^O [ 0 , t ] O , this set has distribution D O , t , H \mathcal{D}_{O,t,H} D O , t , H .
The forward procedure F O , t , H , e \mathrm{F}_{O,t,H,e} F O , t , H , e takes a configuration x ∈ [ 0 , t ] O x \in[0,t]^O x ∈ [ 0 , t ] O and either returns failure, denoted ⊥ \perp ⊥ , or a configuration y y y for the experiment with background H + e H+e H + e . The reverse procedure R O , t , H , e \mathrm{R}_{O,t,H,e} R O , t , H , e takes y y y and always returns an x x x . We write F ( x , d y ) \mathrm{F}(x,dy) F ( x , d y ) for the probability of a successful forward output in d y dy d y , and R ( y , d x ) \mathrm{R}(y,dx) R ( y , d x ) for the reverse output distribution, suppressing parameters when unambiguous. The forward measure can have total mass less than one, in which case the missing mass corresponds to failure. The notation d x dx d x denotes ordinary volume measure on the coordinate domain [ 0 , t ] O [0,t]^O [ 0 , t ] O . The next lemma summarizes the properties we need for these two procedures.
Lemma 6.2 (Forward and reverse procedures). For every ordered set O O O , horizon t ∈ ( p , 1 ] t \in(p,1] t ∈ ( p , 1 ] , background H H H disjoint from O O O , and e ∉ O e \notin O e ∈ / O , there are forward and reverse procedures with the following properties.
(i) Probability-mass balance. Reverse calls always return an output, and the measures on successful input–output pairs satisfy
d x F O , t , H , e ( x , d y ) = p σ e , H d y R O , t , H , e ( y , d x ) . (25) \mathrm{d}x\,F_{O,t,H,e}(x,\mathrm{d}y)=\frac{p}{\sigma_{e,H}}\,\mathrm{d}y\,R_{O,t,H,e}(y,\mathrm{d}x). \tag*{(25)} d x F O , t , H , e ( x , d y ) = σ e , H p d y R O , t , H , e ( y , d x ) . (25) In particular, a forward call on uniform input succeeds with probability p / σ e , H p/\sigma_{e,H} p / σ e , H and, conditional on success, has uniform output.
(ii) Survivors are preserved. Every pair from a successful forward call or a reverse call satisfies
A O , t , H ( x ) = A O , t , H + e ( y ) = A . A_{O,t,H}(x)=A_{O,t,H+e}(y)=A. A O , t , H ( x ) = A O , t , H + e ( y ) = A . (iii) Coordinates move only when allowed. For such a pair, x f = y f x_f=y_f x f = y f for f ∈ A f \in A f ∈ A , and x f ≥ y f x_f \ge y_f x f ≥ y f for f ∉ A f \notin A f ∈ / A . Thus survivors’ coordinates never change; other coordinates only decrease forward and increase in reverse.
(iv) Expected cost. On uniform input, either procedure makes O ( ∣ O ∣ ) O(|O|) O ( ∣ O ∣ ) recursive calls in expectation. Excluding recursion, the number of independence queries and the expected number of arithmetic operations per call are polynomial in the number of available elements.
We construct the procedures and prove Lemma 6.2 in § 6.4 . Identity (25) is stronger than the capacity comparison: it matches individual successful input–output pairs, not just the probabilities of survivor sets. For an eligible arrival e e e at t > p t>p t > p , empty background gives σ e , ∅ = t \sigma_{e,\varnothing}=t σ e , ∅ = t . Integrating the identity over pairs with survivor set A A A yields, for uniform X O X_O X O ,
Pr [ A O , t ( X O ) = A , F O , t , ∅ , e succeeds ] = p t D O , t , e ( A ) = z O + e , e , t ( A ) . \Pr[A_{O,t}(X_O)=A,\ F_{O,t,\varnothing,e}\text{ succeeds}]=\frac{p}{t}D_{O,t,e}(A)=z_{O+e,e,t}(A). Pr [ A O , t ( X O ) = A , F O , t , ∅ , e succeeds ] = t p D O , t , e ( A ) = z O + e , e , t ( A ) .
If D O , t ( A ) > 0 D_{O,t}(A)>0 D O , t ( A ) > 0 , dividing by D O , t ( A ) = Pr [ A O , t ( X O ) = A ] D_{O,t}(A)=\Pr[A_{O,t}(X_O)=A] D O , t ( A ) = Pr [ A O , t ( X O ) = A ] gives the acceptance probability from the opening paragraph. This probability averages over the coordinates conditional on survivor set A A A ; it need not be the success probability for each individual vector. If D O , t ( A ) = 0 D_{O,t}(A)=0 D O , t ( A ) = 0 , use the convention 0 / 0 = 0 0/0=0 0/0 = 0 from Algorithm 3.
The efficient online algorithm
We use the continuous-time model of § 4.3 , simulating arrival times internally in the ordinary secretary model. The algorithm maintains the observed ordered set O O O , the accepted set A L G \mathrm{ALG} ALG , and coordinates X O X_O X O . Its internal updates via reverse procedures are called reverse events .
A rejected element can still have an early coordinate in the configuration, either because it arrived before p p p or because a later forward call lowered its coordinate. Reverse events prevent exactly these elements from becoming survivors. They never reverse an online decision. Throughout this section, the configuration at an event time refers to the one immediately after the update; we omit the probability-zero cases of coincident events.
Lemma 6.3 (Feasibility invariant). Almost surely, at every t ∈ [ p , 1 ] t \in[p,1] t ∈ [ p , 1 ] the algorithm maintains
A L G = A O , t ( X O ) . (26) \mathrm{ALG}=A_{O,t}(X_O). \tag*{(26)} ALG = A O , t ( X O ) . (26) Accepted coordinates never change, and every recomputed reverse event lies strictly in the future.
Algorithm 4 Efficient survival simulation
Let p = 1 / e p = 1/\mathrm{e} p = 1/ e and g ( t ) = p ln ( t / p ) g(t) = p\ln(t/p) g ( t ) = p ln ( t / p ) . Initialize O = A L G = ∅ O = \mathrm{ALG} = \varnothing O = ALG = ∅ and an empty vector X O X_O X O . Use the forward and reverse procedures of Lemma 6.2 .
Process arrivals and reverse events in chronological order.
Arrival e e e at t ≤ p t \le p t ≤ p . Reject e e e , set X e = t X_e = t X e = t , and add e e e to O O O .
Arrival e e e at t > p t > p t > p . If e ∈ Greedy ( O + e ) e \in\operatorname{Greedy}(O + e) e ∈ Greedy ( O + e ) , run F O , t , ∅ , e ( X O ) F_{O,t,\varnothing,e}(X_O) F O , t , ∅ , e ( X O ) . On success, replace X O X_O X O by the returned vector, set X e = g ( t ) X_e = g(t) X e = g ( t ) , and accept e e e by adding it to A L G \mathrm{ALG} ALG . If e e e is ineligible or the call fails, reject it, leave X O X_O X O unchanged, and set X e = t X_e = t X e = t . In either case add e e e to O O O .
Reverse event. For each f ∈ Greedy ( O ) ∖ A L G f \in\operatorname{Greedy}(O) \setminus\mathrm{ALG} f ∈ Greedy ( O ) ∖ ALG with X f ≤ p X_f \le p X f ≤ p , the candidate event time is g − 1 ( X f ) = p exp ( X f / p ) g^{-1}(X_f) = p\exp(X_f/p) g − 1 ( X f ) = p exp ( X f / p ) . At such an event at time t t t , set
X O − f ← R O − f , t , ∅ , f ( X O − f ) , X f ← t . X_{O-f} \gets R_{O-f,t,\varnothing,f}(X_{O-f}), \qquad X_f \gets t. X O − f ← R O − f , t , ∅ , f ( X O − f ) , X f ← t . Leave A L G \mathrm{ALG} ALG unchanged.
Proof. At time p p p , the accepted and survivor sets are empty, since g ( p ) = 0 g(p) = 0 g ( p ) = 0 and the coordinates are positive almost surely.
Rejected arrival. A rejected arrival at t > p t > p t > p gets X e = t > p X_e = t > p X e = t > p and cannot survive. It enters the survivor experiment only at the current horizon, so it changes no other capped spanning time σ f \sigma_f σ f for f ≠ e f \ne e f = e .
Accepted arrival. Let x , y x,y x , y be the input and output of the forward call. Then A O , t ( x ) = A O , t , e ( y ) A_{O,t}(x) = A_{O,t,e}(y) A O , t ( x ) = A O , t , e ( y ) ((Lemma 6.2)). Setting X e = g ( t ) ≤ p X_e = g(t) \le p X e = g ( t ) ≤ p makes e e e early. As shown in the proof of Lemma 5.4 , an early e ∈ Greedy ( O + e ) e \in\operatorname{Greedy}(O + e) e ∈ Greedy ( O + e ) affects the other spanning times exactly as a constant background e e e . Thus the old survivors are unchanged. The new element e e e has capped spanning time σ e = t \sigma_e = t σ e = t , so X e = g ( t ) X_e = g(t) X e = g ( t ) makes it a survivor as well.
Between events. With O O O and the coordinates fixed, the threshold g ( σ f ) g(\sigma_f) g ( σ f ) increases only for f ∈ Greedy ( O ) f \in\operatorname{Greedy}(O) f ∈ Greedy ( O ) , whose capped spanning time is σ f = t \sigma_f = t σ f = t . No survivor disappears. A rejected element can become a survivor only if it lies in Greedy ( O ) \operatorname{Greedy}(O) Greedy ( O ) and g ( t ) g(t) g ( t ) reaches X f ≤ p X_f \le p X f ≤ p , which is precisely its scheduled reverse event.
Reverse event. Just before the event, the triggering f ∈ Greedy ( O ) f \in\operatorname{Greedy}(O) f ∈ Greedy ( O ) is an early nonsurvivor and acts on the other elements as constant background f f f . The reverse call removes this background while preserving the survivor set on O − f O - f O − f ((Lemma 6.2)). Appending X f = t > p X_f = t > p X f = t > p to the returned configuration changes no capped spanning time σ f ′ \sigma_{f'} σ f ′ for f ′ ≠ f f' \ne f f ′ = f and keeps f f f a nonsurvivor. Hence the accepted set remains unchanged.
The procedures fix every survivor’s coordinate, so an accepted e e e keeps X e = g ( T e ) X_e = g(T_e) X e = g ( T e ) thereafter. Finally, just after an update at time t t t , a reverse-event candidate f f f has σ f = t \sigma_f = t σ f = t but is not a survivor. Therefore X f > g ( t ) X_f > g(t) X f > g ( t ) , and its candidate time g − 1 ( X f ) g^{-1}(X_f) g − 1 ( X f ) is strictly greater than t t t .
Number of events. At a reverse event, the triggering element’s configuration coordinate becomes t > p t > p t > p . Subsequent reverse calls only increase nonsurvivors’ coordinates, so that same element cannot trigger again before the next arrival. There are consequently at most n n n forward calls and n ( n + 1 ) n(n + 1) n ( n + 1 ) reverse events. In particular, the event schedule is finite.
The continuous snapshot lemma
Lemma 6.4 (Continuous snapshot lemma). At every fixed t ∈ [ p , 1 ] t \in[p,1] t ∈ [ p , 1 ] , conditional on the observed ordered set O O O , the coordinates X O X_O X O are jointly uniform on [ 0 , t ] O [0,t]^O [ 0 , t ] O .
This is the continuous counterpart of Lemma 2.4. There, reversible updates permute equally likely configurations. Here, the updates are randomized, and (25) replaces the bijection by an equality of probability masses. Concretely, an accepted arrival of e e e at time u u u moves its coordinate from u u u to g ( u ) g(u) g ( u ) , and a reverse event of e e e at time u u u moves it back from g ( u ) g(u) g ( u ) to u u u . Under uniform coordinates, the horizon reaches an arrival time in [ u , u + d u ] [u,u+du] [ u , u + d u ] with probability proportional to d u du d u , while the threshold reaches a rejected early coordinate with probability proportional to g ′ ( u ) d u = ( p / u ) d u g'(u)\,du = (p/u)\,du g ′ ( u ) d u = ( p / u ) d u . Since p / u = p / σ e , ∅ p/u = p/\sigma_{e,\varnothing} p / u = p / σ e , ∅ is exactly the factor in (25) , these two flows of probability cancel. We make this precise by reconstructing an execution backward.
Proof. For analysis only, append the unarrived coordinates, setting X e = T e X_e = T_e X e = T e until e e e arrives. The full vector X ∈ [ 0 , 1 ] V X \in[0,1]^V X ∈ [ 0 , 1 ] V is uniform at time p p p . At a horizon v v v away from event times, it determines the arrived set O = { e : X e ≤ v } O = \{e : X_e \le v\} O = { e : X e ≤ v } and, by (26) , the accepted set. Between events the vector is constant. We show that its uniform distribution is preserved at every fixed later time.
The event table. At time u > p u > p u > p , an arrival has X e = u X_e = u X e = u . A reverse event has X e = g ( u ) X_e = g(u) X e = g ( u ) with e e e still rejected immediately before the update. Call these the late and early boundaries , respectively. For this table, let O O O include the element e e e involved in the event, and let x , y x,y x , y be vectors on O − e O-e O − e . Abbreviate F = F O − e , u , ∅ , e F = F_{O-e,u,\varnothing,e} F = F O − e , u , ∅ , e and R = R O − e , u , ∅ , e R = R_{O-e,u,\varnothing,e} R = R O − e , u , ∅ , e , and let r ( x ) = Pr [ F ( x ) = ⊥ ] r(x) = \Pr[F(x) = \perp] r ( x ) = Pr [ F ( x ) =⊥ ] for eligible e e e . Each pair in the middle columns lists ( X e , X O − e ) (X_e,X_{O-e}) ( X e , X O − e ) .
Table 3.
The first three rows describe three cases of e e e ’s arrival; in the last row, e e e has already arrived and remains rejected.
Backward reconstruction. We compare executions of the online algorithm from uniform vectors at time p p p with the following backward reconstructions from uniform vectors at time t t t , and show that their measures agree after reversing time. Start from a generic vector Y ∈ [ 0 , 1 ] V Y \in[0,1]^V Y ∈ [ 0 , 1 ] V at the target time t t t . Set X = Y X = Y X = Y , O = { e : X e ≤ t } O = \{e : X_e \le t\} O = { e : X e ≤ t } , and A L G = A O , t ( X O ) \mathrm{ALG} = A_{O,t}(X_O) ALG = A O , t ( X O ) , and run the horizon backward. Keep coordinates fixed until reaching one of the following boundaries.
At a late boundary X e = u > p X_e = u > p X e = u > p of an arrived element, e e e is a nonsurvivor. If e ∉ G r e e d y ( O ) e \notin\mathrm{Greedy}(O) e ∈ / Greedy ( O ) , remove it from O O O . Otherwise apply F O − e , u , ∅ , e F_{O-e,u,\varnothing,e} F O − e , u , ∅ , e to X O − e X_{O-e} X O − e . On failure, remove e e e from O O O . On success, replace X O − e X_{O-e} X O − e by the output, set X e = g ( u ) X_e = g(u) X e = g ( u ) , and keep e e e arrived but rejected.
At an early boundary X e = g ( u ) X_e = g(u) X e = g ( u ) of an accepted element, e ∈ G r e e d y ( O ) e \in\mathrm{Greedy}(O) e ∈ Greedy ( O ) : otherwise σ e < u \sigma_e < u σ e < u , and survival would give X e ≤ g ( σ e ) < g ( u ) X_e \le g(\sigma_e) < g(u) X e ≤ g ( σ e ) < g ( u ) . Apply R O − e , u , ∅ , e R_{O-e,u,\varnothing,e} R O − e , u , ∅ , e to X O − e X_{O-e} X O − e , set X e = u X_e = u X e = u , and remove e e e from both O O O and A L G \mathrm{ALG} ALG .
Once an element is removed from O O O at time u u u , its coordinate remains fixed at u u u , which serves as its arrival time in the reconstructed execution. In the first rule, a removal reconstructs a rejected arrival and a successful call reconstructs a reverse event; the second rule reconstructs an accepted arrival. The reconstructed state corresponds to the moment just before the event at time u u u .
Validity of the reconstruction. We check that the reconstructed state is valid at every horizon v v v between events: O = { e : X e ≤ v } O = \{e : X_e \le v\} O = { e : X e ≤ v } and A L G = A O , v ( X O ) \mathrm{ALG} = A_{O,v}(X_O) ALG = A O , v ( X O ) , as in (26) . The first condition holds by construction: the procedures return coordinates in [ 0 , u ] [0,u] [ 0 , u ] , and the horizon reaches a coordinate in O O O only at a late boundary, which either removes the element or lowers its coordinate to g ( u ) ≤ p g(u) \le p g ( u ) ≤ p . For the second, an element kept rejected at X e = g ( u ) X_e = g(u) X e = g ( u ) is a nonsurvivor just before u u u , since g ( v ) < X e g(v) < X_e g ( v ) < X e for v < u v < u v < u . The survivor-preserving property of Lemma 6.2 (ii), together with the argument of Lemma 6.3 , shows that these steps leave the survivor status of every element other than e e e unchanged and give valid states between events.
Termination of the reconstruction. Between two removals, every update is a successful forward call, which only decreases nonsurvivors’ coordinates, followed by setting the triggering coordinate to g ( u ) ≤ p g(u) \le p g ( u ) ≤ p . Each element therefore triggers at most once in between. There are at most n n n removals and n ( n + 1 ) n(n+1) n ( n + 1 ) successful forward calls. Hence, the reconstruction reaches time p p p . There the survivor set is empty since g ( p ) = 0 g(p) = 0 g ( p ) = 0 , so A L G = ∅ \mathrm{ALG} = \varnothing ALG = ∅ and the reconstruction ends in a valid initial state.
Matching individual events. We show that each event of the online algorithm and the backward step that reconstructs it carry the same mass when their input states are weighted by the corresponding boundary weights. Under uniform volume, a late boundary has weight d u d x du\,dx d u d x , because X e = u X_e = u X e = u . An early boundary has weight g ′ ( u ) d u d y g'(u)\,du\,dy g ′ ( u ) d u d y , because X e = g ( u ) X_e = g(u) X e = g ( u ) . The coordinates of unarrived elements contribute the same additional volume factor and are temporarily held fixed. Since g ′ ( u ) = p / u g'(u) = p/u g ′ ( u ) = p / u and σ e , ∅ = u \sigma_{e,\varnothing} = u σ e , ∅ = u , (25) gives
d u d x F O − e , u , ∅ , e ( x , d y ) = g ′ ( u ) d u d y R O − e , u , ∅ , e ( y , d x ) . (27) du\,dx\,F_{O-e,u,\varnothing,e}(x,dy) = g'(u)\,du\,dy\,R_{O-e,u,\varnothing,e}(y,dx). \tag*{(27)} d u d x F O − e , u , ∅ , e ( x , d y ) = g ′ ( u ) d u d y R O − e , u , ∅ , e ( y , d x ) . (27)
This matches each accepted arrival with the second rule, and each reverse event with a successful call in the first rule. A rejected eligible arrival leaves the vector unchanged and has probability r ( x ) r(x) r ( x ) in both directions. An ineligible arrival is the identity in both directions. Thus all four rows have matching weighted transition measures.
From events to complete executions. The boundary weights are ordinary volume on the full vector, with the event time u u u in place of the coordinate X e X_e X e . Partition states at time p p p , or just after an event, according to the next boundary (late or early) and its element, with a separate part for reaching t t t without another event. On each part, the vector remains unchanged until that boundary or time t t t . Hence the volume at the beginning of the interval matches the boundary weight if a boundary is reached, and the volume at time t t t otherwise. The same holds backward, partitioning according to the previous boundary or reaching p p p . The two partitions pair up, since validity on both sides (Lemma 6.3 for the online algorithm) rules out early boundaries inside an interval: an accepted element would be a nonsurvivor before its boundary, and a rejected element of Greedy ( O ) \operatorname{Greedy}(O) Greedy ( O ) a survivor after it.
Fix a sequence of event types and elements. Alternating these unchanged-vector intervals with the matched random updates gives equal measures to executions of the online algorithm and to the backward reconstructions that visit the same states in reverse order. Integrate over the intermediate states and sum over event sequences. The online algorithm and the backward reconstruction both have a uniform finite bound on the number of events; all terms are nonnegative. Coincident boundaries form a null set for the corresponding boundary weights. By (27) , the weighted transitions assign zero mass to these exceptional outgoing configurations in either direction. Since executions have finitely many events, coincidences occur with probability zero. We obtain
d X P p , t ( X , d Y ) = d Y P ← t , p ( Y , d X ) , (28) dX\,P_{p,t}(X,dY)=dY\,\overleftarrow{P}_{t,p}(Y,dX), \tag*{(28)} d X P p , t ( X , d Y ) = d Y P t , p ( Y , d X ) , (28)
where P p , t ( X , d Y ) P_{p,t}(X,dY) P p , t ( X , d Y ) and P ← t , p ( Y , d X ) \overleftarrow{P}_{t,p}(Y,dX) P t , p ( Y , d X ) are the output distributions of the online algorithm from time p p p to t t t and of the backward reconstruction from t t t to p p p , respectively. This argument uses measures on pairs; it does not assume that the randomized updates have densities. Since the backward reconstruction terminates with probability one, integrating out X X X gives
∫ d X P p , t ( X , d Y ) = d Y ∫ P ← t , p ( Y , d X ) = d Y . \int dX\,P_{p,t}(X,dY)=dY\int\overleftarrow{P}_{t,p}(Y,dX)=dY. ∫ d X P p , t ( X , d Y ) = d Y ∫ P t , p ( Y , d X ) = d Y .
Thus the full vector is uniform at time t t t . Conditioning on O = { e : Y e ≤ t } O=\{e:Y_e\le t\} O = { e : Y e ≤ t } proves the lemma. □
Uniformity at a fixed time does not by itself describe inputs at random internal events. We need those inputs both to identify the accepting masses and to bound the total work. The same backward argument supplies them. The following notation records expected numbers of events in a specified time-and-coordinate region; it counts every occurrence of a reverse event, not just the first.
Corollary 6.5 (Inputs at algorithm events). For a measurable region B B B of pairs ( u , x ) (u,x) ( u , x ) , let ν O , e a r r ( B ) \nu^{\mathrm{arr}}_{O,e}(B) ν O , e arr ( B ) be the expected number of arrivals of e e e with preceding observed set O O O and ( u , X O ) ∈ B (u,X_O)\in B ( u , X O ) ∈ B immediately before the arrival. For p < u < 1 p<u<1 p < u < 1 ,
ν O , e a r r ( d u , d x ) = ( 1 − u ) n − ∣ O ∣ − 1 d u d x , e ∉ O , x ∈ [ 0 , u ] O . (29) \nu^{\mathrm{arr}}_{O,e}(du,dx)=(1-u)^{n-|O|-1}\,du\,dx,\qquad e\notin O,\quad x\in[0,u]^O. \tag*{(29)} ν O , e arr ( d u , d x ) = ( 1 − u ) n − ∣ O ∣ − 1 d u d x , e ∈ / O , x ∈ [ 0 , u ] O . (29)
Similarly, let ν O , f r e v ( B ) \nu^{\mathrm{rev}}_{O,f}(B) ν O , f rev ( B ) be the expected number of reverse events with observed set O O O , triggering element f f f , and ( u , X O − f ) ∈ B (u,X_{O-f})\in B ( u , X O − f ) ∈ B just before the event. Then
ν O , f r e v ( d u , d y ) = ( 1 − u ) n − ∣ O ∣ ρ u d u d y , f ∈ Greedy ( O ) , y ∈ [ 0 , u ] O − f . (30) \nu^{\mathrm{rev}}_{O,f}(du,dy)=(1-u)^{n-|O|}\frac{\rho}{u}\,du\,dy,\qquad f\in\operatorname{Greedy}(O),\quad y\in[0,u]^{O-f}. \tag*{(30)} ν O , f rev ( d u , d y ) = ( 1 − u ) n − ∣ O ∣ u ρ d u d y , f ∈ Greedy ( O ) , y ∈ [ 0 , u ] O − f . (30)
For f ∉ Greedy ( O ) f\notin\operatorname{Greedy}(O) f ∈ / Greedy ( O ) this measure is zero. Thus, for fixed event time, observed set, and triggering element, the relevant inputs are uniform under these expected-event measures.
Proof. Stop an execution of the online algorithm immediately before a marked event and reconstruct that prefix backward, without undoing the marked event itself. The input state has the arriving element still unarrived, or the triggering element still rejected. The same interval and update matchings show that the expected-event measure of these input states is their boundary weight multiplied by the probability that the backward reconstruction terminates. That probability is one by the validity and termination argument above. The weights are therefore d u d x du\,dx d u d x at arrivals and g ′ ( u ) d u d y g'(u)\,du\,dy g ′ ( u ) d u d y at reverse events, times volume on the unarrived coordinates. There are n − ∣ O ∣ − 1 n-|O|-1 n − ∣ O ∣ − 1 such coordinates in the first case and n − ∣ O ∣ n-|O| n − ∣ O ∣ in the second, each ranging over ( u , 1 ) (u,1) ( u , 1 ) . Integrating them out gives the stated factors. Every marked occurrence gives one prefix, so this also counts repeated reverse events correctly. □
Proof of Theorem 6.1 . Before p p p the accepted set is empty. Thereafter, Lemma 6.4 and (26) give the conditional distribution D O , t D_{O,t} D O , t at each fixed horizon. At an eligible arrival, Corollary 6.5 supplies the uniform input needed for the calculation after Lemma 6.2 ; hence the accepting mass is exactly z O + e , e , t ( A ) z_{O+e,e,t}(A) z O + e , e , t ( A ) . Before p p p and at ineligible arrivals it is zero. The algorithm therefore realizes the prescribed distributions and accepting masses. The terminal independence guarantee follows from Theorem 5.2 .
For complexity, compare reverse events with accepted arrivals. Fix an observed set O O O and f ∈ Greedy ( O ) f \in\operatorname{Greedy}(O) f ∈ Greedy ( O ) . An arrival of f f f into O − f O-f O − f has input measure ( 1 − u ) n − ∣ O ∣ d u d x (1-u)^{n-\lvert O\rvert}\,du\,dx ( 1 − u ) n − ∣ O ∣ d u d x by (29) . On successful forward calls, (25) , integrated over x x x , gives output measure
( 1 − u ) n − ∣ O ∣ p u d u d y (1-u)^{n-\lvert O\rvert}\frac{p}{u}\,du\,dy ( 1 − u ) n − ∣ O ∣ u p d u d y
because reverse calls return an output with probability one. This is precisely (30) . Summing over O O O and f f f and integrating gives
E [ number of reverse events ] = E ∣ ALG ∣ ≤ n . \mathbb{E}[\text{number of reverse events}]=\mathbb{E}\lvert\operatorname{ALG}\rvert\le n. E [ number of reverse events ] = E ∣ ALG ∣ ≤ n .
This is an equality of expected counts, not a pairing within a single execution. There are also at most n n n forward calls. Integrating the uniform-input cost bounds of Lemma 6.2 against the event measures gives O ( n 2 ) O(n^2) O ( n 2 ) expected calls in total, including recursion. Each call uses polynomial local work. Updating the greedy solution and recomputing candidate event times also cost polynomial work, using the pathwise O ( n 2 ) O(n^2) O ( n 2 ) event bound.
Every comparison and independence query involves arrived elements: recursive calls only move elements of their input into the fixed background. All decisions use only observed value comparisons, arrival times, and independent randomness. This proves ordinality, the information restriction, and the asserted expected complexity.
Proof of lem:kernel
We now construct the procedures of Lemma 6.2 . As in the proof of Lemma 5.3 , we remove the largest element f f f , remember when it contributes to spanning, and recurse on O − f O-f O − f . Here its configuration coordinate also specifies whether it survives. We give the scalar updates explicitly and identify the smaller background comparisons they require. Every recursive call below has candidate set O − f O-f O − f and the same horizon t t t . A failed forward subcall fails the enclosing call.
Base cases. If σ e , H = p \sigma_{e,H}=p σ e , H = p , then e e e is already spanned by H p H_p H p , so adding it changes no spanning time; both procedures directly return their input. If O = ∅ O=\varnothing O = ∅ , the forward procedure returns the empty vector with probability p / σ e , H p/\sigma_{e,H} p / σ e , H and otherwise fails; the reverse procedure always returns the empty vector.
Unchanged spanning times. Beyond the base cases above, let f f f be the largest element of O O O . If f f f ’s spanning time stays the same with e e e added to the background, i.e., σ f , H = σ f , H + e \sigma_{f,H}=\sigma_{f,H+e} σ f , H = σ f , H + e , keep its coordinate and recurse with background H f , u H^{f,u} H f , u , where u = max { p , x f } u=\max\{p,x_f\} u = max { p , x f } forward and u = max { p , y f } u=\max\{p,y_f\} u = max { p , y f } in reverse.
The main case. Suppose
s 0 = σ f , H > s 1 = σ f , H + e , a = g ( s 0 ) , b = g ( s 1 ) . s_0=\sigma_{f,H}>s_1=\sigma_{f,H+e},\qquad a=g(s_0),\qquad b=g(s_1). s 0 = σ f , H > s 1 = σ f , H + e , a = g ( s 0 ) , b = g ( s 1 ) .
Then σ e , H = s 0 \sigma_{e,H}=s_0 σ e , H = s 0 by (18) . Under H H H , the element f f f survives exactly when x f ≤ a x_f\le a x f ≤ a ; under H + e H+e H + e , exactly when y f ≤ b y_f\le b y f ≤ b . Let
h ( u ) = min { s 0 , max { s 1 , u } } , λ = s 0 ( p − a ) s 1 ( p − b ) . h(u)=\min\{s_0,\max\{s_1,u\}\},\qquad\lambda=\frac{s_0(p-a)}{s_1(p-b)}. h ( u ) = min { s 0 , max { s 1 , u }} , λ = s 1 ( p − b ) s 0 ( p − a ) .
Here h ( u ) = σ e , H f , u h(u)=\sigma_{e,H^{f,u}} h ( u ) = σ e , H f , u by (19) , and 0 ≤ λ ≤ 1 0\le\lambda\le1 0 ≤ λ ≤ 1 , as verified below. Figure 1 specifies four branches, numbered from top to bottom, and the failure outcomes. An arrow J ⇏ J + c J\not\Rightarrow J+c J ⇒ J + c means a forward call F O − f , t , J , c F_{O-f,t,J,c} F O − f , t , J , c on the remaining coordinates; in reverse it means R O − f , t , J , c R_{O-f,t,J,c} R O − f , t , J , c . Two arrows are performed in the displayed order forward and the opposite order in reverse. The labels “w.p.” give the probabilities of choosing a branch, before making its recursive calls; unlabeled choices have probability one.
Figure 1. Forward and reverse coordinate updates in the main case s 0 > s 1 s_0 > s_1 s 0 > s 1 . Read the diagram from left to right for the forward procedure and from right to left for the reverse procedure. The middle rectangles specify recursive background changes on O − f O-f O − f ; gray ribbons lead to forward failure ⊥ \perp ⊥ . Ribbon widths are schematic.
Reading the forward procedure. If x f ≤ b x_f \le b x f ≤ b , use the first branch with probability s 1 / s 0 s_1/s_0 s 1 / s 0 , keeping y f = x f y_f=x_f y f = x f , and otherwise fail. If b < x f ≤ a b < x_f \le a b < x f ≤ a , fail immediately. If a < x f ≤ p a < x_f \le p a < x f ≤ p , use the second branch and set
y f = b + p − b p − a ( x f − a ) . y_f=b+\frac{p-b}{p-a}(x_f-a). y f = b + p − a p − b ( x f − a ) .
For x f = u > p x_f=u>p x f = u > p , choose branch 3 with probability 1 − h ( u ) / s 0 1-h(u)/s_0 1 − h ( u ) / s 0 and branch 4 with probability h ( u ) / s 0 h(u)/s_0 h ( u ) / s 0 . In the third branch, y f y_f y f is an independent uniform draw from ( b , p ) (b,p) ( b , p ) ; in the fourth, y f = x f y_f=x_f y f = x f .
The first branch corresponds to outputs containing f f f in the capacity proof: it uses only part of the available surviving mass. The second branch maps early nonsurviving coordinates from ( a , p ] (a,p] ( a , p ] to ( b , p ] (b,p] ( b , p ] . It covers only a fraction λ \lambda λ of the required mass there; the missing 1 − λ 1-\lambda 1 − λ fraction is exactly the early deficit in (21) . The third branch uses the late surplus to cover the early deficit; it is precisely the two successive comparisons in (22) , not an additional rejection rule. The fourth branch leaves f f f late.
Reading the reverse procedure. If y f ≤ b y_f \le b y f ≤ b , use the first branch, keeping x f = y f x_f=y_f x f = y f . If b < y f ≤ p b < y_f \le p b < y f ≤ p , choose the second or third branch with probabilities λ \lambda λ and 1 − λ 1-\lambda 1 − λ . In the second branch, set
x f = a + p − a p − b ( y f − b ) . x_f = a + \frac{p-a}{p-b}(y_f-b). x f = a + p − b p − a ( y f − b ) .
In the third branch, draw x f = u ∈ ( p , s 0 ) x_f=u\in(p,s_0) x f = u ∈ ( p , s 0 ) with density proportional to
s 0 − max { s 1 , u } u , (31) \frac{s_0-\max\{s_1,u\}}{u}, \tag*{(31)} u s 0 − max { s 1 , u } , (31)
and perform the two smaller reverse calls in reverse order. If y f > p y_f>p y f > p , use the fourth branch, keeping x f = y f x_f=y_f x f = y f . All reverse subcalls return an output. If a = p a=p a = p , then λ = 0 \lambda=0 λ = 0 , so the second branch is unused and no division by p − a p-a p − a is performed. Endpoint cases of zero probability do not affect the identities.
To sample (31) efficiently, draw v v v uniformly from ( s 1 , s 0 ) (s_1,s_0) ( s 1 , s 0 ) and, independently, draw u = p exp ( U ln ( s 0 / p ) ) u=p\exp(U\ln(s_0/p)) u = p exp ( U ln ( s 0 / p )) with U ∼ Unif [ 0 , 1 ] U\sim\operatorname{Unif}[0,1] U ∼ Unif [ 0 , 1 ] . Repeat until u < v u<v u < v . The successful pair has density proportional to 1 / u 1/u 1/ u on { ( u , v ) : p < u < v , s 1 < v < s 0 } \{(u,v):p<u<v,\ s_1<v<s_0\} {( u , v ) : p < u < v , s 1 < v < s 0 } , so its u u u -marginal has the required density. This is the integration region in (23) . A trial succeeds with probability
E [ ln ( v / p ) ] ln ( s 0 / p ) ≥ 1 2 . \frac{\mathbb{E}[\ln(v/p)]}{\ln(s_0/p)}\ge\frac{1}{2}. ln ( s 0 / p ) E [ ln ( v / p )] ≥ 2 1 .
concavity puts ln ( v / p ) \ln(v/p) ln ( v / p ) above its chord on [ p , s 0 ] [p,s_0] [ p , s 0 ] , and E v = ( s 1 + s 0 ) / 2 ≥ ( p + s 0 ) / 2 \mathbb{E}v=(s_1+s_0)/2\ge(p+s_0)/2 E v = ( s 1 + s 0 ) /2 ≥ ( p + s 0 ) /2 . Thus this scalar sampler uses at most two trials in expectation.
Proof of Lemma 6.2 . We prove the claims by induction on ∣ O ∣ |O| ∣ O ∣ , first checking balance, then the coordinate properties and costs.
Probability-mass balance. The base cases satisfy (25) directly. When the largest element’s spanning time is unchanged, its coordinate is copied, and the smaller call has the required factor p / σ e , H f , u = p / σ e , H p/\sigma_{e,H_f,u}=p/\sigma_{e,H} p / σ e , H f , u = p / σ e , H : by closure exchange, if f f f newly spanned e e e at some time before t t t , then e e e would newly span f f f at that time, contradicting σ f , H = σ f , H + e \sigma_{f,H}=\sigma_{f,H+e} σ f , H = σ f , H + e . Induction applies.
We now consider the main case. By (18) and (19) , the recursive calls in the first, second, and fourth branches have probability-mass balance factors p / s 1 p/s_1 p / s 1 , p / s 1 p/s_1 p / s 1 , and p / h ( u ) p/h(u) p / h ( u ) . Multiplying by the scalar change-of-variable factors and branch probabilities gives, respectively,
s 1 s 0 p s 1 = p s 0 , p − a p − b p s 1 = λ p s 0 , h ( u ) s 0 p h ( u ) = p s 0 . \frac{s_1}{s_0}\frac{p}{s_1}=\frac{p}{s_0},\qquad
\frac{p-a}{p-b}\frac{p}{s_1}=\lambda\frac{p}{s_0},\qquad
\frac{h(u)}{s_0}\frac{p}{h(u)}=\frac{p}{s_0}. s 0 s 1 s 1 p = s 0 p , p − b p − a s 1 p = λ s 0 p , s 0 h ( u ) h ( u ) p = s 0 p .
These are the required factor times the respective reverse-branch probabilities.
The third branch has two recursive factors, p / h ( u ) p/h(u) p / h ( u ) and p / min { s 1 , u } p/\min\{s_1,u\} p / min { s 1 , u } , and scalar output density 1 / ( p − b ) 1/(p-b) 1/ ( p − b ) . Its joint contribution, before normalizing the reverse choice of u u u , is
( 1 − h ( u ) s 0 ) p h ( u ) p min { s 1 , u } 1 p − b d u = p 2 s 0 s 1 ( p − b ) s 0 − max { s 1 , u } u d u , p < u < s 0 . \left(1-\frac{h(u)}{s_0}\right)\frac{p}{h(u)}\frac{p}{\min\{s_1,u\}}\frac{1}{p-b}\,du
=
\frac{p^2}{s_0s_1(p-b)}\frac{s_0-\max\{s_1,u\}}{u}\,du,\qquad p<u<s_0. ( 1 − s 0 h ( u ) ) h ( u ) p min { s 1 , u } p p − b 1 d u = s 0 s 1 ( p − b ) p 2 u s 0 − max { s 1 , u } d u , p < u < s 0 .
By (23) , the antiderivative in (21) , and the definitions of a , b a,b a , b , its integral is
p 2 s 0 s 1 ( p − b ) ∫ s 1 s 0 ln ( v / p ) d v = p s 0 ( 1 − s 0 ( p − a ) s 1 ( p − b ) ) = p s 0 ( 1 − λ ) . \frac{p^2}{s_0s_1(p-b)}\int_{s_1}^{s_0}\ln(v/p)\,dv
=
\frac{p}{s_0}\left(1-\frac{s_0(p-a)}{s_1(p-b)}\right)
=
\frac{p}{s_0}(1-\lambda). s 0 s 1 ( p − b ) p 2 ∫ s 1 s 0 ln ( v / p ) d v = s 0 p ( 1 − s 1 ( p − b ) s 0 ( p − a ) ) = s 0 p ( 1 − λ ) .
This nonnegative integral also verifies λ ≤ 1 \lambda\le1 λ ≤ 1 ; λ ≥ 0 \lambda\ge0 λ ≥ 0 follows from a ≤ p a\le p a ≤ p . Normalizing gives exactly the reverse density and branch probability. Induction and composition therefore prove (25) for every branch, including its recursive choices. Integrating over x x x shows that a uniform-input forward call succeeds with probability p / σ e , H p/\sigma_{e,H} p / σ e , H and has uniform output conditional on success.
Survivors and coordinates. In the base cases, every coordinate and survivor is unchanged. When f f f ’s spanning time is unchanged, f f f keeps its coordinate and its survival status. In the main case, in the first branch, f f f survives in both experiments and keeps its coordinate. In the other branches it does not survive, and y f ≤ x f y_f \le x_f y f ≤ x f . For the affine branch this follows from
y f − x f = − ( a − b ) ( x f − p ) p − a ≤ 0. y_f-x_f=-\frac{(a-b)(x_f-p)}{p-a}\le0. y f − x f = − p − a ( a − b ) ( x f − p ) ≤ 0.
In each branch, the recursive backgrounds record exactly when f f f is present before and after its coordinate update. Every smaller call preserves its survivor set, fixes survivors’ coordinates, and decreases other coordinates forward. Their composition gives properties (ii) and (iii). Reverse calls read these same pairs in the opposite direction.
Number of recursive calls. On a uniform forward input, the remaining coordinates are uniform conditional on x f x_f x f and the chosen branch. By the induction hypothesis, the output of a smaller call conditioned on success is uniform. Inductively, every recursive call also receives uniform input.
In the main case, let P i P_i P i be the probability of making exactly i i i direct recursive calls. Only the third branch can make two; making no child call means an immediate failure in the surviving range. Consequently,
P 0 = a − b t + b t ( 1 − s 1 s 0 ) = a − ( s 1 / s 0 ) b t . P_0=\frac{a-b}{t}+\frac{b}{t}\left(1-\frac{s_1}{s_0}\right)=\frac{a-(s_1/s_0)b}{t}. P 0 = t a − b + t b ( 1 − s 0 s 1 ) = t a − ( s 1 / s 0 ) b .
P 2 = 1 t ∫ p t ( 1 − h ( u ) s 0 ) p h ( u ) d u = 1 t ∫ s 1 s 0 p ( v − p ) v 2 d v ≤ a − b t ≤ P 0 . P_2=\frac{1}{t}\int_p^t\left(1-\frac{h(u)}{s_0}\right)\frac{p}{h(u)}\,du=\frac{1}{t}\int_{s_1}^{s_0}\frac{p(v-p)}{v^2}\,dv\le\frac{a-b}{t}\le P_0. P 2 = t 1 ∫ p t ( 1 − s 0 h ( u ) ) h ( u ) p d u = t 1 ∫ s 1 s 0 v 2 p ( v − p ) d v ≤ t a − b ≤ P 0 .
Thus the expected number of children is 1 − P 0 + P 2 ≤ 1 1-P_0+P_2\le1 1 − P 0 + P 2 ≤ 1 . Each recursive call has one fewer element in its candidate set, so induction bounds the expected total number of recursive forward calls by 1 + ∣ O ∣ 1+|O| 1 + ∣ O ∣ . The unchanged-spanning-time case has one child and satisfies the same bound; the base cases have none.
The branchwise balance identities also match successful forward and reverse trees of recursive calls, with the same number of nodes. Hence a reverse call on uniform input has the recursive-call count of a successful forward call on uniform input. Since that success probability is p / σ e , H ≥ p = 1 / e p/\sigma_{e,H}\ge p=1/e p / σ e , H ≥ p = 1/ e , its expected number of recursive reverse calls is at most e ( ∣ O ∣ + 1 ) e(|O|+1) e ( ∣ O ∣ + 1 ) .
Finally, the spanning times used by a call are found by checking rank at the finitely many fixed background times. Each call therefore needs only polynomially many independence queries and arithmetic operations outside its recursive calls. The only repeated scalar sampling takes at most two trials in expectation. All elements involved belong to the original call’s candidates, background, or added element e e e . This proves property (iv) and completes the lemma. □
Extensions and Consequences
We first use the characterization to compare probability and ordinal competitiveness on special classes and examine finite-size guarantees. We then extend the snapshot algorithm to intersections of matroids and derive a submodular consequence of the optimal single-matroid algorithm. In these last two applications, competitiveness refers to the expected objective value.
Examples and finite-size evidence
The characterization in § 4.2 supports both algorithm construction and impossibility proofs. Uniform matroids separate the two competitive objectives, while linear matroids admit stronger finite-size guarantees.
Uniform matroids: separating the two objectives. Let U k , n U_{k,n} U k , n be the matroid on n n n elements whose independent sets have size at most k k k .
Theorem 7.1 (Uniform matroids). The optimal per-element selection fraction among ordinal algorithms satisfies 1 ρ ( U k , n ) = 1 − Θ ( log k k ) \frac{1}{\rho(U_{k,n})}=1-\Theta\left(\sqrt{\frac{\log k}{k}}\right) ρ ( U k , n ) 1 = 1 − Θ ( k l o g k ) as k → ∞ k\to\infty k → ∞ , uniformly over n ≥ 2 k n\ge2k n ≥ 2 k . In contrast, an ordinal algorithm can achieve expected-value fraction 1 − O ( k − 1 / 2 ) 1-O(k^{-1/2}) 1 − O ( k − 1/2 ) .
Proof. The probability statement combines Propositions B.1 and B.2. The expected-value guarantee follows from Kleinberg’s algorithm [45 , 66 ] .
Thus the extra log k \sqrt{\log k} log k loss in the per-element guarantee is necessary, answering the question of Soto, Turkieltaub, and Verdugo [66 ] . The constructive bound uses relative-rank thresholds and independent thinning; its parameters and analysis are given in Proposition B.1.
The matching lower bound already holds for n = 2 k n=2k n = 2 k and uses a single midpoint snapshot. If each optimum element is selected with probability at least 1 − ε 1-\varepsilon 1 − ε , capacity permits at most k ε k\varepsilon k ε expected selections outside the optimum, while the k k k -th largest element can be missed with probability at most ε \varepsilon ε . Let X X X count the top k k k elements among the first k k k arrivals, so X ∼ Hypergeometric ( 2 k , k , k ) X\sim\operatorname{Hypergeometric}(2k,k,k) X ∼ Hypergeometric ( 2 k , k , k ) . Combining these two requirements and eliminating the algorithm’s midpoint acceptance marginals gives
2 k ε ≥ ∑ r = 1 k min { Pr [ X < r ] , r Pr [ X = r ] } . 2k\varepsilon\ge\sum_{r=1}^{k}\min\{\Pr[X<r],r\Pr[X=r]\}. 2 k ε ≥ r = 1 ∑ k min { Pr [ X < r ] , r Pr [ X = r ]} .
For Ω ( k log k ) \Omega(\sqrt{k\log k}) Ω ( k log k ) values of r r r , the summand is bounded below by an absolute positive constant. This forces ε = Ω ( log k / k ) \varepsilon=\Omega(\sqrt{\log k/k}) ε = Ω ( log k / k ) . Proposition B.2 proves the certificate and extends the bound to every n ≥ 2 k n\ge2k n ≥ 2 k . No threshold or monotonicity assumption on the algorithm is needed.
Linear matroids: the finite-size rank-one guarantee. For n ≥ 2 n\ge2 n ≥ 2 and 1 ≤ s < n 1\le s<n 1 ≤ s < n , write c n ( s ) = s n ∑ i = s n − 1 1 i c_n(s)=\frac{s}{n}\sum_{i=s}^{n-1}\frac{1}{i} c n ( s ) = n s ∑ i = s n − 1 i 1 for the success probability of the classical secretary rule that rejects the first s s s arrivals.
Theorem 7.2 (Linear matroids). For every linear matroid on n ≥ 2 n\ge2 n ≥ 2 elements, known in advance, and every $1\le s<n, ∗ t h e r e i s a n o r d i n a l a l g o r i t h m a c c e p t i n g e a c h e l e m e n t o f ∗ , *there is an ordinal algorithm accepting each element of* , ∗ t h er e i s an or d ina l a l g or i t hma cce pt in g e a c h e l e m e n t o f ∗ \operatorname{Greedy}(V) with probability exactly c n ( s ) c_n(s) c n ( s ) , for every nonnegative value assignment.
Choosing the best cutoff gives ρ ( M ) ≤ ρ ( U 1 , n ) < e \rho(\mathcal{M})\le\rho(U_{1,n})<e ρ ( M ) ≤ ρ ( U 1 , n ) < e whenever M \mathcal{M} M has positive rank. Thus the guarantee improves on 1 / e 1/e 1/ e for every finite n n n . This covers representable classes such as graphic, transversal, and laminar matroids [30 ] , but only when the matroid is known in advance.
The construction bounds the expected dimension of the intersection of the accepted span with every subspace. The one-dimensional constraints ensure sufficient mass on sets that do not span an arriving candidate; the higher-dimensional constraints allow these availability guarantees to be maintained together. Appendix § 10 .§ 2 gives the feasible family and proof. The construction is finite, with no polynomial running-time bound asserted.
Computational evidence beyond linear matroids. Let ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) denote the optimal expected-value competitive ratio among ordinal algorithms. Numerically optimizing the LP of Corollary 4.3 suggested the stronger finite-size comparison
ρ o r d ( M ) ≤ ρ o r d ( U 1 , n ) . \rho_{\mathrm{ord}}(\mathcal{M}) \le\rho_{\mathrm{ord}}(U_{1,n}). ρ ord ( M ) ≤ ρ ord ( U 1 , n ) .
Every tested instance satisfied this inequality up to numerical precision. The computations covered every positive-rank matroid on seven elements and 1655 of the 1723 positive-rank matroids on eight elements, including 43 of the 44 nonrepresentable ones. These are floating-point observations for the expected-value objective, rather than proofs of the stronger per-element guarantee. Appendix § 11 gives the computational reductions, coverage, and numerical details.
Intersection of matroids
Fix matroids M j = ( V , I j ) \mathcal{M}_j=(V,\mathcal{I}_j) M j = ( V , I j ) for j ∈ [ k ] j \in[k] j ∈ [ k ] , with k ≥ 1 k \ge1 k ≥ 1 , and fixed nonnegative values v e v_e v e . Let I ⋆ I^\star I ⋆ be a maximum-value common independent set. For an auxiliary value vector a = ( a e ) e ∈ V a=(a_e)_{e\in V} a = ( a e ) e ∈ V , write a ( A ) = ∑ e ∈ A a e a(A)=\sum_{e\in A}a_e a ( A ) = ∑ e ∈ A a e and let Greedy j ( T ; a ) \operatorname{Greedy}_j(T;a) Greedy j ( T ; a ) be greedy in M j \mathcal{M}_j M j on T T T , using values a a a and the fixed tie-breaking order. The individual optima need not have a valuable intersection, even when I ⋆ I^\star I ⋆ has large value. The preprocessing of Feldman, Svensson, and Zenklusen [33 ] supplies auxiliary values for which their overlap is valuable in expectation.
Theorem 7.3. There is an 8 k 2 ( k + 1 ) 8k^2(k+1) 8 k 2 ( k + 1 ) -competitive secretary algorithm under the intersection of k k k matroids. It needs only n = ∣ V ∣ n=|V| n = ∣ V ∣ , comparisons of values, and independence queries on arrived elements in each matroid, and uses O ( k n 2 ) O(kn^2) O ( k n 2 ) independence queries.
Proof. Preprocessing. Let p 0 = 1 − 1 / ( 2 k ) p_0=1-1/(2k) p 0 = 1 − 1/ ( 2 k ) , draw L ∼ Bin ( n , p 0 ) L\sim\operatorname{Bin}(n,p_0) L ∼ Bin ( n , p 0 ) , and reject the first L L L arrivals, forming a sample P P P . Each element belongs to P P P independently with probability p 0 p_0 p 0 . Let Greedy ∩ ( T ) \operatorname{Greedy}_{\cap}(T) Greedy ∩ ( T ) be decreasing-value greedy on T T T subject to all k k k constraints: it adds each element whenever the resulting set is independent in every matroid. Define
a e = { v e , e ∉ P and e ∈ Greedy ∩ ( P + e ) , 0 , otherwise . a_e =
\begin{cases}
v_e, & e\notin P \text{ and } e\in\operatorname{Greedy}_{\cap}(P+e),\\
0, & \text{otherwise}.
\end{cases} a e = { v e , 0 , e ∈ / P and e ∈ Greedy ∩ ( P + e ) , otherwise .
Greedy scans every element with positive auxiliary value before the zero-valued elements. Thus the overlap guarantee of Feldman, Svensson, and Zenklusen [33 Theorem 3.3] gives
E P [ a ( B + ( a ) ) ] ≥ v ( I ⋆ ) 4 k 2 , B + ( a ) = { e : a e > 0 } ∩ ⋂ j = 1 k Greedy j ( V ; a ) . (32) \mathbb{E}_P[a(B^+(a))] \ge\frac{v(I^\star)}{4k^2}, \qquad B^+(a)=\{e:a_e>0\}\cap\bigcap_{j=1}^{k}\operatorname{Greedy}_j(V;a). \tag*{(32)} E P [ a ( B + ( a ))] ≥ 4 k 2 v ( I ⋆ ) , B + ( a ) = { e : a e > 0 } ∩ j = 1 ⋂ k Greedy j ( V ; a ) . (32)
In particular, B + ( a ) ⊆ V ∖ P B^+(a)\subseteq V\setminus P B + ( a ) ⊆ V ∖ P . The value a e a_e a e is computable at the arrival of e e e using only P + e P+e P + e . It therefore suffices to select each element of B + ( a ) B^+(a) B + ( a ) with conditional probability at least 1 / ( 2 ( k + 1 ) ) 1/(2(k+1)) 1/ ( 2 ( k + 1 )) , given P P P . The snapshot argument below supplies this probability by requiring the element to precede at most one exchange partner per matroid.
A common reference set. Conditional on P P P , let U = V ∖ P U=V\setminus P U = V ∖ P and m = ∣ U ∣ m=|U| m = ∣ U ∣ . If m = 0 m=0 m = 0 , return the empty set. Otherwise, run Algorithm 1 on all m m m remaining elements with values a a a and fresh randomness. Its initial reference set is a new sample from U U U , not the preprocessing sample P P P . Require the preservation test in every matroid:
Greedy j ( C ′ ; a ) ∩ F = Greedy j ( C ; a ) ∩ F ( j ∈ [ k ] ) . \operatorname{Greedy}_j(C';a) \cap F = \operatorname{Greedy}_j(C;a) \cap F \qquad(j \in[k]). Greedy j ( C ′ ; a ) ∩ F = Greedy j ( C ; a ) ∩ F ( j ∈ [ k ]) .
If the test passes, accept the current element exactly when it belongs to every proposed greedy set, and perform the reference-set update whether or not it is accepted. After each processing step, add its element to F F F . As in § 2 , sample steps cannot be accepted because they are deleted from the proposed set.
We retain all elements of U U U in the stream, including those assigned auxiliary value zero. Thus the second algorithm knows its input size m m m without knowing how many future elements will pass the preprocessing test. Its invariant A L G ⊆ ⋂ j = 1 k Greedy j ( C ; a ) \mathrm{ALG} \subseteq\bigcap_{j=1}^{k} \operatorname{Greedy}_j(C;a) ALG ⊆ ⋂ j = 1 k Greedy j ( C ; a ) proves feasibility in all k k k matroids.
Snapshot and acceptance probability. Conditional on P P P , the auxiliary values a a a are fixed and the remaining arrival order is uniform. The conjunction of the k k k preservation tests has the same answer at C C C and C ⊕ e C \oplus e C ⊕ e . Thus each update can be undone by the same rule, and Lemma 2.4 and Corollary 2.5 apply unchanged. For each fixed target e e e , the configuration C e C_e C e immediately before its processing step is therefore uniform on 2 U 2^U 2 U , independently of the uniformly random processing order.
Fix e ∈ B + ( a ) e \in B^{+}(a) e ∈ B + ( a ) and condition on C e = T C_e = T C e = T with e ∉ T e \notin T e ∈ / T . This is a real arrival, since no earlier step changes the membership of e e e . By greedy monotonicity (Lemma 2.1 (i)), e ∈ Greedy j ( T + e ; a ) e \in\operatorname{Greedy}_j(T+e;a) e ∈ Greedy j ( T + e ; a ) for every j j j . Inserting e e e displaces at most one element in each matroid. Let D D D be the set of distinct displaced elements. Once P , T , e P,T,e P , T , e are fixed, D D D is fixed and ∣ D ∣ ≤ k |D| \leq k ∣ D ∣ ≤ k .
The test passes exactly when no element of D D D has been processed, or equivalently when e e e precedes them all in the processing order. The snapshot property leaves that order uniform, giving
Pr [ e ∈ A L G ∣ P , C e = T ] = 1 ∣ D ∣ + 1 ≥ 1 k + 1 . \Pr[e \in\mathrm{ALG} \mid P,C_e=T] = \frac{1}{|D|+1} \geq\frac{1}{k+1}. Pr [ e ∈ ALG ∣ P , C e = T ] = ∣ D ∣ + 1 1 ≥ k + 1 1 .
Since Pr [ e ∉ C e ∣ P ] = 1 / 2 \Pr[e \notin C_e \mid P] = 1/2 Pr [ e ∈ / C e ∣ P ] = 1/2 , each element of B + ( a ) B^{+}(a) B + ( a ) is accepted with conditional probability at least 1 / ( 2 ( k + 1 ) ) 1/(2(k+1)) 1/ ( 2 ( k + 1 )) . Therefore,
E [ v ( A L G ) ] ≥ E [ a ( A L G ) ] ≥ E P [ a ( B + ( a ) ) ] 2 ( k + 1 ) ≥ v ( I ⋆ ) 8 k 2 ( k + 1 ) . \mathbb{E}[v(\mathrm{ALG})] \geq\mathbb{E}[a(\mathrm{ALG})] \geq\frac{\mathbb{E}_P[a(B^{+}(a))]}{2(k+1)} \geq\frac{v(I^\star)}{8k^2(k+1)}. E [ v ( ALG )] ≥ E [ a ( ALG )] ≥ 2 ( k + 1 ) E P [ a ( B + ( a ))] ≥ 8 k 2 ( k + 1 ) v ( I ⋆ ) .
Finally, preprocessing uses at most n n n common-greedy scans, each requiring O ( k n ) O(kn) O ( k n ) independence queries. The second stage uses at most two greedy scans per matroid at each of its m m m processing steps. All queries involve only P + e P+e P + e or the current and proposed reference sets, hence only arrived elements. The total is O ( k n 2 ) O(kn^2) O ( k n 2 ) .
Submodular objectives
A set function f : 2 V → R ≥ 0 f:2^V \to\mathbb{R}_{\geq0} f : 2 V → R ≥ 0 is submodular if f ( A + e ) − f ( A ) ≥ f ( B + e ) − f ( B ) f(A+e)-f(A) \geq f(B+e)-f(B) f ( A + e ) − f ( A ) ≥ f ( B + e ) − f ( B ) whenever A ⊆ B A \subseteq B A ⊆ B and e ∉ B e \notin B e ∈ / B ; it need not be monotone. In the submodular matroid secretary problem, the goal is to maximize E [ f ( A L G ) ] \mathbb{E}[f(\mathrm{ALG})] E [ f ( ALG )] , compared with max I ∈ I f ( I ) \max_{I \in\mathcal{I}} f(I) max I ∈ I f ( I ) . The algorithm knows n n n and may query f f f and independence on sets of arrived elements. The reduction below additionally requires an upper bound on every element’s selection probability. Our survivor construction provides this because only elements of the auxiliary early sample can survive.
Theorem 7.4 (Feldman and Zenklusen [35 ] ). Let α ≥ 1 \alpha\ge1 α ≥ 1 . Suppose an additive matroid secretary algorithm is α \alpha α -competitive and selects every element with probability at most 1 / α 1/\alpha 1/ α . Then there is a 96 α 96\alpha 96 α -competitive algorithm for nonnegative submodular objectives in the same information model. The reduction preserves expected polynomial arithmetic and oracle complexity.
Corollary 7.5. For every matroid and every nonnegative submodular objective, there is a 96 e 96e 96 e -competitive secretary algorithm with expected polynomial arithmetic and oracle complexity. It needs only the number of elements and independence and value-oracle queries on subsets of arrived elements.
Proof. The algorithm of Theorem 6.1 is e e e -competitive and has terminal distribution D V , 1 \mathcal{D}_{V,1} D V , 1 . In the survivor experiment defining this distribution, every survivor belongs to the auxiliary early sample E E E . Hence, for every e ∈ V e \in V e ∈ V ,
Pr [ e ∈ A L G ] ≤ Pr [ e ∈ E ] = p = 1 / e . \Pr[e \in\mathrm{ALG}] \le\Pr[e \in E] = p = 1/e. Pr [ e ∈ ALG ] ≤ Pr [ e ∈ E ] = p = 1/ e .
Apply Theorem 7.4 with α = e \alpha= e α = e .
Acknowledgments and AI Methodology Statement
Relation to the predecessor manuscripts. This paper merges and extends the preprints [64 , 1 , 42 ] into a unified treatment. The combinatorial snapshot algorithm was presented by Singla [64 ] ; the optimal single-sample prophet inequality by Abdi, Banihashem, Hajiaghayi, and Mittal [1 ] ; and the optimal general-matroid secretary algorithm and its efficient implementation by Huang [42 ] . The paper [1 ] also gave, in the known-matroid model, an optimal secretary algorithm for linear matroids and a black-box reduction yielding a 64-competitive algorithm for arbitrary matroids. This treatment organizes the results around snapshot invariants, acceptance distributions, and survival simulation.
AI usage in research. The results came from combining the authors’ direction with the technical capabilities of AI models. The authors made judgment calls about which approaches to pursue, used linear-program computations to guide the search, and directed the exploration toward simulating an offline distribution of accepted elements. The linear program in § 4 and the computations with it were devised and carried out without AI models, starting in February 2026.11 Interactions with models available through ChatGPT Pro, especially GPT Astra, were used in obtaining the main algorithmic guarantees, including Theorems 2.2 , 3.1 , 5.2 and 7.2 ; GPT Sol 5.6 was also used in developing the single-sample prophet and linear-matroid results. Along the way, the authors explored single-sample algorithms [53 , 22 ] , pairings of sample and real elements [61 ] , the minimax principle [46 ] , and reductions to free-order secretary through tangential sequences [31 ] . Recognizing that the survival-comparison and online-realization arguments are algorithmic led from partial, computationally inefficient guarantees to the efficient implementation. The authors checked the resulting proofs.
AI usage in writing. This manuscript was prepared with the assistance of ChatGPT and Claude, which were used to draft and revise the exposition, including the unified presentation of results that first appeared in separate papers. The authors have checked all mathematical arguments and take full responsibility for the contents.
Acknowledgments. Singla is grateful to Anupam Gupta and S. Matthew Weinberg for discussions on the matroid secretary problem over the past decade, and thanks Thomas Kesselheim, Robert Kleinberg, Wenzheng Li, Thiago Oliveira, Kalen Patton, Rebecca Reiffenhäuser, Aviad Rubinstein, Siddharth M. Sundaram, and Ola Svensson for related discussions, and Anupam Gupta, S. Matthew Weinberg, and Robert Kleinberg for comments on early versions of [64 ] . Banihashem thanks Neel Patel for pointing out the existence of the reduction from matroid secretary to constant-sample prophet inequalities. Banihashem, Hajiaghayi, and Mittal thank Dariusz Kowalski, Piotr Krysta, and Jan Olkowski for early discussions and joint work on the matroid secretary problem, which led to [10 ] on graphic matroids. Huang thanks Dongchen Li, Zahra Parsaeian, and Zixuan Zhu for early discussions and joint work on the matroid secretary problem.
Why Natural Greedy Rules Fail
Many sample-based algorithms for matroid secretary exploit greedy monotonicity (Lemma 2.1 ), i.e., an element e ∈ Greedy ( V ) e \in\operatorname{Greedy}(V) e ∈ Greedy ( V ) of the global optimum is also part of the optimal solution on any subset containing e e e . This suggests a naïve algorithm that discards the first roughly n / 2 n/2 n /2 elements to use as a sample S S S and then accepts an element e e e if and only if e ∈ Greedy ( S ∪ { e } ) e \in\operatorname{Greedy}(S \cup\{e\}) e ∈ Greedy ( S ∪ { e }) . In the secretary setting, this algorithm has good total value since it accepts every e ∈ Greedy ( V ) ∖ S e \in\operatorname{Greedy}(V) \setminus S e ∈ Greedy ( V ) ∖ S , but its accepted set need not be independent. For example, consider the graphic matroid in Figure 2 (a): the sample consists of edges ( u , a ) (u,a) ( u , a ) , ( u , b ) (u,b) ( u , b ) , ( u , c ) (u,c) ( u , c ) of weight 1, and the real elements are ( a , b ) (a,b) ( a , b ) , ( b , c ) (b,c) ( b , c ) , ( c , a ) (c,a) ( c , a ) of weight 2. The naïve algorithm accepts all three real edges, which form a cycle.
(a) The naïve rule accepts a cycle.
(b) A hat; real arrival order e 1 , e 2 , h e_1,e_2,h e 1 , e 2 , h .
Figure 2. Dashed edges belong to the sample; solid edges are real. In (a), every real edge individually belongs to the optimum when added to the sample. In (b), contracting e 1 e_1 e 1 allows greedy to accept e 2 e_2 e 2 , whereas ordinary greedy would drop e 1 e_1 e 1 .
Greedy algorithms. A natural approach to go beyond the naïve algorithm maintains an independent set I t I_t I t at all times t t t , initialized to the optimum solution on the sample, and containing all accepted elements. It accepts the next real element e e e if and only if the optimum solution on I t ∪ { e } I_t \cup\{e\} I t ∪ { e } after contracting the accepted elements contains e e e , and updates I t I_t I t to this new solution (with the contracted elements included).
The authors of [7 ] considered this and related “greedy” algorithms. More formally, their algorithms maintain an independent set I t I_t I t that spans the previously observed elements and satisfies two properties: (i) I t I_t I t contains all accepted elements, and (ii) I t I_t I t contains no real element rejected after the sampling stage. The choice of I t I_t I t is flexible, but the contracted-greedy acceptance rule above is mandatory. They show that this class cannot be constant-competitive on graphic matroids, using hat-shaped instances.
A small hat illustrates the failure mechanism; see Figure 2 (b). The sample contains a u u u –v v v path with edge weights 4, 2, while the real elements form another u u u –v v v path with weights 1, 3, followed by a base edge of arbitrarily large weight H H H . The greedy algorithm accepts the weight-1 edge since it preserves independence. It then accepts the weight-3 edge: after contracting the first acceptance, the optimum keeps weights 4, 3, 1 and drops the weight-2 sample. The two accepted edges now connect u u u to v v v , making the heavy base edge infeasible.
The combinatorial secretary algorithm (Algorithm 1) builds on two ideas.
Idea 1: Preserve processed greedy decisions (Step 2 of Algorithm 1). Rather than making the greedy decision from a single independent set I t I_t I t after contracting the accepted elements, maintain a reference set C C C and only consider e e e if the proposed update preserves greedy membership on the processed elements. In particular, we do not contract the already accepted elements; instead, Step 2 ensures that these greedy memberships do not change. This immediately guarantees feasibility, since the accepted elements always belong to the optimum of the current reference set.
On the hat above, after sampling s 1 , s 2 s_1, s_2 s 1 , s 2 , consider the processing order e 1 , e 2 , h , s 1 , s 2 e_1, e_2, h, s_1, s_2 e 1 , e 2 , h , s 1 , s 2 , so both sample elements are processed after all real arrivals. The weight-1 edge e 1 e_1 e 1 is accepted, but inserting the weight-3 edge e 2 e_2 e 2 would change the ordinary optimum from weights 4, 2, 1 to 4, 3, 2, removing e 1 e_1 e 1 . Step 2 therefore rejects this update, and the heavy base can subsequently be accepted. Thus, unlike contracted greedy, our algorithm can reject an element even when it improves the optimum subject to retaining earlier acceptances.
Although this idea avoids the harmful exchange above, if we update the reference set only when we accept an element, the algorithm can get stuck on simple matroids. For example, consider a uniform matroid of rank r r r on n = 4 r n = 4r n = 4 r elements with values in [ 1 , 1 + ε ] [1, 1 + \varepsilon] [ 1 , 1 + ε ] , with distinct perturbations to avoid ties. In the secretary algorithm, this modification keeps C = S ∪ A L G C = S \cup\mathrm{ALG} C = S ∪ ALG : sample elements are never deleted. Once the smallest element of Greedy( C ) (C) ( C ) is an accepted element, every improving insertion would remove it and is forbidden. The algorithm can then remain permanently stuck with many unused slots. A heuristic calculation suggests that it accepts only O ( r ) O(\sqrt{r}) O ( r ) elements in expectation, rather than Ω ( r ) \Omega(r) Ω ( r ) .12
Idea 2: Update reversibly (Step 2(b) of Algorithm 1). To overcome this rigidity, the algorithm updates the reference set whenever the element passes Step 2, even when it is not accepted. In the secretary algorithm, this allows consistent deletions of sample elements. Such a deletion can bring a smaller, not-yet-processed sample element into the optimum, allowing a later real arrival to replace that sample without removing an earlier acceptance. This also explains why we retain the whole reference set rather than only its current optimum: sampled elements outside that optimum can become relevant after later updates.
Because Step 2 compares the same two optima in either direction, every permitted update is reversible; this is the basis of the snapshot lemma (Lemma 2.4 ).
Feasible Families for Special Classes
This appendix proves the special-class results in § 7.1 . For uniform matroids, a threshold-and-thinning construction and a matching midpoint lower bound establish the probability guarantee in Theorem 7.1 . For linear matroids, a recursive feasible family based on a subspace invariant proves Theorem 7.2 .
Uniform matroids
We prove the two probability bounds used in Theorem 7.1 . Recall that U k , n U_{k,n} U k , n has all subsets of size at most k k k as its independent sets. We first recover the known 1 − O ( log k / k ) 1 - O(\sqrt{\log k/k}) 1 − O ( log k / k ) per-element probability guarantee [66 ] , then prove the matching lower bound.
Proposition B.1. For n ≥ k ≥ 2 n \ge k \ge2 n ≥ k ≥ 2 , the probability L P LP L P for the uniform matroid U k , n U_{k,n} U k , n has value at least 1 − O ( log k / k ) 1 - O(\sqrt{\log k/k}) 1 − O ( log k / k ) , with an absolute constant independent of n n n . Proof. It suffices to consider k ≥ 3 k \ge3 k ≥ 3 , since bounded values of k k k can be absorbed into the constant. Set
b = k log k , q = k − b k + 6 b , r i = min { i , ⌊ k i n + 3 b i n ⌋ } . b = \sqrt{k \log k}, \qquad q = \frac{k-b}{k+6b}, \qquad r_i = \min\left\{i,\left\lfloor\frac{ki}{n}+3b\sqrt{\frac{i}{n}}\right\rfloor\right\}. b = k log k , q = k + 6 b k − b , r i = min { i , ⌊ n k i + 3 b n i ⌋ } .
Call an arrival at position i i i eligible if it is among the first r i r_i r i elements of the observed value order.
Starting from μ ∅ ( ∅ ) = 1 \mu_{\varnothing}(\varnothing)=1 μ ∅ ( ∅ ) = 1 , define the accepting masses by
y O , e ( A ) = q μ O − e ( A ) 1 { e is eligible , ∣ A ∣ < k } , y_{O,e}(A)=q\mu_{O-e}(A)\mathbf{1}\{e\text{ is eligible},\ |A|<k\}, y O , e ( A ) = q μ O − e ( A ) 1 { e is eligible , ∣ A ∣ < k } ,
and define each μ O \mu_O μ O recursively by consistency (4) . Capacity holds directly, and induction gives nonnegative, normalized distributions supported on sets of size at most k k k . The realizing algorithm accepts each eligible arrival with probability q q q , independently, until it has accepted k k k elements.
Consider this algorithm without the limit of k k k acceptances, and let Z Z Z be its total number of acceptances. The successive relative ranks, with rank 1 denoting the largest element observed so far, are independent, with the rank at position i i i uniform on [ i ] [i] [ i ] . Thus Z Z Z is a sum of independent Bernoulli variables, and
E Z = q ∑ i = 1 n r i i ≤ q ( k + 3 b n ∑ i = 1 n i − 1 / 2 ) ≤ q ( k + 6 b ) = k − b . \mathbb{E}Z=q\sum_{i=1}^{n}\frac{r_i}{i}\le q\left(k+\frac{3b}{\sqrt{n}}\sum_{i=1}^{n}i^{-1/2}\right)\le q(k+6b)=k-b. E Z = q i = 1 ∑ n i r i ≤ q ( k + n 3 b i = 1 ∑ n i − 1/2 ) ≤ q ( k + 6 b ) = k − b .
A Chernoff bound therefore gives
Pr [ Z ≥ k ] ≤ exp ( − ( k − E Z ) 2 2 k ) ≤ k − 1 / 2 . \Pr[Z\ge k]\le\exp\left(-\frac{(k-\mathbb{E}Z)^2}{2k}\right)\le k^{-1/2}. Pr [ Z ≥ k ] ≤ exp ( − 2 k ( k − E Z ) 2 ) ≤ k − 1/2 .
Fix e ∈ Greedy ( V ) e\in\operatorname{Greedy}(V) e ∈ Greedy ( V ) and condition on its arrival at position i i i . Its relative rank is 1 + H 1+H 1 + H , where H H H counts the larger elements among the preceding i − 1 i-1 i − 1 arrivals. Thus H H H is hypergeometric, with mean at most a = k i / n a=ki/n a = k i / n . Suppose a ≥ log k a\ge\log k a ≥ log k . If r i = i r_i=i r i = i , eligibility is automatic. Otherwise, failure of the rank test implies
H ≥ r i ≥ a + 3 a log k − 1 ≥ a + 2 a log k . H\ge r_i\ge a+3\sqrt{a\log k}-1\ge a+2\sqrt{a\log k}. H ≥ r i ≥ a + 3 a log k − 1 ≥ a + 2 a log k .
The hypergeometric Chernoff bound gives
Pr [ e is ineligible ∣ e arrives at i ] ≤ exp ( − 4 a log k 2 ( a + 2 3 a log k ) ) ≤ k − 1 . \Pr[e\text{ is ineligible}\mid e\text{ arrives at }i]\le\exp\left(-\frac{4a\log k}{2\left(a+\frac{2}{3}\sqrt{a\log k}\right)}\right)\le k^{-1}. Pr [ e is ineligible ∣ e arrives at i ] ≤ exp ( − 2 ( a + 3 2 a log k ) 4 a log k ) ≤ k − 1 .
The positions with k i / n < log k ki/n<\log k k i / n < log k have total probability at most log k / k \log k/k log k / k . Hence e e e passes the rank test and its independent acceptance coin succeeds with probability at least q ( 1 − log k / k − k − 1 ) q(1-\log k/k-k^{-1}) q ( 1 − log k / k − k − 1 ) . Outside the event Z ≥ k Z\ge k Z ≥ k , all such acceptances fit within capacity. Consequently,
Pr [ e ∈ A L G ] ≥ q ( 1 − log k k − 1 k ) − 1 k = 1 − O ( log k k ) . \Pr[e\in\mathrm{ALG}]\ge q\left(1-\frac{\log k}{k}-\frac{1}{k}\right)-\frac{1}{\sqrt{k}}=1-O\left(\sqrt{\frac{\log k}{k}}\right). Pr [ e ∈ ALG ] ≥ q ( 1 − k log k − k 1 ) − k 1 = 1 − O ( k log k ) .
This holds for every full value order and every e ∈ Greedy ( V ) e\in\operatorname{Greedy}(V) e ∈ Greedy ( V ) , proving all terminal inclusion constraints.
Proposition B.2 (Matching probability lower bound). For n ≥ 2 k n\ge2k n ≥ 2 k and k ≥ 128 k\ge128 k ≥ 128 , the probability LP for U k , n U_{k,n} U k , n has value at most 1 − 1 64 log k k 1-\frac{1}{64}\sqrt{\frac{\log k}{k}} 1 − 64 1 k l o g k . Consequently, together with Proposition B.1, its value is 1 − Θ ( log k / k ) 1-\Theta(\sqrt{\log k/k}) 1 − Θ ( log k / k ) , uniformly over n ≥ 2 k n\ge2k n ≥ 2 k as k → ∞ k\to\infty k → ∞ .
Proof. First let n = 2 k n=2k n = 2 k . By Theorem 4.1, a feasible point of value 1 − ε 1-\varepsilon 1 − ε yields an ordinal algorithm selecting each of the k k k largest elements with probability at least 1 − ε 1-\varepsilon 1 − ε . Average the algorithm over permutations of the element labels; this preserves its guarantee. Number the elements 1 , … , 2 k 1,\ldots,2k 1 , … , 2 k by decreasing value, for analysis only, and let S S S be the first k k k arrivals.
The relative arrival order within S S S is independent of its set of global ranks. By symmetry and ordinality, there are numbers a r ∈ [ 0 , 1 ] a_r\in[0,1] a r ∈ [ 0 , 1 ] such that, conditional on any possible S S S , its r r r -th largest element has been accepted by this midpoint with probability a r a_r a r . Put
X = ∣ S ∩ [ k ] ∣ , g r = Pr [ X = r ] = ( k r ) 2 ( 2 k k ) , b r = Pr [ X < r ] . X=|S\cap[k]|,\qquad g_r=\Pr[X=r]=\frac{\binom{k}{r}^{2}}{\binom{2k}{k}},\qquad b_r=\Pr[X<r]. X = ∣ S ∩ [ k ] ∣ , g r = Pr [ X = r ] = ( k 2 k ) ( r k ) 2 , b r = Pr [ X < r ] .
Let W W W count the accepted elements of S S S outside [ k ] [k] [ k ] , and let D D D be the event that element k k k belongs to S S S but is rejected. The terminal inclusion constraints and the capacity bound give E W ≤ k ε \mathbb{E}W\le k\varepsilon E W ≤ k ε , while Pr [ D ] ≤ ε \Pr[D]\le\varepsilon Pr [ D ] ≤ ε . The r r r -th largest element of S S S is outside [ k ] [k] [ k ] exactly when X < r X<r X < r . Conditional on X = r X=r X = r , element k k k belongs to S S S with probability r / k r/k r / k and is then its r r r -th largest element. Hence
E W = ∑ r = 1 k b r a r , Pr [ D ] = ∑ r = 1 k r k g r ( 1 − a r ) . \mathbb{E}W=\sum_{r=1}^{k}b_ra_r,\qquad\Pr[D]=\sum_{r=1}^{k}\frac{r}{k}g_r(1-a_r). E W = r = 1 ∑ k b r a r , Pr [ D ] = r = 1 ∑ k k r g r ( 1 − a r ) .
Combining these two inequalities eliminates the algorithm:
2 k ε ≥ E W + k Pr [ D ] = ∑ r = 1 k [ b r a r + r g r ( 1 − a r ) ] ≥ ∑ r = 1 k min { b r , r g r } . (33) 2k\varepsilon\ge\mathbb{E}W+k\Pr[D]=\sum_{r=1}^{k}\left[b_ra_r+rg_r(1-a_r)\right]\ge\sum_{r=1}^{k}\min\{b_r,rg_r\}. \tag*{(33)} 2 k ε ≥ E W + k Pr [ D ] = r = 1 ∑ k [ b r a r + r g r ( 1 − a r ) ] ≥ r = 1 ∑ k min { b r , r g r } . (33)
Set m = ⌈ k / 2 ⌉ m=\lceil k/2\rceil m = ⌈ k /2 ⌉ and L = ⌊ k log k / 8 ⌋ L=\lfloor\sqrt{k\log k}/8\rfloor L = ⌊ k log k /8 ⌋ . For r = m + 1 , … , m + L r=m+1,\ldots,m+L r = m + 1 , … , m + L , symmetry gives b r ≥ 1 / 2 b_r\ge1/2 b r ≥ 1/2 . We claim that g r ≥ 1 / k g_r\ge1/k g r ≥ 1/ k throughout this interval. Indeed, g m g_m g m is a maximum point mass; since Var ( X ) ≤ k / 4 \operatorname{Var}(X)\le k/4 Var ( X ) ≤ k /4 , Chebyshev’s inequality gives g m ≥ 1 / ( 4 k ) g_m\ge1/(4\sqrt{k}) g m ≥ 1/ ( 4 k ) . For 1 ≤ s ≤ L ≤ m / 2 1\le s\le L\le m/2 1 ≤ s ≤ L ≤ m /2 , the binomial-coefficient ratio and log ( ( 1 − x ) / ( 1 + x ) ) ≥ − 3 x \log((1-x)/(1+x))\ge-3x log (( 1 − x ) / ( 1 + x )) ≥ − 3 x for 0 ≤ x ≤ 1 / 2 0\le x\le1/2 0 ≤ x ≤ 1/2 give
g m + s g m = ∏ j = 1 s ( k − m − j + 1 m + j ) 2 ≥ exp ( − 6 s ( s + 1 ) k ) ≥ k − 3 / 16 . \frac{g_{m+s}}{g_m}=\prod_{j=1}^{s}\left(\frac{k-m-j+1}{m+j}\right)^{2}\ge\exp\left(-\frac{6s(s+1)}{k}\right)\ge k^{-3/16}. g m g m + s = j = 1 ∏ s ( m + j k − m − j + 1 ) 2 ≥ exp ( − k 6 s ( s + 1 ) ) ≥ k − 3/16 .
Thus g m + s ≥ 1 4 k − 11 / 16 ≥ 1 / k g_{m+s}\ge\frac14k^{-11/16}\ge1/k g m + s ≥ 4 1 k − 11/16 ≥ 1/ k for k ≥ 128 k\ge128 k ≥ 128 . On these L L L indices, both b r b_r b r and r g r rg_r r g r are at least 1 / 2 1/2 1/2 . Equation (33) therefore yields
ε ≥ L 4 k ≥ 1 64 log k k . \varepsilon\ge\frac{L}{4k}\ge\frac{1}{64}\sqrt{\frac{\log k}{k}}. ε ≥ 4 k L ≥ 64 1 k log k .
Finally, an ordinal algorithm on n > 2 k n>2k n > 2 k elements can be simulated on 2 k 2k 2 k real elements by interleaving n − 2 k n-2k n − 2 k fictitious elements, all smaller than the real ones, at uniformly random positions and in a uniformly random relative order. Fictitious selections are discarded but still consume capacity. The combined order is uniform, and its k k k largest elements are real, so the simulation preserves the per-element guarantee. The bound for 2 k 2k 2 k elements therefore applies to every n ≥ 2 k n\ge2k n ≥ 2 k .
Remark (A midpoint certificate). Equation (33) is a dual certificate for a relaxation of the probability LP: retain only the symmetrized midpoint marginals a r a_r a r , the terminal guarantee for element k k k , and the sum of the terminal guarantees for all k k k optimum elements. It gives the finite bound
1 ρ ( U k , 2 k ) ≤ 1 − 1 2 k ∑ r = 1 k min { Pr [ X < r ] , r Pr [ X = r ] } , X ∼ Hypergeometric ( 2 k , k , k ) . \frac{1}{\rho(U_{k,2k})}\le1-\frac{1}{2k}\sum_{r=1}^{k}\min\{\Pr[X<r],r\Pr[X=r]\},\qquad X\sim\operatorname{Hypergeometric}(2k,k,k). ρ ( U k , 2 k ) 1 ≤ 1 − 2 k 1 r = 1 ∑ k min { Pr [ X < r ] , r Pr [ X = r ]} , X ∼ Hypergeometric ( 2 k , k , k ) .
No threshold or monotonicity assumption on the algorithm is used.
Linear matroids
We prove Theorem 7.2 by recursively constructing a family in P ( M ) \mathcal{P}(\mathcal{M}) P ( M ) , using a subspace invariant in place of the survivor distributions of § 5 . Throughout, M \mathcal{M} M is a linear matroid on n ≥ 2 n \ge2 n ≥ 2 elements, known in advance, and 1 ≤ s < n 1 \le s < n 1 ≤ s < n is a fixed cutoff. Recall that c n ( s ) c_n(s) c n ( s ) , defined in § 7.1 , is the success probability of the classical cutoff rule. Its maximum over s s s is the optimal success probability for the classical n n n -element secretary problem [54 , 26 ] , and hence equals 1 / ρ ( U 1 , n ) 1/\rho(U_{1,n}) 1/ ρ ( U 1 , n ) . The construction below is finite; no polynomial running-time bound is asserted.
The subspace invariant. By a theorem of Rado [60 ] , every linear matroid has a representation over a finite field. Fix such a representation ( u e ) e ∈ V (u_e)_{e \in V} ( u e ) e ∈ V in F d \mathbb{F}^d F d , for a finite field F \mathbb{F} F ; the algorithm can find one by exhaustive search before the arrivals. For A ⊆ V A \subseteq V A ⊆ V , let ⟨ A ⟩ \langle A\rangle ⟨ A ⟩ be the span of { u e : e ∈ A } \{u_e : e \in A\} { u e : e ∈ A } , and for a vector u u u let ⟨ u ⟩ \langle u\rangle ⟨ u ⟩ be its span. For a subspace U ≤ F d U \le\mathbb{F}^d U ≤ F d , the load of A A A at U U U is ℓ U ( A ) = dim ( ⟨ A ⟩ ∩ U ) \ell_U(A) = \dim(\langle A\rangle\cap U) ℓ U ( A ) = dim (⟨ A ⟩ ∩ U ) . A distribution μ \mu μ on independent sets is β \beta β -bounded if
E A ∼ μ [ ℓ U ( A ) ] ≤ β dim U for every subspace U ≤ F d . (34) \mathbb{E}_{A \sim\mu}[\ell_U(A)] \le\beta\dim U \qquad\text{for every subspace } U \le\mathbb{F}^d. \tag*{(34)} E A ∼ μ [ ℓ U ( A )] ≤ β dim U for every subspace U ≤ F d . (34)
There are finitely many subspaces, so this is a finite system of linear inequalities.
To motivate the invariant, recall the cutoff rule in rank one. After t ≥ s t \ge s t ≥ s arrivals it has accepted an element with probability exactly β t = 1 − s / t \beta_t = 1 - s/t β t = 1 − s / t , and it accepts a record arriving at time t > s t > s t > s with probability a t = s / ( t − 1 ) a_t = s/(t - 1) a t = s / ( t − 1 ) . These numbers satisfy
β t − 1 + a t = 1 , β t − 1 + a t t = β t ( t > s ) . (35) \beta_{t-1} + a_t = 1,\qquad\beta_{t-1} + \frac{a_t}{t} = \beta_t \qquad(t > s). \tag*{(35)} β t − 1 + a t = 1 , β t − 1 + t a t = β t ( t > s ) . (35)
For a nonloop e e e of a linear matroid, the constraint (34) at the line spanned by u e u_e u e states that u e ∈ ⟨ A ⟩ u_e \in\langle A\rangle u e ∈ ⟨ A ⟩ with probability at most β \beta β . With β = β t − 1 \beta= \beta_{t-1} β = β t − 1 , at least a t a_t a t of the probability mass can therefore accept e e e at time t t t . Lines bound the mass available for an acceptance but not its cost: bounding the increase of the load at U U U requires the constraint at U + ⟨ u e ⟩ U + \langle u_e\rangle U + ⟨ u e ⟩ . To maintain many constraints at once, the proof replaces families of subspaces by chains of intersections and sums, and intersections of subspaces spanned by elements need not be spanned by elements. The invariant is therefore imposed on every subspace.
Definition B.3 (The family for linear matroids). Fix 1 ≤ s < n 1 \le s < n 1 ≤ s < n . For ∣ O ∣ ≤ s |O| \le s ∣ O ∣ ≤ s , let μ O \mu_O μ O be the point mass at ∅ \varnothing ∅ and y O , ⋅ = 0 y_{O,\cdot} = 0 y O , ⋅ = 0 . For ∣ O ∣ = t > s |O| = t > s ∣ O ∣ = t > s , assume that μ O − e \mu_{O-e} μ O − e has been defined for every e ∈ O e \in O e ∈ O , and let y O , ⋅ y_{O,\cdot} y O , ⋅ be a canonical (for instance, lexicographically smallest) solution of the following finite linear system:
(a) 0 ≤ y O , e ( A ) ≤ μ O − e ( A ) 0 \le y_{O,e}(A) \le\mu_{O-e}(A) 0 ≤ y O , e ( A ) ≤ μ O − e ( A ) for every e ∈ O e \in O e ∈ O and independent A ⊆ O − e A \subseteq O-e A ⊆ O − e ;
(b) y O , e ( A ) = 0 y_{O,e}(A) = 0 y O , e ( A ) = 0 unless e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) and u e ∉ ⟨ A ⟩ u_e \notin\langle A\rangle u e ∈ / ⟨ A ⟩ ;
(c) ∑ A y O , e ( A ) = a t \sum_A y_{O,e}(A) = a_t ∑ A y O , e ( A ) = a t for every e ∈ Greedy ( O ) e \in\operatorname{Greedy}(O) e ∈ Greedy ( O ) ;
(d) the distribution μ O \mu_O μ O defined by (4) is β t \beta_t β t -bounded.
The family depends only on the ordered sets and the fixed representation. If the systems are feasible, normalization follows inductively from (4); together with (a) and (b), this places the family in P ( M ) \mathcal{P}(\mathcal{M}) P ( M ) . By Theorem 4.1, it is realized by (2). The only issue is feasibility of the system for t > s t > s t > s .
Proposition B.4. For every ordered set O O O with ∣ O ∣ > s |O| > s ∣ O ∣ > s , the system in Definition B.3 is feasible. For ∣ O ∣ ≥ s |O| \ge s ∣ O ∣ ≥ s , the distribution μ O \mu_O μ O is a β ∣ O ∣ \beta_{|O|} β ∣ O ∣ -bounded probability distribution on independent subsets of O O O .
We prove the proposition below. Accepting e e e at a state A A A raises the load at U U U exactly when u e ∈ ⟨ A ⟩ + U u_e \in\langle A\rangle+ U u e ∈ ⟨ A ⟩ + U . Along a chain of subspaces these sets of states are nested, so a single order of filling the acceptance mass preserves every constraint of the chain. Any weighted family of subspaces can be replaced by a chain without decreasing any load or changing the total dimension, and a minimax argument then gives one solution for all subspaces. The bound holds only on average over the identity of the last arrival. This is where the uniformly random order is used: the candidates Greedy(O O O ) form an independent set, which has at most dim U \dim U dim U vectors in any subspace U U U .
Admitting an element along a chain. The following two identities hold for subspaces Y Y Y , U U U and a vector u u u . Both follow from dim ( X ∩ Y ) = dim X + dim Y − dim ( X + Y ) \dim(X \cap Y) = \dim X + \dim Y - \dim(X + Y) dim ( X ∩ Y ) = dim X + dim Y − dim ( X + Y ) :
dim ( ( Y + ⟨ u ⟩ ) ∩ U ) − dim ( Y ∩ U ) = 1 { u ∈ Y + U } if u ∉ Y , dim ( Y ∩ ( U + ⟨ u ⟩ ) ) − dim ( Y ∩ U ) = 1 { u ∈ Y + U } if u ∉ U . (36) \begin{aligned}
\dim((Y + \langle u\rangle) \cap U) - \dim(Y \cap U) &= \mathbf{1}\{u \in Y + U\} && \text{if } u \notin Y,\\
\dim(Y \cap(U + \langle u\rangle)) - \dim(Y \cap U) &= \mathbf{1}\{u \in Y + U\} && \text{if } u \notin U. \tag*{(36)}
\end{aligned} dim (( Y + ⟨ u ⟩) ∩ U ) − dim ( Y ∩ U ) dim ( Y ∩ ( U + ⟨ u ⟩)) − dim ( Y ∩ U ) = 1 { u ∈ Y + U } = 1 { u ∈ Y + U } if u ∈ / Y , if u ∈ / U . (36)
By (36) , accepting e e e at a state A A A with u e ∉ ⟨ A ⟩ u_e \notin\langle A\rangle u e ∈ / ⟨ A ⟩ raises the load at U U U by one exactly when u e ∈ ⟨ A ⟩ + U u_e \in\langle A\rangle+ U u e ∈ ⟨ A ⟩ + U . We call such states expensive for U U U . By (37), if u e ∉ U u_e \notin U u e ∈ / U , the probability that u e ∈ ⟨ A ⟩ + U u_e \in\langle A\rangle+ U u e ∈ ⟨ A ⟩ + U , that is, of an expensive or infeasible state, is the difference between the expected loads at U + ⟨ u e ⟩ U + \langle u_e\rangle U + ⟨ u e ⟩ and at U U U .
An addition rule for e e e on a distribution μ \mu μ assigns masses 0 ≤ z ( A ) ≤ μ ( A ) 0 \le z(A) \le\mu(A) 0 ≤ z ( A ) ≤ μ ( A ) , with z ( A ) = 0 z(A) = 0 z ( A ) = 0 whenever u e ∈ ⟨ A ⟩ u_e \in\langle A\rangle u e ∈ ⟨ A ⟩ . It moves mass z ( A ) z(A) z ( A ) from A A A to A + e A + e A + e ; its total mass is ∑ A z ( A ) \sum_A z(A) ∑ A z ( A ) .
Lemma B.5 (Chain admission). Let μ \mu μ be β \beta β -bounded, let u e ≠ 0 u_e \ne0 u e = 0 , and let 0 ≤ a ≤ 1 − β 0 \le a \le1 - \beta 0 ≤ a ≤ 1 − β . For every chain of subspaces C 1 ⊆ ⋯ ⊆ C m C_1 \subseteq\cdots\subseteq C_m C 1 ⊆ ⋯ ⊆ C m , there is an addition rule of total mass a a a whose updated distribution μ ′ \mu' μ ′ satisfies E μ ′ [ ℓ U ] ≤ β dim U + a 1 { u e ∈ U } \mathbb{E}_{\mu'}[\ell_U] \le\beta\dim U + a\mathbf{1}\{u_e \in U\} E μ ′ [ ℓ U ] ≤ β dim U + a 1 { u e ∈ U } for every U U U in the chain.
Proof. For a chain member U U U , let D U = { A : u e ∈ ⟨ A ⟩ + U } D_U = \{A : u_e \in\langle A\rangle+ U\} D U = { A : u e ∈ ⟨ A ⟩ + U } be its set of expensive or infeasible states. These sets are nested along the chain. Give each feasible state the index i ( A ) = min { i : A ∈ D C i } i(A) = \min\{i : A \in D_{C_i}\} i ( A ) = min { i : A ∈ D C i } , or m + 1 m + 1 m + 1 if there is no such i i i . The feasible mass is 1 − Pr μ [ u e ∈ ⟨ A ⟩ ] ≥ 1 − β ≥ a 1 - \Pr_\mu[u_e \in\langle A\rangle] \ge1 - \beta\ge a 1 − Pr μ [ u e ∈ ⟨ A ⟩] ≥ 1 − β ≥ a , by (34) at ⟨ u e ⟩ \langle u_e\rangle ⟨ u e ⟩ . Place mass a a a on feasible states in decreasing order of index, splitting the last atom if necessary.
Fix a chain member U U U and let p U = μ ( D U ) p_U = \mu(D_U) p U = μ ( D U ) . Every state outside D U D_U D U is feasible and is filled before any state of D U D_U D U . Hence the mass placed in D U D_U D U is ( a − 1 + p U ) + (a - 1 + p_U)_+ ( a − 1 + p U ) + , and by (36) this is the increase of the expected load at U U U . If u e ∈ U u_e \in U u e ∈ U , then D U D_U D U contains every state and the increase is a a a . Otherwise, (37) gives E μ [ ℓ U ] + p U = E μ [ ℓ U + ⟨ u e ⟩ ] ≤ β ( dim U + 1 ) \mathbb{E}_{\mu}[\ell_U] + p_U = \mathbb{E}_{\mu}[\ell_{U+\langle u_e\rangle}] \le\beta(\dim U + 1) E μ [ ℓ U ] + p U = E μ [ ℓ U + ⟨ u e ⟩ ] ≤ β ( dim U + 1 ) . Using β + a ≤ 1 \beta+ a \le1 β + a ≤ 1 , the updated load is
max { E μ [ ℓ U ] , E μ [ ℓ U ] + p U + a − 1 } ≤ β dim U . \max\{\mathbb{E}_{\mu}[\ell_U],\ \mathbb{E}_{\mu}[\ell_U] + p_U + a - 1\} \le\beta\dim U. max { E μ [ ℓ U ] , E μ [ ℓ U ] + p U + a − 1 } ≤ β dim U . Lemma B.5 needs a chain; the next lemma reduces any weighted family of subspaces to one.
Lemma B.6 (Uncrossing). For nonnegative rational weights ( λ U ) U ≤ F d (\lambda_U)_{U \leq\mathbb{F}^d} ( λ U ) U ≤ F d , there are a chain C 1 ⊆ ⋯ ⊆ C m C_1 \subseteq\cdots\subseteq C_m C 1 ⊆ ⋯ ⊆ C m and nonnegative weights κ 1 , … , κ m \kappa_1,\ldots,\kappa_m κ 1 , … , κ m such that, for every subspace Y Y Y ,
∑ U λ U dim ( Y ∩ U ) ≤ ∑ i κ i dim ( Y ∩ C i ) , ∑ U λ U dim U = ∑ i κ i dim C i . \sum_U \lambda_U \dim(Y \cap U) \leq\sum_i \kappa_i \dim(Y \cap C_i), \qquad\sum_U \lambda_U \dim U = \sum_i \kappa_i \dim C_i. U ∑ λ U dim ( Y ∩ U ) ≤ i ∑ κ i dim ( Y ∩ C i ) , U ∑ λ U dim U = i ∑ κ i dim C i . Proof. Clear denominators and regard the weights as a multiset of subspaces; at the end, κ i \kappa_i κ i will be the multiplicity of C i C_i C i divided by the common denominator. While two members U , T U,T U , T are incomparable, replace them by U ∩ T U \cap T U ∩ T and U + T U + T U + T . This preserves the total dimension. It does not decrease the left side for any Y Y Y : the subspaces Y ∩ U Y \cap U Y ∩ U and Y ∩ T Y \cap T Y ∩ T have intersection Y ∩ U ∩ T Y \cap U \cap T Y ∩ U ∩ T and sum contained in Y ∩ ( U + T ) Y \cap(U + T) Y ∩ ( U + T ) . With d 0 = dim ( U ∩ T ) d_0 = \dim(U \cap T) d 0 = dim ( U ∩ T ) , the sum of squared dimensions increases by 2 ( dim U − d 0 ) ( dim T − d 0 ) > 0 2(\dim U - d_0)(\dim T - d_0) > 0 2 ( dim U − d 0 ) ( dim T − d 0 ) > 0 . This integer is bounded, so the process terminates, at a chain.
Lemma B.7 (Averaged extension). Let ∣ O ∣ = t ≥ 1 |O| = t \ge1 ∣ O ∣ = t ≥ 1 , let B ⊆ O B \subseteq O B ⊆ O be independent, and for each e ∈ O e \in O e ∈ O let μ e \mu_e μ e be a β \beta β -bounded distribution on independent subsets of O − e O-e O − e . If 0 ≤ a ≤ 1 − β 0 \le a \le1-\beta 0 ≤ a ≤ 1 − β , there are addition rules z e z_e z e for μ e \mu_e μ e , of total mass a a a for e ∈ B e \in B e ∈ B and zero for e ∉ B e \notin B e ∈ / B , such that the average over e ∈ O e \in O e ∈ O of the updated distributions is ( β + a / t ) (\beta+a/t) ( β + a / t ) -bounded.
Proof. Let P P P be the set of families z = ( z e ) e ∈ O z=(z_e)_{e\in O} z = ( z e ) e ∈ O of addition rules with the prescribed total masses. It is a nonempty polytope: the elements of the independent set B B B are nonloops, so by the availability bound in the proof of Lemma B.5 , each μ e \mu_e μ e with e ∈ B e \in B e ∈ B has feasible mass at least 1 − β ≥ a 1-\beta\ge a 1 − β ≥ a . For z ∈ P z \in P z ∈ P and a subspace U U U , let g U ( z ) g_U(z) g U ( z ) be the expected load at U U U of the averaged updated distribution; it is affine in z z z . We need z ∈ P z \in P z ∈ P with g U ( z ) ≤ ( β + a / t ) dim U g_U(z) \le(\beta+a/t)\dim U g U ( z ) ≤ ( β + a / t ) dim U for all U U U .
Fix nonnegative rational weights λ \lambda λ , and obtain a chain from Lemma B.6 . Apply Lemma B.5 to this chain in every row e ∈ B e \in B e ∈ B , and add nothing in the other rows. For each chain member C i C_i C i , averaging the row bounds gives
g C i ( z ) ≤ β dim C i + a t ∣ { e ∈ B : u e ∈ C i } ∣ ≤ ( β + a t ) dim C i , g_{C_i}(z) \le\beta\dim C_i+\frac{a}{t}|\{e\in B:u_e\in C_i\}|\le\left(\beta+\frac{a}{t}\right)\dim C_i, g C i ( z ) ≤ β dim C i + t a ∣ { e ∈ B : u e ∈ C i } ∣ ≤ ( β + t a ) dim C i ,
since the independent set B B B has at most dim C i \dim C_i dim C i vectors in C i C_i C i . Taking expectations in the pointwise domination of Lemma B.6 gives ∑ U λ U g U ( z ) ≤ ( β + a / t ) ∑ U λ U dim U \sum_U\lambda_Ug_U(z)\le(\beta+a/t)\sum_U\lambda_U\dim U ∑ U λ U g U ( z ) ≤ ( β + a / t ) ∑ U λ U dim U .
Thus min z ∈ P ∑ U λ U ( g U ( z ) − ( β + a / t ) dim U ) ≤ 0 \min_{z\in P}\sum_U\lambda_U\left(g_U(z)-(\beta+a/t)\dim U\right)\le0 min z ∈ P ∑ U λ U ( g U ( z ) − ( β + a / t ) dim U ) ≤ 0 for every rational nonnegative λ \lambda λ , and hence for every λ \lambda λ in the probability simplex: the minimum over the compact set P P P of a jointly continuous function is continuous in λ \lambda λ . The function is linear in λ \lambda λ and affine in z z z , on a product of two polytopes. By the minimax theorem [67 ] , some z ∈ P z\in P z ∈ P makes the maximum over the simplex nonpositive, so every constraint holds at that z z z . □
The lemma controls only the average of the updated distributions, not each row separately; the independence of B B B bounds the average increase.
Proof of Proposition B.4 . We show by induction on t = ∣ O ∣ ≥ s t=|O|\ge s t = ∣ O ∣ ≥ s that the system in Definition B.3 is feasible when t > s t>s t > s and that μ O \mu_O μ O is a β t \beta_t β t -bounded probability distribution on independent sets. For t = s t=s t = s , the point mass at ∅ \varnothing ∅ is 0 0 0 -bounded and β s = 0 \beta_s=0 β s = 0 . For t > s t>s t > s , apply Lemma B.7 with B = Greedy ( O ) B=\operatorname{Greedy}(O) B = Greedy ( O ) , μ e = μ O − e \mu_e=\mu_{O-e} μ e = μ O − e , β = β t − 1 \beta=\beta_{t-1} β = β t − 1 , and a = a t = 1 − β t − 1 a=a_t=1-\beta_{t-1} a = a t = 1 − β t − 1 . Elements of the independent set B B B are nonloops, so u e ≠ 0 u_e\ne0 u e = 0 . The resulting rules satisfy (a)–(c), and (d) holds because β t − 1 + a t / t = β t \beta_{t-1}+a_t/t=\beta_t β t − 1 + a t / t = β t by (35) . The distribution defined by (4) is the averaged updated distribution, a probability distribution on independent sets. □
Proof of Theorem 7.2 . By Proposition B.4 , the family in Definition B.3 is well defined and belongs to P ( M ) \mathcal{P}(\mathcal{M}) P ( M ) . Apply Theorem 4.1.
Fix e ∈ Greedy ( V ) e\in\operatorname{Greedy}(V) e ∈ Greedy ( V ) . By Lemma 2.1 (i), e ∈ Greedy ( O ) e\in\operatorname{Greedy}(O) e ∈ Greedy ( O ) for every observed ordered set O O O containing e e e . Conditional on e e e arriving at position t t t and on the observed order O O O , its acceptance probability is therefore ∑ A y O , e ( A ) = a t \sum_A y_{O,e}(A)=a_t ∑ A y O , e ( A ) = a t when t > s t>s t > s , and zero when t ≤ s t\le s t ≤ s . Since e e e arrives at each position with probability 1 / n 1/n 1/ n ,
Pr [ e ∈ ALG ] = 1 n ∑ t = s + 1 n s t − 1 = c n ( s ) . \Pr[e\in\operatorname{ALG}]=\frac{1}{n}\sum_{t=s+1}^{n}\frac{s}{t-1}=c_n(s). Pr [ e ∈ ALG ] = n 1 t = s + 1 ∑ n t − 1 s = c n ( s ) .
Choosing s s s optimally gives ρ ( M ) ≤ ρ ( U 1 , n ) \rho(\mathcal{M})\le\rho(U_{1,n}) ρ ( M ) ≤ ρ ( U 1 , n ) . It remains to show max s c n ( s ) > 1 / e \max_s c_n(s)>1/e max s c n ( s ) > 1/ e . For n = 2 n=2 n = 2 , c 2 ( 1 ) = 1 / 2 c_2(1)=1/2 c 2 ( 1 ) = 1/2 . For n ≥ 3 n\ge3 n ≥ 3 , let ζ = n / e \zeta=n/e ζ = n / e , j = ⌊ ζ ⌋ j=\lfloor\zeta\rfloor j = ⌊ ζ ⌋ , and ϑ = ζ − j \vartheta=\zeta-j ϑ = ζ − j ; then 1 ≤ j < j + 1 ≤ n − 1 1\le j<j+1\le n-1 1 ≤ j < j + 1 ≤ n − 1 . Using ln x ≤ x − 1 \ln x \le x - 1 ln x ≤ x − 1 , first for x = ( j + 1 ) / ζ x = (j + 1)/\zeta x = ( j + 1 ) / ζ and then for x = ( i + 1 ) / i x = (i + 1)/i x = ( i + 1 ) / i , with strict inequality in the second case,
1 e = ζ n ln n ζ < j + 1 − ζ n + ζ n ∑ i = j + 1 n − 1 1 i = ( 1 − ϑ ) c n ( j ) + ϑ c n ( j + 1 ) . \frac{1}{\mathrm{e}} = \frac{\zeta}{n}\ln\frac{n}{\zeta} < \frac{j + 1 - \zeta}{n} + \frac{\zeta}{n}\sum_{i=j+1}^{n-1}\frac{1}{i} = (1-\vartheta)c_n(j) + \vartheta c_n(j+1). e 1 = n ζ ln ζ n < n j + 1 − ζ + n ζ i = j + 1 ∑ n − 1 i 1 = ( 1 − ϑ ) c n ( j ) + ϑ c n ( j + 1 ) .
Hence one of the two cutoffs achieves more than 1 / e 1/\mathrm{e} 1/ e .
In a loopless matroid of rank one, the system in Definition B.3 has a unique solution and the algorithm is exactly the classical cutoff rule. The subspace invariant replaces the single number β t \beta_t β t by a bound on every subspace.
Open problem. Does every matroid M \mathcal{M} M on n ≥ 2 n \ge2 n ≥ 2 elements with a nonloop, known in advance, satisfy ρ ( M ) ≤ ρ ( U 1 , n ) \rho(\mathcal{M}) \le\rho(U_{1,n}) ρ ( M ) ≤ ρ ( U 1 , n ) ? Equivalently, is there always an ordinal algorithm that selects every element of Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) with probability at least max s c n ( s ) \max_s c_n(s) max s c n ( s ) ? Theorem 7.2 answers this affirmatively for linear matroids. The computations of Appendix § 11 suggest the weaker comparison for the ordinal expected-value objective.
Computational Insights
This appendix gives the numerical findings and computational reductions summarized in § 7.1 . Write ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) for the optimal expected-value competitive ratio among ordinal algorithms on the known matroid M \mathcal{M} M . By Corollary 4.3 , its reciprocal is the value of the program with prefix constraints. The ratio ρ ( M ) \rho(\mathcal{M}) ρ ( M ) in § 4.2 instead requires a guarantee for every element of Greedy ( V ) \operatorname{Greedy}(V) Greedy ( V ) . The computations reported here concern ρ o r d \rho_{\mathrm{ord}} ρ ord .
Numerical findings and coverage
Using the catalogue of matroids on at most nine elements of Mayhew and Royle [56 ] , we solved the program with Gurobi in floating-point arithmetic. The coverage is summarized below.13
Table 1 (PDF p. 49).
The 68 unsolved eight-element matroids all have rank four, and all but one have no nontrivial automorphism. For these 67 matroids, the symmetry reduction described below does not shrink the programs. Every matroid on at most seven elements is representable over some field [59 ] ; on eight elements, there are 44 matroids not representable over any field [56 ] .
Every computed ratio was below e \mathrm{e} e . More strongly, every tested instance satisfied
ρ o r d ( M ) ≤ ρ o r d ( U 1 , n ) , \rho_{\mathrm{ord}}(\mathcal{M}) \le\rho_{\mathrm{ord}}(U_{1,n}), ρ ord ( M ) ≤ ρ ord ( U 1 , n ) ,
with equality, up to numerical precision, only for U 1 , n U_{1,n} U 1 , n itself. For n = 8 n = 8 n = 8 , the computed values of 1 / ρ o r d ( M ) 1/\rho_{\mathrm{ord}}(\mathcal{M}) 1/ ρ ord ( M ) exceed 1 / ρ o r d ( U 1 , 8 ) 1/\rho_{\mathrm{ord}}(U_{1,8}) 1/ ρ ord ( U 1 , 8 ) by at least 0.004 except for U 1 , 8 U_{1,8} U 1 , 8 , far above the solver tolerance. These are floating-point observations, not exact certificates. For n ≤ 7 n \le7 n ≤ 7 , representability and Theorem 7.2 also prove ρ o r d ( M ) ≤ ρ o r d ( U 1 , n ) < e \rho_{\mathrm{ord}}(\mathcal{M}) \le\rho_{\mathrm{ord}}(U_{1,n}) < e ρ ord ( M ) ≤ ρ ord ( U 1 , n ) < e for every positive-rank matroid. The solved eight-element instances include 43 nonrepresentable matroids, beyond the scope of that theorem.
These computations predate the proofs in this paper. At the time, they were evidence for the strong conjecture beyond the classes for which it was known, and they guided the search for the single-sample prophet inequality of § 3 and the construction of Appendix § 10 .§ 2 .
LP representation and reductions
Acceptance marginals. For a full value order ω \omega ω and an element e e e , define
p ω , e ( y ) = ∑ S ⊆ V e ∈ S 1 n ( n − 1 ∣ S ∣ − 1 ) ∑ A ⊆ S − e y ∣ S ∣ , e ( A ) . (37) p_{\omega,e}(y) = \sum_{\substack{S \subseteq V \\ e \in S}} \frac{1}{n\binom{n-1}{|S|-1}} \sum_{A \subseteq S-e} y_{|S|,e}(A). \tag*{(37)} p ω , e ( y ) = S ⊆ V e ∈ S ∑ n ( ∣ S ∣ − 1 n − 1 ) 1 A ⊆ S − e ∑ y ∣ S ∣ , e ( A ) . (37)
The element e e e arrives at each position with probability 1 / n 1/n 1/ n ; conditional on position ∣ S ∣ |S| ∣ S ∣ , its observed set is uniform among the ( n − 1 ∣ S ∣ − 1 ) \binom{n-1}{|S|-1} ( ∣ S ∣ − 1 n − 1 ) sets of that size containing e e e . Thus (37) is its inclusion probability, and equals ∑ A ∋ e μ ω ( A ) \sum_{A \ni e}\mu_\omega(A) ∑ A ∋ e μ ω ( A ) for a feasible family. The ordinal objective can therefore be imposed through
∑ e ∈ H p ω , e ( y ) ≥ γ rank ( H ) \sum_{e \in H} p_{\omega,e}(y) \ge\gamma\operatorname{rank}(H) e ∈ H ∑ p ω , e ( y ) ≥ γ rank ( H )
for every full order ω \omega ω and prefix H H H .
This expression uses the total accepting mass for each element, which is preserved by the state aggregation below.
Computational reductions. We use the unconditional state and accepting-transition probabilities
μ O ( A ) ( n ∣ O ∣ ) and y O , e ( A ) n ( n − 1 ∣ O ∣ − 1 ) , \frac{\mu_O(A)}{\binom{n}{|O|}}
\qquad\text{and}\qquad
\frac{y_{O,e}(A)}{n\binom{n-1}{|O|-1}}, ( ∣ O ∣ n ) μ O ( A ) and n ( ∣ O ∣ − 1 n − 1 ) y O , e ( A ) ,
respectively. This rescaling preserves the optimum. Three further reductions make the program tractable for small matroids. First, only prefixes ending with an element of Greedy ( ω ) \operatorname{Greedy}(\omega) Greedy ( ω ) need constraints: between successive such prefixes, the rank is unchanged and the left side only increases. Second, averaging a feasible family over the automorphism group of M \mathcal{M} M preserves its objective, so an optimal family can be restricted to orbit representatives.
Third, call independent sets A , A ′ ⊆ O A,A' \subseteq O A , A ′ ⊆ O equivalent at O O O if A ∪ J A \cup J A ∪ J and A ′ ∪ J A' \cup J A ′ ∪ J have the same independence status for every J ⊆ V ∖ O J \subseteq V \setminus O J ⊆ V ∖ O . They admit the same feasible extensions. A class Q Q Q at O − e O-e O − e lies in one class at O O O after rejecting e e e . Moreover, either every A ∈ Q A \in Q A ∈ Q can accept e e e or none can; in the former case all sets A + e A+e A + e , for A ∈ Q A \in Q A ∈ Q , lie in one class at O O O . Both facts follow directly from the definition, using extension sets J J J and J + e J+e J + e , respectively.
The aggregated program has a probability variable for each class at each ordered set and an accepting-mass variable for each predecessor class. It imposes the initial point mass at ∅ \varnothing ∅ , class capacities, independent support, and (4) summed over each destination class. In (37) , replace the sum over states by the sum over predecessor classes. Summing a feasible family over classes gives an aggregated feasible solution with exactly the same accepting totals and objective. Conversely, at a state in a predecessor class Q Q Q , accept with probability y O , e ( Q ) / μ O − e ( Q ) y_{O,e}(Q)/\mu_{O-e}(Q) y O , e ( Q ) / μ O − e ( Q ) , with 0 / 0 = 0 0/0=0 0/0 = 0 . The class determines both possible destination classes, so induction in (4) shows that this algorithm realizes the prescribed class distributions and accepting masses. Formula (37) then gives the same per-element marginals and hence the same objective. The aggregation preserves the optimum; it need not preserve each individual terminal set probability.
The truncation hypothesis
Before the general result was known, the computations also suggested structural statements that would imply the strong conjecture. We describe one of them. For 1 ≤ k ≤ rank ( M ) 1 \le k \le\operatorname{rank}(\mathcal{M}) 1 ≤ k ≤ rank ( M ) , the truncation M ( k ) \mathcal{M}^{(k)} M ( k ) has the independent sets of M \mathcal{M} M of size at most k k k . The truncation M ( 1 ) \mathcal{M}^{(1)} M ( 1 ) is the classical secretary problem on the nonloops of M \mathcal{M} M , so ρ o r d ( M ( 1 ) ) ≤ e \rho_{\mathrm{ord}}(\mathcal{M}^{(1)}) \le\mathrm{e} ρ ord ( M ( 1 ) ) ≤ e . We say that M \mathcal{M} M satisfies truncation monotonicity if ρ o r d ( M ( k ) ) \rho_{\mathrm{ord}}(\mathcal{M}^{(k)}) ρ ord ( M ( k ) ) is nonincreasing in k k k ; then ρ o r d ( M ) ≤ ρ o r d ( M ( 1 ) ) ≤ e \rho_{\mathrm{ord}}(\mathcal{M}) \le\rho_{\mathrm{ord}}(\mathcal{M}^{(1)}) \le\mathrm{e} ρ ord ( M ) ≤ ρ ord ( M ( 1 ) ) ≤ e , which would have implied the strong conjecture. The computed values satisfy truncation monotonicity, up to solver tolerance. Appendix § 12 shows that it holds, strictly, for uniform matroids, but fails for the graphic matroid of a large complete bipartite graph K 2 , N K_{2,N} K 2 , N . The failure of this route is part of why the construction of Appendix § 10 .§ 2 controls the span of the accepted set directly instead of inducting on the rank.
Truncation monotonicity would also imply the comparison with rank one observed above. Indeed, M ( 1 ) \mathcal{M}^{(1)} M ( 1 ) is the classical problem on the n ′ ≤ n n' \le n n ′ ≤ n nonloops of M \mathcal{M} M , and inserting n − n ′ n-n' n − n ′ fictitious elements, as in the proof of Proposition D.7, shows that ρ o r d ( U 1 , n ′ ) ≤ ρ o r d ( U 1 , n ) \rho_{\mathrm{ord}(U_{1,n'})} \le\rho_{\mathrm{ord}}(U_{1,n}) ρ ord ( U 1 , n ′ ) ≤ ρ ord ( U 1 , n ) . The counterexample does not contradict this weaker statement: there, ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) is only shown to exceed 100 / 53 100/53 100/53 , while ρ o r d ( U 1 , n ) \rho_{\mathrm{ord}}(U_{1,n}) ρ ord ( U 1 , n ) is close to e \mathrm{e} e . Theorem 7.2 proves it for every linear matroid.
Ordinal Ratios under Truncation
This appendix proves the two statements about truncation mentioned in Appendix § 11 . Recall that ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) is the optimal ordinal competitive ratio of a known matroid M \mathcal{M} M , and that M ( k ) \mathcal{M}^{(k)} M ( k ) is its truncation to rank k k k . Truncation monotonicity asserts that ρ o r d ( M ( k ) ) ≤ ρ o r d ( M ( k − 1 ) ) \rho_{\mathrm{ord}}(\mathcal{M}^{(k)}) \le\rho_{\mathrm{ord}}(\mathcal{M}^{(k-1)}) ρ ord ( M ( k ) ) ≤ ρ ord ( M ( k − 1 ) ) for 2 ≤ k ≤ rank ( M ) 2 \le k \le\operatorname{rank}(\mathcal{M}) 2 ≤ k ≤ rank ( M ) . Theorem D.5 proves it, with strict inequality, for uniform matroids. Theorem D.6 refutes it for a graphic matroid; there, the bound on M \mathcal{M} M holds even for algorithms that observe numerical values.
For 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n , let r ( n , k ) r(n,k) r ( n , k ) be the largest expected fraction of the k k k largest elements that a possibly randomized algorithm can select, with capacity k k k , when n n n elements arrive in uniformly random order and the algorithm observes only the relative order of the arrived elements. The maximum exists, and is attained by a deterministic rule, because the problem is a finite Markov decision problem.
Let R t ∈ { 1 , … , t } R_t \in\{1,\ldots,t\} R t ∈ { 1 , … , t } be the relative rank of the t t t -th arrival among the first t t t , with 1 1 1 the largest. The relative ranks are independent, R t R_t R t is uniform on { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } , and conditional on R 1 , … , R t R_1,\ldots,R_t R 1 , … , R t the set of global ranks of the first t t t arrivals is a uniform t t t -subset of { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } . The t t t -th arrival is the R t R_t R t -th largest of this subset. Hence, conditional on the entire ordinal history, it is among the k k k largest elements with probability
p k ( t , R t ) , p k ( t , s ) = Pr [ Ξ k , t ≥ s ] , Ξ k , t ∼ Hypergeometric ( n , k , t ) , (38) p_k(t,R_t), \qquad p_k(t,s)=\Pr[\Xi_{k,t}\ge s], \qquad\Xi_{k,t}\sim\operatorname{Hypergeometric}(n,k,t), \tag*{(38)} p k ( t , R t ) , p k ( t , s ) = Pr [ Ξ k , t ≥ s ] , Ξ k , t ∼ Hypergeometric ( n , k , t ) , (38)
the number of successes among t t t draws without replacement from n n n items, k k k of which are successes.
Lemma D.1. For 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n , ρ o r d ( U k , n ) = 1 / r ( n , k ) \rho_{\mathrm{ord}}(U_{k,n})=1/r(n,k) ρ ord ( U k , n ) = 1/ r ( n , k ) .
Proof. Let an ordinal algorithm be c c c -competitive on U k , n U_{k,n} U k , n . Run it on a uniformly random relabeling of the elements; every permutation of the ground set is an automorphism of U k , n U_{k,n} U k , n , so this preserves feasibility. For each value order, its behavior is an average of its behavior on other value orders, so it remains c c c -competitive, and the sequence of labels it observes is now independent of ( R 1 , … , R n ) (R_1,\ldots,R_n) ( R 1 , … , R n ) . The labels can therefore be generated by internal randomness, so the relabeled algorithm observes only relative order, as in the definition of r ( n , k ) r(n,k) r ( n , k ) . Corollary 4.3 , applied to the prefix of the k k k largest elements, shows that it selects at least k / c k/c k / c of them in expectation. Hence r ( n , k ) ≥ 1 / c r(n,k) \ge1/c r ( n , k ) ≥ 1/ c .
Conversely, since the relative ranks are independent, the optimal continuation value depends only on the time and the number of free slots. By backward induction, there is an optimal deterministic rule for r ( n , k ) r(n,k) r ( n , k ) that accepts the t t t -th arrival, when b ≥ 1 b \ge1 b ≥ 1 slots remain, exactly when p k ( t , R t ) p_k(t,R_t) p k ( t , R t ) is at least a threshold depending only on t t t and b b b . Since p k ( t , s ) p_k(t,s) p k ( t , s ) is nonincreasing in s s s , a smaller relative rank is accepted whenever a larger one is. We claim that under this rule, the probability that the element of global rank j j j is selected is nonincreasing in j j j . Pair each arrival order with the order exchanging the positions of the elements of ranks j j j and j + 1 j+1 j + 1 . Every other element compares identically with these two elements. Hence the two runs see the same relative ranks, except at the later of the two positions, where the relative rank is smaller by one when the later element has rank j j j . The decisions coincide before that position, and at that position the run with the smaller relative rank accepts whenever the other does. Summing over the pair shows that rank j j j is selected at least as often as rank j + 1 j+1 j + 1 , and averaging over all pairs proves the claim.
Consequently, for a prefix H H H of size m ≤ k m \le k m ≤ k , the average selection probability over H H H is at least that over the k k k largest elements, which is r ( n , k ) r(n,k) r ( n , k ) . For m > k m > k m > k , the expected number selected from H H H is at least k r ( n , k ) kr(n,k) k r ( n , k ) . In both cases it is at least r ( n , k ) rank ( H ) r(n,k)\operatorname{rank}(H) r ( n , k ) rank ( H ) , and Corollary 4.3 gives ρ o r d ( U k , n ) ≤ 1 / r ( n , k ) \rho_{\rm ord}(U_{k,n}) \le1/r(n,k) ρ ord ( U k , n ) ≤ 1/ r ( n , k ) . □ \square □
We reformulate r ( n , k ) r(n,k) r ( n , k ) as an optimal stopping problem. For independent nonnegative random variables Z = ( Z 1 , … , Z n ) Z=(Z_1,\ldots,Z_n) Z = ( Z 1 , … , Z n ) with finite support, let Φ b ( Z ) \Phi_b(Z) Φ b ( Z ) be the largest expected total of at most b b b selections made online, where Z t Z_t Z t is observed at time t t t . Let Z t k = p k ( t , R t ) Z_t^k=p_k(t,R_t) Z t k = p k ( t , R t ) . Then
k r ( n , k ) = Φ k ( Z k ) . (39) k r(n,k)=\Phi_k(Z^k). \tag*{(39)} k r ( n , k ) = Φ k ( Z k ) . (39)
Indeed, by (38) , the expected number of the k k k largest elements selected by a rank-observing algorithm is the expected sum of Z t k Z_t^k Z t k over the selected times. Every rule based on Z k Z^k Z k is rank-observing. Conversely, by independence, the Bellman decision of a rank-observing rule at time t t t depends on R t R_t R t only through Z t k Z_t^k Z t k , so observing the relative ranks does not increase the optimal value.
Lemma D.2 (Comparison). Let Z , Z ′ Z,Z' Z , Z ′ have independent coordinates with E [ ( Z t − c ) + ] ≤ E [ ( Z t ′ − c ) + ] \mathbb{E}[(Z_t-c)_+] \le\mathbb{E}[(Z'_t-c)_+] E [( Z t − c ) + ] ≤ E [( Z t ′ − c ) + ] for every t t t and every c ≥ 0 c \ge0 c ≥ 0 . Then Φ b ( Z ) ≤ Φ b ( Z ′ ) \Phi_b(Z) \le\Phi_b(Z') Φ b ( Z ) ≤ Φ b ( Z ′ ) for every b b b .
Proof. Let v t ( b ) v_t(b) v t ( b ) be the optimal value from time t t t onward with b b b slots, with v n + 1 = 0 v_{n+1}=0 v n + 1 = 0 and v t ( 0 ) = 0 v_t(0)=0 v t ( 0 ) = 0 . Then v t ( b ) ≥ v t ( b − 1 ) v_t(b) \ge v_t(b-1) v t ( b ) ≥ v t ( b − 1 ) and
v t ( b ) = v t + 1 ( b ) + E [ ( Z t − [ v t + 1 ( b ) − v t + 1 ( b − 1 ) ] ) + ] . v_t(b)=v_{t+1}(b)+\mathbb{E}\left[(Z_t-\left[v_{t+1}(b)-v_{t+1}(b-1)\right])_+\right]. v t ( b ) = v t + 1 ( b ) + E [ ( Z t − [ v t + 1 ( b ) − v t + 1 ( b − 1 ) ] ) + ] .
The map ( x , x ′ ) ↦ x + E [ ( Z t − ( x − x ′ ) ) + ] (x,x')\mapsto x+\mathbb{E}[(Z_t-(x-x'))_+] ( x , x ′ ) ↦ x + E [( Z t − ( x − x ′ ) ) + ] is nondecreasing in both arguments, and the threshold x − x ′ x-x' x − x ′ is nonnegative. Backward induction on t t t gives v t ( b ) ≤ v t ′ ( b ) v_t(b)\le v'_t(b) v t ( b ) ≤ v t ′ ( b ) for all b b b . □ \square □
Lemma D.3 (Thinning and capacity). Let 1 ≤ m < K 1\le m<K 1 ≤ m < K , and let ξ 1 , … , ξ n \xi_1,\ldots,\xi_n ξ 1 , … , ξ n be independent Bernoulli ( m / K ) \operatorname{Bernoulli}(m/K) Bernoulli ( m / K ) variables, independent of Z Z Z . Then
K m Φ m ( ( ξ t Z t ) t ) ≤ ( 1 − δ ) Φ K ( Z ) + δ Φ m ( Z ) , δ = K 1 − n . \frac{K}{m}\Phi_m((\xi_t Z_t)_t)\le(1-\delta)\Phi_K(Z)+\delta\Phi_m(Z),\qquad\delta=K^{1-n}. m K Φ m (( ξ t Z t ) t ) ≤ ( 1 − δ ) Φ K ( Z ) + δ Φ m ( Z ) , δ = K 1 − n .
Proof. Give each time an independent uniform color C t ∈ { 1 , … , K } C_t\in\{1,\ldots,K\} C t ∈ { 1 , … , K } . For each set J J J of m m m colors, the variables Z t 1 { C t ∈ J } Z_t\mathbf{1}\{C_t\in J\} Z t 1 { C t ∈ J } form an ( m / K ) (m/K) ( m / K ) -thinning of Z Z Z . Run on each of them the same optimal deterministic m m m -selection rule, chosen never to select a zero reward, and let I t J I_t^J I t J indicate its selections. Let a t = ( K − 1 m − 1 ) − 1 ∑ J I t J a_t = \binom{K-1}{m-1}^{-1} \sum_J I_t^J a t = ( m − 1 K − 1 ) − 1 ∑ J I t J . Only the ( K − 1 m − 1 ) \binom{K-1}{m-1} ( m − 1 K − 1 ) sets containing C t C_t C t can select at time t t t , so 0 ≤ a t ≤ 1 0 \le a_t \le1 0 ≤ a t ≤ 1 . Each copy selects at most m m m times, so ∑ t a t ≤ K \sum_t a_t \le K ∑ t a t ≤ K . The expected value E [ ∑ t a t Z t ] \mathbb{E}[\sum_t a_tZ_t] E [ ∑ t a t Z t ] equals ( K m ) ( K − 1 m − 1 ) − 1 Φ m ( ( ξ t Z t ) t ) = K m Φ m ( ( ξ t Z t ) t ) \binom{K}{m}\binom{K-1}{m-1}^{-1}\Phi_m((\xi_tZ_t)_t) = \frac{K}{m}\Phi_m((\xi_tZ_t)_t) ( m K ) ( m − 1 K − 1 ) − 1 Φ m (( ξ t Z t ) t ) = m K Φ m (( ξ t Z t ) t ) .
Round these fractional decisions online with one independent uniform U ∈ [ 0 , 1 ) U \in[0,1) U ∈ [ 0 , 1 ) . With Q t = ∑ i ≤ t a i Q_t = \sum_{i\le t} a_i Q t = ∑ i ≤ t a i , select at time t t t when ⌊ Q t + U ⌋ > ⌊ Q t − 1 + U ⌋ \lfloor Q_t+U\rfloor> \lfloor Q_{t-1}+U\rfloor ⌊ Q t + U ⌋ > ⌊ Q t − 1 + U ⌋ . This selects at most K K K times, at time t t t with probability a t a_t a t conditional on Z Z Z and the colors. For every fixed coloring, it is an online rule for Z Z Z . With probability δ \delta δ , all colors coincide; then all active copies see Z Z Z itself and make identical decisions, so at most m m m selections are made. Bounding the value by Φ m ( Z ) \Phi_m(Z) Φ m ( Z ) on this event and by Φ K ( Z ) \Phi_K(Z) Φ K ( Z ) otherwise proves the lemma. □
Lemma D.4 (Adjacent posteriors). For 2 ≤ k ≤ n 2 \le k \le n 2 ≤ k ≤ n , every t t t , and every convex φ \varphi φ with φ ( 0 ) = 0 \varphi(0)=0 φ ( 0 ) = 0 ,
E [ φ ( Z t k − 1 ) ] ≤ k − 1 k E [ φ ( Z t k ) ] . \mathbb{E}[\varphi(Z_t^{k-1})] \le\frac{k-1}{k}\mathbb{E}[\varphi(Z_t^k)]. E [ φ ( Z t k − 1 )] ≤ k k − 1 E [ φ ( Z t k )] .
Proof. Couple the two hypergeometric counts by turning one uniformly random success of the population into a failure. Given that the sample contains s s s successes, the removed success was sampled with probability s / k s/k s / k . Hence Pr [ Ξ k − 1 , t ≥ s ] = Pr [ Ξ k , t ≥ s + 1 ] + ( 1 − s / k ) Pr [ Ξ k , t = s ] \Pr[\Xi_{k-1,t}\ge s] = \Pr[\Xi_{k,t}\ge s+1] + (1-s/k)\Pr[\Xi_{k,t}=s] Pr [ Ξ k − 1 , t ≥ s ] = Pr [ Ξ k , t ≥ s + 1 ] + ( 1 − s / k ) Pr [ Ξ k , t = s ] , that is,
p k − 1 ( t , s ) = ( 1 − s k ) p k ( t , s ) + s k p k ( t , s + 1 ) ( 1 ≤ s ≤ k − 1 ) , p_{k-1}(t,s)=\left(1-\frac{s}{k}\right)p_k(t,s)+\frac{s}{k}p_k(t,s+1) \qquad(1\le s\le k-1), p k − 1 ( t , s ) = ( 1 − k s ) p k ( t , s ) + k s p k ( t , s + 1 ) ( 1 ≤ s ≤ k − 1 ) ,
while p k − 1 ( t , s ) = 0 p_{k-1}(t,s)=0 p k − 1 ( t , s ) = 0 for s ≥ k s\ge k s ≥ k . Jensen’s inequality and summation over s s s give
∑ s = 1 k − 1 φ ( p k − 1 ( t , s ) ) ≤ ∑ s = 1 k − 1 [ ( 1 − s k ) φ ( p k ( t , s ) ) + s k φ ( p k ( t , s + 1 ) ) ] = k − 1 k ∑ s = 1 k φ ( p k ( t , s ) ) . \sum_{s=1}^{k-1}\varphi(p_{k-1}(t,s))\le\sum_{s=1}^{k-1}\left[\left(1-\frac{s}{k}\right)\varphi(p_k(t,s))+\frac{s}{k}\varphi(p_k(t,s+1))\right]=\frac{k-1}{k}\sum_{s=1}^{k}\varphi(p_k(t,s)). s = 1 ∑ k − 1 φ ( p k − 1 ( t , s )) ≤ s = 1 ∑ k − 1 [ ( 1 − k s ) φ ( p k ( t , s )) + k s φ ( p k ( t , s + 1 )) ] = k k − 1 s = 1 ∑ k φ ( p k ( t , s )) .
Since R t R_t R t is uniform on { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } , and p k ( t , s ) = 0 p_k(t,s)=0 p k ( t , s ) = 0 whenever s > min { t , k } s>\min\{t,k\} s > min { t , k } , we have t E [ φ ( Z t k ) ] = ∑ s = 1 k φ ( p k ( t , s ) ) t\mathbb{E}[\varphi(Z_t^k)]=\sum_{s=1}^{k}\varphi(p_k(t,s)) t E [ φ ( Z t k )] = ∑ s = 1 k φ ( p k ( t , s )) and t E [ φ ( Z t k − 1 ) ] = ∑ s = 1 k − 1 φ ( p k − 1 ( t , s ) ) t\mathbb{E}[\varphi(Z_t^{k-1})]=\sum_{s=1}^{k-1}\varphi(p_{k-1}(t,s)) t E [ φ ( Z t k − 1 )] = ∑ s = 1 k − 1 φ ( p k − 1 ( t , s )) . Dividing by t t t proves the claim. □
Theorem D.5. For 2 ≤ k ≤ n 2 \le k \le n 2 ≤ k ≤ n , r ( n , k ) > r ( n , k − 1 ) r(n,k)>r(n,k-1) r ( n , k ) > r ( n , k − 1 ) . Equivalently, ρ o r d ( U k , n ) < ρ o r d ( U k − 1 , n ) \rho_{\mathrm{ord}}(U_{k,n})<\rho_{\mathrm{ord}}(U_{k-1,n}) ρ ord ( U k , n ) < ρ ord ( U k − 1 , n ) .
Proof. Let m = k − 1 m=k-1 m = k − 1 , and let ξ t \xi_t ξ t be independent Bernoulli( m / k ) (m/k) ( m / k ) variables. For c ≥ 0 c\ge0 c ≥ 0 , the function ( x − c ) + (x-c)_+ ( x − c ) + is convex and vanishes at zero. By Lemma D.4 ,
E [ ( Z t m − c ) + ] ≤ m k E [ ( Z t k − c ) + ] = E [ ( ξ t Z t k − c ) + ] . \mathbb{E}[(Z_t^m-c)_+]\le\frac{m}{k}\mathbb{E}[(Z_t^k-c)_+]=\mathbb{E}[(\xi_tZ_t^k-c)_+]. E [( Z t m − c ) + ] ≤ k m E [( Z t k − c ) + ] = E [( ξ t Z t k − c ) + ] .
By (39) and Lemmas D.2 and D.3 ,
m r ( n , m ) = Φ m ( Z m ) ≤ Φ m ( ( ξ t Z t k ) t ) ≤ m k [ Φ k ( Z k ) − δ ( Φ k ( Z k ) − Φ m ( Z k ) ) ] . mr(n,m)=\Phi_m(Z^m)\le\Phi_m((\xi_tZ_t^k)_t)\le\frac{m}{k}\left[\Phi_k(Z^k)-\delta\left(\Phi_k(Z^k)-\Phi_m(Z^k)\right)\right]. m r ( n , m ) = Φ m ( Z m ) ≤ Φ m (( ξ t Z t k ) t ) ≤ k m [ Φ k ( Z k ) − δ ( Φ k ( Z k ) − Φ m ( Z k ) ) ] .
It remains to show Φ k ( Z k ) > Φ m ( Z k ) \Phi_k(Z^k)>\Phi_m(Z^k) Φ k ( Z k ) > Φ m ( Z k ) . For t ≤ k t\le k t ≤ k and every s ≤ t s\le t s ≤ t , we have Z t k ≥ p k ( t , t ) = ( n − t k − t ) / ( n k ) = ( n k ) − 1 Z_t^k\ge p_k(t,t)=\binom{n-t}{k-t}/\binom{n}{k}=\binom{n}{k}^{-1} Z t k ≥ p k ( t , t ) = ( k − t n − t ) / ( k n ) = ( k n ) − 1 . Follow an optimal m m m -selection rule, and use one additional slot at its first rejection among the first k k k times; such a rejection exists because at most m = k − 1 m=k-1 m = k − 1 of these times are selected. This gains at least ( n k ) − 1 \binom{n}{k}^{-1} ( k n ) − 1 on every realization. Hence m r ( n , m ) < m k k r ( n , k ) mr(n,m)<\frac{m}{k}kr(n,k) m r ( n , m ) < k m k r ( n , k ) . □
Together with Lemma D.1 , the theorem gives ρ o r d ( U k , n ) ≤ ρ o r d ( U 1 , n ) ≤ e \rho_{\mathrm{ord}}(U_{k,n})\le\rho_{\mathrm{ord}}(U_{1,n})\le e ρ ord ( U k , n ) ≤ ρ ord ( U 1 , n ) ≤ e . This recovers, as a guarantee on value, the known ratio e e e for uniform matroids; the ordinal algorithm of [12 ] even selects each of the k k k largest elements with the classical cutoff probability.
A graphic counterexample
Theorem D.6. Let N = 10 42 N = 10^{42} N = 1 0 42 , and let M \mathcal{M} M be the graphic matroid of the complete bipartite graph K 2 , N K_{2,N} K 2 , N . Then
ρ o r d ( M ( 3 ) ) < 100 53 < ρ o r d ( M ) . \rho_{\mathrm{ord}}(\mathcal{M}^{(3)}) < \frac{100}{53} < \rho_{\mathrm{ord}}(\mathcal{M}). ρ ord ( M ( 3 ) ) < 53 100 < ρ ord ( M ) . Since rank ( M ) = N + 1 \operatorname{rank}(\mathcal{M}) = N + 1 rank ( M ) = N + 1 , there is 4 ≤ k ≤ N + 1 4 \le k \le N + 1 4 ≤ k ≤ N + 1 with ρ o r d ( M ( k ) ) > ρ o r d ( M ( k − 1 ) ) \rho_{\mathrm{ord}}(\mathcal{M}^{(k)}) > \rho_{\mathrm{ord}}(\mathcal{M}^{(k-1)}) ρ ord ( M ( k ) ) > ρ ord ( M ( k − 1 ) ) . The upper bound on 1 / ρ o r d ( M ) 1/\rho_{\mathrm{ord}}(\mathcal{M}) 1/ ρ ord ( M ) holds even for algorithms that observe numerical values and know the input distribution used in the proof.
The graph K 2 , N K_{2,N} K 2 , N has no cycle of length at most three, so every set of at most three edges is independent and M ( 3 ) \mathcal{M}^{(3)} M ( 3 ) is the uniform matroid U 3 , 2 N U_{3,2N} U 3 , 2 N . The theorem follows from the next two propositions and Lemma D.1 .
Proposition D.7. For every m ≥ 3 m \ge3 m ≥ 3 , r ( m , 3 ) ≥ L ⋆ r(m,3) \ge L^\star r ( m , 3 ) ≥ L ⋆ , where L ⋆ = 0.5326 … > 53 / 100 L^\star= 0.5326\ldots> 53/100 L ⋆ = 0.5326 … > 53/100 is given by (40) .
Proof. Consider h ≥ 6 h \ge6 h ≥ 6 elements and the following rule: reject the first ⌊ h / 6 ⌋ \lfloor h/6 \rfloor ⌊ h /6 ⌋ arrivals; until time ⌊ h / 2 ⌋ \lfloor h/2 \rfloor ⌊ h /2 ⌋ , accept records; afterwards, accept arrivals among the three largest so far; stop after three acceptances. Call the t t t -th arrival eligible if the rule would accept it with a free slot: R t = 1 R_t = 1 R t = 1 in the first active phase, and R t ≤ 3 R_t \le3 R t ≤ 3 in the second. Eligibility events are independent, with probabilities 1 / t 1/t 1/ t and 3 / t 3/t 3/ t , respectively, and a slot is free at time t t t exactly when fewer than three earlier arrivals were eligible. This event depends only on R 1 , … , R t − 1 R_1,\ldots,R_{t-1} R 1 , … , R t − 1 , so it is independent of R t R_t R t .
Apply (38) with h h h in place of n n n . Given a free slot, time t t t contributes in expectation p 3 ( t , 1 ) / t p_3(t,1)/t p 3 ( t , 1 ) / t selected top-three elements in the first phase, and 1 t ∑ s ≤ 3 p 3 ( t , s ) = E [ Ξ 3 , t ] / t = 3 / h \frac{1}{t}\sum_{s \le3}p_3(t,s) = \mathbb{E}[\Xi_{3,t}]/t = 3/h t 1 ∑ s ≤ 3 p 3 ( t , s ) = E [ Ξ 3 , t ] / t = 3/ h in the second. Write x = t / h x = t/h x = t / h . As h → ∞ h \to\infty h → ∞ , p 3 ( t , 1 ) → 1 − ( 1 − x ) 3 p_3(t,1) \to1 - (1-x)^3 p 3 ( t , 1 ) → 1 − ( 1 − x ) 3 uniformly, and the expected number of eligible arrivals before t t t converges uniformly to λ ( x ) = ln ( 6 x ) \lambda(x) = \ln(6x) λ ( x ) = ln ( 6 x ) for x ≤ 1 / 2 x \le1/2 x ≤ 1/2 and to λ ( x ) = ln 3 + 3 ln ( 2 x ) \lambda(x) = \ln3 + 3\ln(2x) λ ( x ) = ln 3 + 3 ln ( 2 x ) for x ≥ 1 / 2 x \ge1/2 x ≥ 1/2 . By Le Cam’s inequality [52 ] , the number of eligible arrivals before t t t differs in total variation from a Poisson variable with the same mean by at most the sum of the squared eligibility probabilities, which is O ( 1 / h ) O(1/h) O ( 1/ h ) . Hence the expected fraction of the top three selected converges to
L ⋆ = ∫ 1 / 6 1 / 2 ( 1 + λ + λ 2 2 ) 3 − 3 x + x 2 18 x d x + ∫ 1 / 2 1 ( 1 + λ + λ 2 2 ) d x 24 x 3 . (40) L^\star= \int_{1/6}^{1/2}\left(1+\lambda+\frac{\lambda^2}{2}\right)\frac{3-3x+x^2}{18x}\,dx+\int_{1/2}^{1}\left(1+\lambda+\frac{\lambda^2}{2}\right)\frac{dx}{24x^3}. \tag*{(40)} L ⋆ = ∫ 1/6 1/2 ( 1 + λ + 2 λ 2 ) 18 x 3 − 3 x + x 2 d x + ∫ 1/2 1 ( 1 + λ + 2 λ 2 ) 24 x 3 d x . (40) where λ = λ ( x ) \lambda= \lambda(x) λ = λ ( x ) . With α 2 = ln 2 \alpha_2 = \ln2 α 2 = ln 2 and α 3 = ln 3 \alpha_3 = \ln3 α 3 = ln 3 , integration gives
L ⋆ = − 3 α 2 2 32 − α 2 α 3 16 − 5 α 2 32 + α 3 3 36 + 11 α 3 2 144 + 47 α 3 144 + 425 1728 = 0.53261 … L^\star= -\frac{3\alpha_2^2}{32}-\frac{\alpha_2\alpha_3}{16}-\frac{5\alpha_2}{32}+\frac{\alpha_3^3}{36}+\frac{11\alpha_3^2}{144}+\frac{47\alpha_3}{144}+\frac{425}{1728}=0.53261\ldots L ⋆ = − 32 3 α 2 2 − 16 α 2 α 3 − 32 5 α 2 + 36 α 3 3 + 144 11 α 3 2 + 144 47 α 3 + 1728 425 = 0.53261 … Enclosures 0.693 < α 2 < 0.694 0.693 < \alpha_2 < 0.694 0.693 < α 2 < 0.694 and 1.098 < α 3 < 1.099 1.098 < \alpha_3 < 1.099 1.098 < α 3 < 1.099 , used with the unfavorable endpoint in each term, give L ⋆ > 0.531 L^\star> 0.531 L ⋆ > 0.531 .
To apply this to m m m elements, choose h ≥ max { m , 6 } h \ge\max\{m,6\} h ≥ max { m , 6 } and insert h − m h-m h − m fictitious elements, smaller than all real ones, at uniformly random positions and in a uniformly random relative order; both are sampled before the arrivals. Comparisons involving fictitious elements are known to the algorithm. Fictitious selections are discarded but count against the capacity. The combined order is uniform and its three largest elements are real, so r ( m , 3 ) r(m,3) r ( m , 3 ) is at least the value of the rule on h h h elements. Letting h → ∞ h \to\infty h → ∞ proves the proposition.
Proposition D.8. With N = 10 42 N = 10^{42} N = 1 0 42 , every online algorithm for the graphic matroid of K 2 , N K_{2,N} K 2 , N , even one observing numerical values, has expected value less than 53 100 \frac{53}{100} 100 53 times the expected optimum on some random instance. Hence ρ o r d ( M ) > 100 / 53 \rho_{\mathrm{ord}}(\mathcal{M}) > 100/53 ρ ord ( M ) > 100/53 .
Proof. We use the construction of [10 ] . First consider two elements. Fix integers Q > 1 Q > 1 Q > 1 and L ≥ 1 L \ge1 L ≥ 1 . Choose i ∈ { 0 , … , L − 1 } i \in\{0,\ldots,L-1\} i ∈ { 0 , … , L − 1 } with probability Q − ( i + 1 ) / Γ Q^{-(i+1)}/\Gamma Q − ( i + 1 ) /Γ , where Γ = ∑ i = 0 L − 1 Q − ( i + 1 ) \Gamma= \sum_{i=0}^{L-1} Q^{-(i+1)} Γ = ∑ i = 0 L − 1 Q − ( i + 1 ) , and present the values Q i Q^i Q i and Q i + 1 Q^{i+1} Q i + 1 in uniformly random order. The expected maximum is ν = L / Γ \nu= L/\Gamma ν = L /Γ . Suppose an algorithm accepts a first value Q j Q^j Q j with probability p j p_j p j . Granting it the second value whenever it rejects the first, its expected reward at scale i i i is at most
1 2 [ p i Q i + ( 1 − p i ) Q i + 1 ] + 1 2 [ p i + 1 Q i + 1 + ( 1 − p i + 1 ) Q i ] = Q i + 1 [ 1 + 1 / Q 2 + ( 1 − 1 / Q ) ( p i + 1 − p i ) 2 ] . \frac{1}{2}\left[p_iQ^i+(1-p_i)Q^{i+1}\right]+\frac{1}{2}\left[p_{i+1}Q^{i+1}+(1-p_{i+1})Q^i\right]=Q^{i+1}\left[\frac{1+1/Q}{2}+\frac{(1-1/Q)(p_{i+1}-p_i)}{2}\right]. 2 1 [ p i Q i + ( 1 − p i ) Q i + 1 ] + 2 1 [ p i + 1 Q i + 1 + ( 1 − p i + 1 ) Q i ] = Q i + 1 [ 2 1 + 1/ Q + 2 ( 1 − 1/ Q ) ( p i + 1 − p i ) ] .
Each scale has probability times Q i + 1 Q^{i+1} Q i + 1 equal to 1 / Γ 1/\Gamma 1/Γ , so the differences p i + 1 − p i p_{i+1}-p_i p i + 1 − p i telescope. Using p L − p 0 ≤ 1 p_L-p_0\le1 p L − p 0 ≤ 1 , the expected reward is at most α ν \alpha\nu α ν , where α = ( 1 + 1 / Q ) / 2 + ( 1 − 1 / Q ) / ( 2 L ) \alpha=(1+1/Q)/2+(1-1/Q)/(2L) α = ( 1 + 1/ Q ) /2 + ( 1 − 1/ Q ) / ( 2 L ) .
Now let o 1 , o 2 o_1,o_2 o 1 , o 2 be the two vertices of degree N N N in K 2 , N K_{2,N} K 2 , N , and let w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N be the others. The edges o 1 w i , o 2 w i o_1w_i,o_2w_i o 1 w i , o 2 w i form the i i i -th pair. Draw an independent two-element instance for each pair, assign its values to the two edges in random order, and present all edges in uniformly random order. For each pair, consider the first selected edge of that pair. Condition on the values of the other pairs, the arrival order of the edges, and the algorithm’s randomness; these are independent of the pair’s scale and of the assignment of its values, so the first arriving edge of the pair carries either value with probability 1 / 2 1/2 1/2 , as in the two-element instance. The decision on that edge depends only on its value. The bound above therefore applies, and the first selections have total expected value at most N α ν N\alpha\nu N α ν .
A forest contains both edges of at most one pair, since two complete pairs form a cycle of length four. The remaining selections are worth at most Q L Q^L Q L . On the other hand, the heavier edges of the pairs form a forest, so the expected optimum is at least N ν N\nu N ν . The ratio is at most α + Q L / ( N ν ) \alpha+Q^L/(N\nu) α + Q L / ( N ν ) .
For Q = 100 Q=100 Q = 100 , L = 21 L=21 L = 21 , and N = Q L N=Q^L N = Q L , we have Γ < 1 / 99 \Gamma<1/99 Γ < 1/99 , so ν > 2079 \nu>2079 ν > 2079 and α = 37 / 70 \alpha=37/70 α = 37/70 . The ratio is at most 37 / 70 + 1 / 2079 < 53 / 100 37/70+1/2079<53/100 37/70 + 1/2079 < 53/100 . A c c c -competitive algorithm has expected value at least 1 / c 1/c 1/ c times the optimum on every fixed instance, and hence on average. Therefore every such c c c satisfies c ≥ ( 37 / 70 + 1 / 2079 ) − 1 > 100 / 53 c\ge(37/70+1/2079)^{-1}>100/53 c ≥ ( 37/70 + 1/2079 ) − 1 > 100/53 , and so does the infimum ρ o r d ( M ) \rho_{\mathrm{ord}}(\mathcal{M}) ρ ord ( M ) .
From Single-Sample Prophet Inequalities to Secretary
This appendix shows how to turn a single-sample matroid prophet algorithm into a matroid secretary algorithm. We give a self-contained presentation of the construction attributed to Wenzheng Li by [29 ] . We work in the secretary model with the matroid M = ( V , I ) \mathcal{M}=(V,\mathcal{I}) M = ( V , I ) and n = ∣ V ∣ n=|V| n = ∣ V ∣ known in advance; the values v ∈ R ≥ 0 V v\in\mathbb{R}_{\ge0}^{V} v ∈ R ≥ 0 V are fixed and arrive in uniformly random order. As in § 2 , Greedy ( T ) \operatorname{Greedy}(T) Greedy ( T ) is decreasing-value greedy on T T T with ties broken by labels, and f ≺ e f\prec e f ≺ e means that f f f precedes e e e in this order. For a nonnegative vector w w w indexed by T ⊆ V T\subseteq V T ⊆ V , write opt ( w ) = max { w ( I ) : I ∈ I , I ⊆ T } \operatorname{opt}(w)=\max\{w(I):I\in\mathcal{I}, I\subseteq T\} opt ( w ) = max { w ( I ) : I ∈ I , I ⊆ T } for the optimum value of the restriction to T T T ; thus opt ( v ∣ T ) = v ( Greedy ( T ) ) \operatorname{opt}(v|_T)=v(\operatorname{Greedy}(T)) opt ( v ∣ T ) = v ( Greedy ( T )) .
A single-sample prophet algorithm is c c c -competitive in random order if, for every matroid and independent nonnegative distributions, given one independent sample from each distribution, it selects an independent set of expected value at least 1 / c 1/c 1/ c times the expected optimum, when the arrival order is uniformly random and independent of the samples and values and is not known to the algorithm. By averaging over orders, Theorem 3.1 gives such an algorithm with c = 2 c=2 c = 2 .
Theorem E.1 (Secretary from single-sample prophet inequalities). A single-sample prophet algorithm that is c c c -competitive in random order yields a 16 c 2 16c^2 16 c 2 -competitive secretary algorithm for every matroid known in advance. The reduction preserves polynomial running time. With Algorithm 2, it gives an ordinal 64-competitive secretary algorithm.
The natural idea is to reject a prefix of the arrivals, use their values as samples, and run the prophet algorithm on the remaining elements. The difficulty is that the prophet algorithm may select an element whose value was used as a sample, and such an element has already been rejected. The reduction makes these conflicts rare: each element is presented to the prophet algorithm with a value that is nonzero only with a small probability q q q , independently as a sample and as a value. The useful reward is then linear in q q q , while a conflict requires both activations and costs only order q 2 q^2 q 2 . A preliminary sample ensures that this quadratic loss is charged against the optimum rather than against the total value of all elements.
A preliminary sample. Draw K 0 ∼ Bin ( n , 1 / 2 ) K_0 \sim\operatorname{Bin}(n,1/2) K 0 ∼ Bin ( n , 1/2 ) and reject the first K 0 K_0 K 0 arrivals, forming a set P P P ; it contains each element independently with probability 1 / 2 1/2 1/2 . An element e ∉ P e \notin P e ∈ / P is eligible if e ∉ cl ( { f ∈ P : f ≻ e } ) e \notin\operatorname{cl}(\{f \in P : f \succ e\}) e ∈ / cl ({ f ∈ P : f ≻ e }) . Let T T T be the set of eligible elements. Eligibility of e e e can be decided when e e e arrives, since all values in P P P have been observed.
Lemma E.2. E [ v ( T ) ] = E [ v ( Greedy ( P ) ) ] ≤ v ( Greedy ( V ) ) \mathbb{E}[v(T)] = \mathbb{E}[v(\operatorname{Greedy}(P))] \le v(\operatorname{Greedy}(V)) E [ v ( T )] = E [ v ( Greedy ( P ))] ≤ v ( Greedy ( V )) and E [ opt ( v ∣ T ) ] ≥ v ( Greedy ( V ) ) / 2 \mathbb{E}[\operatorname{opt}(v|_T)] \ge v(\operatorname{Greedy}(V))/2 E [ opt ( v ∣ T )] ≥ v ( Greedy ( V )) /2 .
Proof. Whether e ∈ cl ( { f ∈ P : f ≻ e } ) e \in\operatorname{cl}(\{f \in P : f \succ e\}) e ∈ cl ({ f ∈ P : f ≻ e }) is independent of whether e ∈ P e \in P e ∈ P . If it fails, then e ∈ Greedy ( P ) e \in\operatorname{Greedy}(P) e ∈ Greedy ( P ) when e ∈ P e \in P e ∈ P , and e ∈ T e \in T e ∈ T when e ∉ P e \notin P e ∈ / P ; both happen with probability 1 / 2 1/2 1/2 . Summing over e e e gives the equality, and Greedy ( P ) \operatorname{Greedy}(P) Greedy ( P ) is independent, which gives the inequality. Each e ∈ Greedy ( V ) e \in\operatorname{Greedy}(V) e ∈ Greedy ( V ) is not spanned by the elements preceding it, so Greedy ( V ) ∖ P \operatorname{Greedy}(V) \setminus P Greedy ( V ) ∖ P is an independent subset of T T T , of expected value v ( Greedy ( V ) ) / 2 v(\operatorname{Greedy}(V))/2 v ( Greedy ( V )) /2 .
Rare activations. Condition on P P P , and let V ′ = V ∖ P V' = V \setminus P V ′ = V ∖ P and N = ∣ V ′ ∣ N = |V'| N = ∣ V ′ ∣ . The remaining arrival order is uniform on V ′ V' V ′ . For e ∈ V ′ e \in V' e ∈ V ′ let v ˉ e = v e 1 { e ∈ T } \bar{v}_e = v_e 1\{e \in T\} v ˉ e = v e 1 { e ∈ T } , which can be computed when e e e arrives. Fix q ∈ ( 0 , 1 ) q \in(0,1) q ∈ ( 0 , 1 ) . We run the prophet algorithm on the restriction of M \mathcal{M} M to V ′ V' V ′ with the independent distributions D e = ( 1 − q ) δ 0 + q δ v ˉ e D_e = (1-q)\delta_0 + q\delta_{\bar{v}_e} D e = ( 1 − q ) δ 0 + q δ v ˉ e . Its sample and value of e e e are X e v ˉ e X_e\bar{v}_e X e v ˉ e and Y e v ˉ e Y_e\bar{v}_e Y e v ˉ e , where all X e , Y e X_e,Y_e X e , Y e are independent Bernoulli( q ) (q) ( q ) bits.
Draw independent Bernoulli( q ) (q) ( q ) bits b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N , and let K = ∑ i b i K = \sum_i b_i K = ∑ i b i . Reject the next K K K arrivals, forming a set R R R , and set X e = 1 { e ∈ R } X_e = 1\{e \in R\} X e = 1 { e ∈ R } . Give the prophet algorithm the sample v ˉ e \bar{v}_e v ˉ e for e ∈ R e \in R e ∈ R and 0 0 0 for e ∈ V ′ ∖ R e \in V' \setminus R e ∈ V ′ ∖ R , and draw the bits Y e Y_e Y e independently.
For i = 1 , … , N i = 1,\ldots,N i = 1 , … , N : if b i = 1 b_i = 1 b i = 1 , take the next element e e e of R R R in its arrival order; if b i = 0 b_i = 0 b i = 0 , let e e e be the next arrival and compute v ˉ e \bar{v}_e v ˉ e . Present e e e to the prophet algorithm with value Y e v ˉ e Y_e\bar{v}_e Y e v ˉ e . If the prophet algorithm selects e e e and b i = 0 b_i = 0 b i = 0 , accept e e e .
All selections are recorded in the internal state of the prophet algorithm, including selections of elements of R R R , which are discarded. Hence the accepted set is a subset of the prophet algorithm’s independent output. Every decision on an arrival is made immediately.
Lemma E.3. Conditional on P P P , the set R R R contains each element of V ′ V' V ′ independently with probability q q q , and the order Σ \Sigma Σ in which elements are presented to the prophet algorithm is uniform and independent of R R R and of the bits Y Y Y .
Proof. Fix D ⊆ V ′ D \subseteq V' D ⊆ V ′ and an order σ \sigma σ of V ′ V' V ′ . The outcome ( R , Σ ) = ( D , σ ) (R,\Sigma) = (D,\sigma) ( R , Σ ) = ( D , σ ) occurs for exactly one arrival order and one bit string: the arrival order lists D D D in the order σ \sigma σ followed by V ′ ∖ D V' \setminus D V ′ ∖ D in the order σ \sigma σ , and the bits mark the positions of D D D in σ \sigma σ . Hence
Pr [ R = D , Σ = σ ∣ P ] = q ∣ D ∣ ( 1 − q ) N − ∣ D ∣ N ! . \Pr[R = D,\ \Sigma= \sigma\mid P] = \frac{q^{|D|}(1-q)^{N-|D|}}{N!}. Pr [ R = D , Σ = σ ∣ P ] = N ! q ∣ D ∣ ( 1 − q ) N − ∣ D ∣ .
The bits Y Y Y are drawn independently of both.
By Lemma E.3 , the prophet algorithm sees independent samples and values from the distributions D e D_e D e , in a uniformly random order independent of them, exactly as its guarantee requires.
Proof of Theorem E.1 . A selected element of R R R contributes to the prophet algorithm’s value only if X e = Y e = 1 X_e=Y_e=1 X e = Y e = 1 , so the discarded value is at most ∑ e ∈ V ′ X e Y e v ˉ e \sum_{e\in V'}X_eY_e\bar{v}_e ∑ e ∈ V ′ X e Y e v ˉ e , whose conditional expectation is q 2 v ( T ) q^2v(T) q 2 v ( T ) . Every accepted element has value v e ≥ Y e v ˉ e v_e\ge Y_e\bar{v}_e v e ≥ Y e v ˉ e . The prophet guarantee therefore gives
E [ v ( A L G ) ∣ P ] ≥ 1 c E [ opt ( ( Y e v ˉ e ) e ∈ V ′ ) ∣ P ] − q 2 v ( T ) ≥ q c opt ( v ∣ T ) − q 2 v ( T ) , \mathbb{E}[v(\mathrm{ALG})\mid P]\ge\frac{1}{c}\mathbb{E}\left[\operatorname{opt}\left((Y_e\bar{v}_e)_{e\in V'}\right)\mid P\right]-q^2v(T)\ge\frac{q}{c}\operatorname{opt}(v\vert_T)-q^2v(T), E [ v ( ALG ) ∣ P ] ≥ c 1 E [ opt ( ( Y e v ˉ e ) e ∈ V ′ ) ∣ P ] − q 2 v ( T ) ≥ c q opt ( v ∣ T ) − q 2 v ( T ) ,
where the second inequality retains the activated elements of Greedy ( T ) \operatorname{Greedy}(T) Greedy ( T ) . By Lemma E.2 , E [ v ( A L G ) ] ≥ ( q / ( 2 c ) − q 2 ) v ( Greedy ( V ) ) \mathbb{E}[v(\mathrm{ALG})]\ge(q/(2c)-q^2)v(\operatorname{Greedy}(V)) E [ v ( ALG )] ≥ ( q / ( 2 c ) − q 2 ) v ( Greedy ( V )) . Choosing q = 1 / ( 4 c ) q=1/(4c) q = 1/ ( 4 c ) gives v ( Greedy ( V ) ) / ( 16 c 2 ) v(\operatorname{Greedy}(V))/(16c^2) v ( Greedy ( V )) / ( 16 c 2 ) .
Eligibility requires one independence query per arrival against a prefix of Greedy ( P ) \operatorname{Greedy}(P) Greedy ( P ) , and the remaining bookkeeping is polynomial, so the reduction preserves polynomial running time. For Algorithm 2, every value presented to the prophet algorithm is either 0 0 0 or an observed value of an eligible element, and the algorithm only compares values. Treat every eligible element as larger than every artificial zero. For positive distinct values, the comparisons and the eligibility tests then depend only on the relative order of the observed values, so the secretary algorithm is ordinal; its guarantee extends to all nonnegative values, with ties resolved by labels, by taking limits of positive distinct value vectors with the same order. With c = 2 c=2 c = 2 , the ratio is 64 64 64 .