The final count and a secretary rule

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

This lesson assembles the estimates of the previous lessons into the proof of Proposition 4.1 and Theorem 3.1 of Prophets, matroids and an almighty adversary. Three steps remain. The test mask thins each group independently of everything its paths depend on, which turns rank into expected acceptances. The cost of later path enlargements is small in expectation. Summing over weight levels gives a guarantee for the main rule when no single label dominates, and the maximum rule covers the other case. A last section derives a guarantee for the secretary problem with an adversarial suffix.

We use the statistics \(\lambda_h\), \(z_h\), \(c_h\) of Layers and a rank bound for every order, the transfer lemma of From safe samples to unrevealed rank, and the candidate mass lemma and maximum rule of Rounding, a maximum rule and candidates. For a true group \(U_i\) listed as \(G_h\) write \(\lambda_i=\lambda_h\), \(z_i=z_h\), \(c_i=c_h\); for an unlisted group all three are zero.

1. Thinning by the test mask

Lemma 1.1 (test thinning). Let \(U_i\) be a true group, and let \(\mathcal F_{-i}\) be generated by \(H,D,C\), the parity, and the test mask outside \(U_i\). Then \[ \mathbb E[\lambda_i\mid\mathcal F_{-i}]\geq t\,(z_i-c_i). \]

Proof. If \(U_i\) is unlisted, both sides vanish; listing is determined by \(D\). Suppose \(U_i=G_h\). The paths depend on \(H,D,C\) only; the birth sets \(P_{h,b}\) and valid endpoints use the parity; \(O=D\cup C\); the competition sets \(K_{h,b}\) use the test bits of lighter groups. So all sets \(S_{h,b}\), \(\widehat F(b-2)\), \(K_{h,b}\) and the numbers \(z_h\), \(c_h\) are \(\mathcal F_{-i}\)-measurable, while the test bits on \(U_i\) are independent of \(\mathcal F_{-i}\) with rate \(t\). For each \(b\) choose, measurably in \(\mathcal F_{-i}\), a set \(W_b\subseteq S_{h,b}\) independent over the final base \(\widehat\Omega_b\) of the fourth lesson, with \(|W_b|=\operatorname{rk}(S_{h,b}\mid\widehat\Omega_b)\). Its subset \(W_b\cap T\) is still independent over the same base and lies in \(T_h\cap S_{h,b}\), so \[ \begin{gathered} \operatorname{rk}\bigl(T_h\cap S_{h,b}\bigm|\widehat\Omega_b\bigr)\geq|W_b\cap T|,\\ \mathbb E\bigl[|W_b\cap T|\bigm|\mathcal F_{-i}\bigr]=t|W_b|. \end{gathered} \] Summing over \(b\in\mathfrak B_h\) and applying Lemma 4.1 of the fourth lesson gives \(\mathbb E[\lambda_h\mid\mathcal F_{-i}]\geq t\sum_b|W_b|\geq t(z_h-c_h)\). \(\square\)

Lemma 1.2 (expected cost). For every true group \(U_i\), \[ \mathbb E[c_i\mid H]\leq t\,n_i+\Bigl(t+\frac1\kappa\Bigr)\sum_{\ell>i}n_\ell. \]

Proof. If \(U_i=G_h\), the heavier listed groups \(G_j\), \(j>h\), are true groups \(U_\ell\) with \(\ell>i\), so pointwise \[ \begin{aligned} c_i\leq{}&|C\cap U_i|\\ &+\sum_{\ell>i}\Bigl(|C\cap U_\ell|+\frac{|D\cap U_\ell|}\kappa\Bigr), \end{aligned} \] and this also holds when \(c_i=0\). Given \(H\), the masks \(C\) and \(D\) have rates \(t\) and \(\frac14\). \(\square\)

Combining Lemma 1.1, Lemma 1.2 and the transfer lemma, Lemma 3.1 of the eighth lesson, for every true group with \(n_i\geq\kappa\): \[ \begin{aligned} &\mathbb E[\lambda_i\mid H]\geq\frac t\kappa\,\Bigl(\gamma|Y_i|\\ &\quad-\bigl(2^{-23}+t\kappa\bigr)n_i\\ &\quad-(1+t\kappa)\sum_{\ell>i}n_\ell\Bigr). \end{aligned}\tag{1.1} \] The variables \(\lambda_i\) for different groups depend on one another's test bits, but each estimate is valid separately, and expectations add.

2. Summing over weight levels

Let \(A_{\mathrm{main}}(\pi)\) be the set accepted by the main rule under the order \(\pi\), and let \(\mathcal A(H)=\{i:n_i\geq\kappa\}\) be the analysed groups.

Lemma 2.1 (minimum over orders). For every seed of the main rule, \[ \begin{aligned} &\min_\pi u\bigl(A_{\mathrm{main}}(\pi)\bigr)\\ &\quad\geq\frac12\sum_{i\in\mathcal A(H)}B^i\lambda_i. \end{aligned}\tag{2.1} \]

Proof. Fix the seed and an order \(\pi\), and let \(N_i(\pi)\) be the number of accepted labels of rounded weight at least \(B^i\). By Lemma 3.1 of the fourth lesson, \(\lambda_i\leq N_i(\pi)\) for listed groups, and trivially for unlisted ones. An accepted label of weight \(B^\ell\) is counted in \(N_i(\pi)\) for every \(i\leq\ell\), and \(\sum_{i\leq\ell}B^i=B^\ell\frac B{B-1}<2B^\ell\). Hence \[ \begin{aligned} \sum_{i\in\mathcal A(H)}B^i\lambda_i&\leq\sum_iB^iN_i(\pi)\\ &\leq2\,u\bigl(A_{\mathrm{main}}(\pi)\bigr). \end{aligned} \] The left side does not depend on \(\pi\). \(\square\)

The order is minimized before any expectation is taken. Now multiply (1.1) by \(B^i\), sum over \(i\in\mathcal A(H)\), and bound the error terms with \(u(U)=\sum_iB^in_i\): \[ \begin{aligned} &\sum_{i\in\mathcal A(H)}B^in_i\leq u(U),\\ &\sum_{i\in\mathcal A(H)}B^i\sum_{\ell>i}n_\ell\leq\sum_\ell n_\ell\sum_{i<\ell}B^i\\ &\qquad=\frac{u(U)}{B-1}. \end{aligned} \] With the constants of the second lesson, \(t\kappa=2^{-40}\) and \((1+t\kappa)/(B-1)<2^{-31}\), so \[ 2^{-23}+t\kappa+\frac{1+t\kappa}{B-1}<2^{-21}. \] Together with (2.1) this gives, with \(Y_{\mathcal A}=\bigcup_{i\in\mathcal A(H)}Y_i\), so that \(u(Y_{\mathcal A})=\sum_{i\in\mathcal A(H)}B^i|Y_i|\), \[ \begin{aligned} &\mathbb E\Bigl[\min_\pi u\bigl(A_{\mathrm{main}}(\pi)\bigr)\Bigm|H\Bigr]\\ &\quad\geq\frac t{2\kappa}\bigl(\gamma\,u(Y_{\mathcal A})\\ &\qquad-2^{-21}u(U)\bigr). \end{aligned}\tag{2.2} \]

3. The two cases and the constant

Assume \(W>0\), so \(m_*>0\). Every candidate is a positive nonloop, so its rounded weight is at most \(m_*\). By Lemma 3.1 of the second lesson \(Y\subseteq U\), so \(Y\) is the disjoint union of the sets \(Y_i\). A group outside \(\mathcal A(H)\) has \(|Y_i|\leq n_i<\kappa\), hence \[ \begin{aligned} u(Y\setminus Y_{\mathcal A})&\leq\kappa\sum_{i:\,B^i\leq m_*}B^i\\ &<2\kappa m_*. \end{aligned}\tag{3.1} \]

Case \(m_*\leq W/(8\kappa)\). By Lemma 3.1 of the second lesson and (3.1), \(\mathbb E\,u(Y_{\mathcal A})\geq\frac W2-2\kappa m_*\geq\frac W4\), and \(\mathbb E\,u(U)\leq W\). Since \(\gamma=2^{-16}\), \(\frac\gamma4-2^{-21}=7\cdot2^{-21}\geq\frac\gamma8\), and averaging (2.2) over \(H\) gives \[ \begin{aligned} &\mathbb E\Bigl[\min_\pi u\bigl(A_{\mathrm{main}}(\pi)\bigr)\Bigr]\\ &\quad\geq\frac{t\gamma}{16\kappa}W. \end{aligned}\tag{3.2} \]

Case \(m_*>W/(8\kappa)\). Lemma 2.1 of the second lesson gives \(\mathbb E[\min_\pi u(A_{\max}(\pi))]\geq m_*/4\), which exceeds \(W/(32\kappa)\).

Proof of Proposition 4.1 of the first lesson. The complete rule chooses the maximum rule or the main rule by a fair coin, which is part of the seed; for every complete seed the minimum over orders is taken separately, so the guarantee holds even when the adversary's order depends on the coin. In the first case the main branch contributes at least \(\frac12\cdot\frac{t\gamma}{16\kappa}W=\frac{t\gamma}{32\kappa}W\); in the second the maximum branch contributes more than \(\frac W{64\kappa}\), which is larger. Accepted labels satisfy \(w_e\geq u_e\), and \(W\geq\mathrm{OPT}_M(w)/B\) by Lemma 1.1 of the second lesson. So \[ \begin{aligned} &\mathbb E_\rho\Bigl[\min_\pi w\bigl(A(w,\rho,\pi)\bigr)\Bigr]\\ &\quad\geq\frac{t\gamma}{32\kappa B}\,\mathrm{OPT}_M(w)\\ &\quad=2^{-140-16-5-100-32}\,\mathrm{OPT}_M(w)\\ &\quad=2^{-293}\,\mathrm{OPT}_M(w). \end{aligned} \] If \(W=0\), then \(\mathrm{OPT}_M(w)=0\) and there is nothing to prove. Feasibility for every seed and order is Lemma 1.1 of the fourth lesson and Lemma 2.1 of the second; the seed (the four masks, the parity, the mask of the maximum rule and the branch coin) takes finitely many values, and the sacrificed set is a function of it; the rule is measurable. \(\square\)

Proof of Theorem 3.1 of the first lesson. Lemma 4.2 of the first lesson turns the fixed-vector rule into a one-sample rule with the same constant \(2^{-293}\). \(\square\)

The construction covers empty ground sets, loops, rank zero, ties and zero weights. Each realized weight vector is finite even when the laws have unbounded support, and only \(\mathbb E[\mathrm{OPT}_M(V)]<\infty\) is assumed. OpenAI's Lean formalization proves the one-sample statement with the constant \(2^{-310}\), and the fixed-vector statement with \(2^{-293}\), both with a finite seed law and feasibility after every prefix.

4. A secretary rule with an adversarial suffix

In the secretary problem the weights are fixed in advance and the arrival order is uniformly random. The fixed-vector guarantee gives more: the rule may observe a random initial segment of a uniformly random order, and afterwards an adversary who knows everything, including the rule's entire seed, may rearrange the rest.

Corollary 4.1. For every finite matroid \(M\) there is a measurable randomized online rule with the following property. Fix \(w\in[0,\infty)^E\) before all randomness. The rule draws its seed \(\mathsf Q\), independent of a uniformly random order \(\sigma\) of \(E\), and fixes a prefix length \(K\) as part of \(\mathsf Q\). It observes the first \(K\) labels of \(\sigma\) with their weights, in order, and rejects them. Then an adversary who knows \(M\), \(w\), the observed prefix and \(\mathsf Q\) chooses, measurably, any order \(\tau\) of the remaining labels, which arrive in that order; the rule decides irrevocably at each arrival and keeps its accepted set \(A\) independent. For every such adversary, \[ \mathbb E[w(A)]\geq2^{-293}\,\mathrm{OPT}_M(w). \]

Proof. Let \(\rho\) be the seed of the fixed-vector rule, including its branch coin \(J\). Its sacrificed set contains each label independently with probability \(p_J\): \(p_{\max}=\frac12\) in the maximum branch, and in the main branch, where it is \(H\cup D\cup C\), \[ p_{\mathrm{main}}=1-\tfrac12\cdot\tfrac34\cdot(1-t)=\tfrac58+\tfrac38t. \] Let \(n=|E|\). The seed \(\mathsf Q\) contains \(J\) and \(K\), with \(K\) binomial with parameters \(n\) and \(p_J\) given \(J\), drawn independently of \(\sigma\). For the prefix set \(P=\{\sigma_1,\ldots,\sigma_K\}\) and every \(p\subseteq E\), \[ \begin{aligned} \Pr(P=p\mid J)&=\frac{\Pr(K=|p|\mid J)}{\binom n{|p|}}\\ &=p_J^{|p|}(1-p_J)^{n-|p|}, \end{aligned} \] since given \(K=k\) the prefix set is a uniform \(k\)-set. So \(P\) has, given \(J\), exactly the law of the sacrificed set.

After the prefix, rebuild \(\rho\) from its conditional law given \(J\) and \(\Xi(\rho)=P\). In the maximum branch, set the mask equal to \(P\). In the main branch, set the triple \((\mathbf 1_H,\mathbf 1_D,\mathbf 1_C)\) equal to \((0,0,0)\) at labels outside \(P\), and at each label of \(P\), independently, draw it from its original law conditioned on being nonzero; draw the test mask, the parity and all unused coins from their original laws. Since the triples are independent across labels and the sacrificed set is the set of labels with a nonzero triple, this kernel, combined with the law of \(P\), reproduces exactly the joint law of \(J\) and \(\rho\). The seed \(\mathsf Q\) contains in advance the independent uniform variables used by these finite kernels; after the prefix they are evaluated using only the set \(P\), not the weights. So \(\rho\) is a function of \(\mathsf Q\) and \(P\), and the adversary knows it.

Run the fixed-vector rule with seed \(\rho\). It sacrifices exactly \(P\) and learns \(w\) there, which is what has been observed; feed it the prefix in its order, all rejected, and then each suffix label as it arrives. For the combined order \(\pi=(\sigma_1,\ldots,\sigma_K,\tau)\) its accepted set is \(A(w,\rho,\pi)\). For every realization, even when \(\tau\) depends on \(\mathsf Q\) and the prefix, \[ \begin{aligned} w(A)&=w\bigl(A(w,\rho,\pi)\bigr)\\ &\geq\min_{\pi'}w\bigl(A(w,\rho,\pi')\bigr). \end{aligned} \] The marginal law of \(\rho\) is the original one, and \(w\) is fixed, so taking expectations and applying Proposition 4.1 of the first lesson proves the corollary. Feasibility for every prefix comes from the fixed-vector rule. \(\square\)

The order-oblivious form, a random observed prefix followed by an adversarial suffix, goes back to Azar, Kleinberg and Weinberg. For uniformly random arrivals throughout, constant ratios with much larger constants have recently been announced by Singla, by Huang, and by Abdi, Banihashem, Hajiaghayi and Mittal. Corollary 4.1 differs in its information pattern: after the observed prefix, the suffix may depend on the weights and on every coin of the rule.

5. Exercises

5.1. Verify the arithmetic \(\frac{t\gamma}{32\kappa B}=2^{-293}\) and the inequality \(2^{-23}+2^{-40}+2^{-31}<2^{-21}\).

5.2. Show that \(\sum_{i<\ell}B^i=B^\ell/(B-1)\), the sum running over all integers \(i<\ell\), and deduce the second bound before (2.2).

5.3. In Lemma 1.1, why must the witness sets \(W_b\) be chosen before the test bits on \(U_i\) are drawn?

5.4. Compute \(p_{\mathrm{main}}\) and check that the seven nonzero triples have conditional probabilities summing to one.

5.5. In Corollary 4.1, why is it essential that \(K\) is drawn independently of \(\sigma\) and before any arrival?

6. Solutions

5.1. \(t\gamma/(32\kappa B)\) is \(2^{-140}\cdot2^{-16}\cdot2^{-5}\cdot2^{-100}\cdot2^{-32}=2^{-293}\). And \(2^{-23}+2^{-40}+2^{-31}<2^{-23}+2^{-23}\), which is \(2^{-22}<2^{-21}\).

5.2. The geometric series \(\sum_{j\geq1}B^{\ell-j}=B^\ell\cdot\frac{1/B}{1-1/B}=\frac{B^\ell}{B-1}\). Exchanging the sums, \(\sum_iB^i\sum_{\ell>i}n_\ell=\sum_\ell n_\ell\sum_{i<\ell}B^i\), restricted to analysed \(i\), which only lowers it.

5.3. The estimate \(\mathbb E|W_b\cap T|=t|W_b|\) needs \(W_b\) to be fixed when the bits are drawn. A set chosen after seeing \(T\), for instance \(T\cap S_{h,b}\) itself, would not be thinned at rate \(t\).

5.4. A label avoids \(H\), \(D\), \(C\) with probability \(\frac12\cdot\frac34\cdot(1-t)\), so \(p_{\mathrm{main}}=1-\frac38(1-t)=\frac58+\frac38t\). The seven nonzero triples have original probabilities summing to \(p_{\mathrm{main}}\); dividing each by \(p_{\mathrm{main}}\) gives a probability distribution.

5.5. The prefix set must have the law of the sacrificed set, which is chosen from the seed before any weight is seen. If \(K\) depended on the arrivals or on observed weights, the prefix set would depend on \(w\), and the rebuilt seed would no longer have its original law, so Proposition 4.1 of the first lesson could not be applied.

References