Theorem 3.1 — optimal retry priority under a prefix probability bound
OpenCorrelatedLocalSearch.Supplement.theorem_3_1local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
For , always attempting an unfinished task with smallest minimizes the worst probability of simultaneously for every and . For sorted weights, the displayed recursion has exact optimum and uses arithmetic and memory. Every valid selector has the same stopping-time law under and the same two powered prefix sums and at every depth and exponent.
Differences from the source:
- encoding: arithmetic-operation and memory bounds in big-O notation → the explicit in-place row evaluation of the displayed recurrence uses at most arithmetic operations and cells; reason: an explicit costed evaluation witnesses the stated asymptotics
- encoding: worst probabilities written as nonnegative real quantities →
ENNReal; reason: exact nonnegative encoding
Preamble
import Mathlib import Definitions.Def_CorrelatedLocalSearch_Supplement_RetryTasks set_option autoImplicit false
Formal statement
namespace CorrelatedLocalSearch.Supplement
open MeasureTheory
open scoped ENNReal BigOperators
/-- Xu, arXiv:2607.17469 (sha256 17e00d69…), Theorem 3.1, p.7 (PDF p.9).
The smallest powered success-set weight first is simultaneously minimax at every deadline and
slack; the displayed suffix recursion is exact; its arithmetic cost is linear in `nT`; and every
selector has the same independent stopping law and every powered single-depth sum. -/
theorem theorem_3_1 {A : Type*} [Fintype A] [DecidableEq A]
[MeasurableSpace A] [MeasurableSingletonClass A]
(hA : 2 ≤ Fintype.card A) (pi : A -> Real) (hpi : ∀ a, 0 < pi a)
(hpisum : (∑ a, pi a) = 1) (n : Nat) (hn : 1 ≤ n)
(M : RetryModel A (Fin n)) (s : Real) (hs0 : 0 < s) (hs1 : s ≤ 1)
(order : List (Fin n)) (horder : order.Nodup)
(hcomplete : ∀ i, i ∈ order)
(hsorted : order.Pairwise (fun i j => taskPowerWeight M pi s i ≤ taskPowerWeight M pi s j)) :
∃ priority : RetrySelector A (Fin n),
IsValidRetrySelector priority ∧ AlwaysChoosesSmallest M pi s priority ∧
(∀ D, 1 ≤ D -> ∀ T,
worstProbability pi s D (retrySurvivalEvent M priority T) =
min 1 (ENNReal.ofReal D * ENNReal.ofReal
(retryValue (totalPowerWeight pi s)
(order.map (taskPowerWeight M pi s)) T 0)) ∧
(∃ nu : Measure (Nat -> A), nu ∈ SourceClass pi s D ∧
nu (retrySurvivalEvent M priority T) =
worstProbability pi s D (retrySurvivalEvent M priority T)) ∧
∀ sel, IsValidRetrySelector sel ->
worstProbability pi s D (retrySurvivalEvent M priority T) ≤
worstProbability pi s D (retrySurvivalEvent M sel T)) ∧
(∀ T, (retryValueTable (totalPowerWeight pi s)
(order.map (taskPowerWeight M pi s)) T).getD 0 0 =
retryValue (totalPowerWeight pi s)
(order.map (taskPowerWeight M pi s)) T 0 ∧
retryArithmeticOperations n T ≤ 4 * n * T) ∧
retryMemoryCells n ≤ n + 1 ∧
∀ sel1 sel2, IsValidRetrySelector sel1 -> IsValidRetrySelector sel2 ->
∀ T, retryReferenceTail M sel1 pi T = retryReferenceTail M sel2 pi T ∧
∀ theta, 0 < theta ->
retryCompletionPrefixPowerSum M sel1 pi T theta =
retryCompletionPrefixPowerSum M sel2 pi T theta ∧
retryPrefixPowerSum M sel1 pi T theta =
retryPrefixPowerSum M sel2 pi T theta := by sorry
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), Theorem 3.1, p.7 (PDF p.9)