Theorem 2 — Optimal segmentation and oracle computation
ProvedFBMSP.theorem2_computing_segmentationLet predicted values be nonnegative, with positive weights summing to one. Let the independent common error have a finite first moment, mean zero, and MHR. For each index block , an oracle supplies a nonnegative price attaining the block's maximum revenue. Its declared charge includes both the price and attained revenue, and is bounded by on every nonempty block.
For every , there exist ordered cuts covering all types and a monotone assignment realizing those cuts, such that the oracle prices yield exactly the Bellman value and dominate every assignment to arbitrary nonnegative real prices. The specified bottom-up schedule, including precomputation and backtracking, satisfies
Formalization note. Empty blocks represent unused price slots. The last endpoint is , so no type is omitted. This is an explicit oracle-operation cost model for sorted inputs, not a claim about the naive recursive evaluation or bit complexity of a continuous price oracle. The source's intended price-and-value oracle contract is made explicit.
import Definitions.Def_FBMSP_Model import Definitions.Def_FBMSP_DynamicProgram
namespace FBMSP
theorem theorem2_computing_segmentation
{n k : ℕ} (hk : 1 ≤ k) (η : MeasureTheory.Measure ℝ)
(hη : ValidNoise η) (hMHR : HasMHR η)
(μ w : Fin n → ℝ) (hMarket : ValidFiniteMarket μ w)
(o : ℕ → ℕ → ℝ) (ho : BlockOracle η μ w o)
(charge : ℕ → ℕ → ℕ) (m : ℕ) (hm : 1 ≤ m)
(hCost : ∀ a b, a < b → b ≤ n → charge a b ≤ m) :
∃ (c : Fin (k + 1) → ℕ) (a : Fin n → Fin k),
ValidCuts n k c ∧ RealizesCuts a c ∧ Monotone a ∧
finitePolicyRevenue η μ w a
(fun j => o (c j.castSucc) (c j.succ)) =
intervalDP (oracleScore η μ w o) (k - 1) 0 n ∧
(∀ (a' : Fin n → Fin k) (p' : Fin k → ℝ),
(∀ j, 0 ≤ p' j) →
finitePolicyRevenue η μ w a' p' ≤
finitePolicyRevenue η μ w a
(fun j => o (c j.castSucc) (c j.succ))) ∧
segmentationWork charge k n ≤ 5 * (n * n) * (k + m) := by sorry
end FBMSPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For all natural with , let be a probability measure on with integrable identity function and , and write . Assume also that is absolutely continuous with respect to Lebesgue measure and that is convex and is concave on , meaning for and ; zero survival values outside are allowed. Let real arrays satisfy , whenever , all , all , and . For natural endpoints and real , put . Let satisfy, for every , and for every nonnegative real , and set . Let be any charge function and any natural number such that for every . Define and . There exist natural cuts and an assignment such that for every , the assignment is nondecreasing in , and with one has . Moreover, for every assignment into these slots and every real price vector with all , . The same existential conclusion includes . This left side is the defined segmentation-work expression; the hypotheses bound the supplied charges but state no further relation between the charge function and the evaluation of . Since , natural subtraction has its usual integer value and the recurrence uses blocks. Repeated cuts and empty blocks are allowed, including when ; empty block revenue is . The case is excluded by the market hypotheses, the oracle is unconstrained outside , diagonal and out-of-range charges are unbounded but unused by the work expression, and no condition is imposed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.