Theorem D.9 — paid overlay
OpenCausalFailureRank.Supplement.theorem_D_9algorithmic-complexitylaminar-familyonline-allocationp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
In the cap-relaxed rational homogeneous shared-pool model, fix . For every finite-cost free-correction policy , there exists a current-payment policy with no larger failure probability and
Consequently,
The simulator retains current payment: every genuine correction is physically executed and charged before advance, including on paths that later fail. This is only a cap-relaxed comparison and makes no native stopping-time claim.
Differences from the source:
- encoding: expected costs and values that may be infinite → lower integrals and infima in ; reason: the finite-cost hypothesis is stated as inequality with , and extended nonnegative values preserve all nonnegative charges without defaulting
Preamble
import Mathlib import Definitions.Def_CausalFailureRank_Supplement_paidModel set_option autoImplicit false
Formal statement
namespace CausalFailureRank
namespace Supplement
/-- **Theorem D.9 (Paid overlay).** Zang, Li, Jin, Xu, *Causal Failure Rank Determines
Statistical Depth*, preprint (STOC 2027 submission, version of 2026-11-03, sha256 721c8b0d…),
Theorem D.9, pp.29–30 (PDF pp.30–31), equations (41)–(42).
Every finite-cost cap-relaxed free-correction policy has a cap-relaxed current-payment overlay
with no larger failure probability and the stated additive review-and-fee bound. Consequently the
paid relaxed value is at most the free relaxed value plus `9 D_f`.
**Formalization Note.** This theorem deliberately uses `relaxedCaps`; it makes no native stopping-
time claim. The free and paid instances have identical facts, channels, compatibilities, review
prices, and normal-call accounting and differ only in their correction fee. `expectedObsBill`
counts reviews alone, and the produced policy uses the base model's genuine `currentPay` execution,
so corrections on paths that later fail are still physically executed and charged. -/
theorem theorem_D_9 {N K : ℕ} (M : PaidModel N K) (δ : ℚ)
(hδ : 0 < δ) (hδmax : δ ≤ 1 / 64) :
(∀ π₀ : Policy (freeInstance M),
expBill (freeInstance M) .currentPay (relaxedCaps N) π₀ ≠ ⊤ →
∃ πf : Policy M.I,
failProb M.I .currentPay (relaxedCaps N) πf ≤
failProb (freeInstance M) .currentPay (relaxedCaps N) π₀ ∧
expBill M.I .currentPay (relaxedCaps N) πf ≤
expectedObsBill (freeInstance M) (relaxedCaps N) π₀ +
ENNReal.ofReal ((17 / 2 : ℝ) * N * scaleA M *
Real.log (1 + M.fee / scaleA M))) ∧
relaxedValue M δ ≤ relaxedFreeValue M δ + 9 * feeScale M := by sorry
end Supplement
end CausalFailureRank
Source
Zang, Li, Jin, Xu, Causal Failure Rank Determines Statistical Depth, preprint (STOC 2027 submission, version of 2026-11-03, sha256 721c8b0d…), Theorem D.9, pp.29–30 (PDF pp.30–31), eqs. (41)–(42)