§7.1.2, (7.9)–(7.10) — rates and integrated continuous cost
ProvedCompetitiveOnlinePD.WeightedCaching.continuous_growthLet be a finite universe of unit-size pages, let be an integer, and let be arbitrary real costs. A finite request list has no prescribed horizon or restriction on repetitions or on relative to . All states below are computed by the shared prefix algorithm. Write for its interval slack, for its unscaled dual objective, and .
At each smooth strictly unsatisfied clock , let and let be the saturated pages. With , the full rate chain is
The statement also gives , on , and on . Since has unit rate, its clock derivative is the derivative with respect to in the display. Differentiability itself is concluded from the explicit clock formulas; no regularity assumption on histories or runs is added.
At the endpoint of every finite execution, including all events,
These are the integrated conclusion on printed p.158 and the exact cost decomposition; no extra factor of is applied to the unscaled .
Differences from the source:
- encoding: finite unit-page universes and arbitrary request prefixes → a finite page type, finite lists and one-based natural indices restricted to valid requests and occurrence intervals; reason: every finite prefix is included, also the empty list; no final horizon or future request is an input to a transition
- encoding: the next request time in the interval sums → the absent next occurrence is T+1 solely as a summation sentinel; reason: last intervals include all intervening requests through T; the sentinel is never a request
- reading: the boxed parenthetical r(p_t,t) < t′ < r(p_t,t)+1 → updates between occurrence request times t(p,j)+1 and t(p,j+1)-1; reason: the consecutive counters admit no integer update time; printed p.152 specifies the intended lifetime
- encoding: continuous updates until capacity is satisfied → an exact real scalar flow with simultaneous events, first-stop infimum and left/right activation states; reason: this gives the stated zero, jump, exponential and saturation rules without discretization; completion is a conclusion
- reading: no visible operator between the two printed dual-objective sums → the second sum is subtracted; reason: equation (7.8), the dual constraints and the dual-profit derivatives fix the minus sign
- encoding: inconsistent dummy page letters i,p and an overloaded time t → bound page variables and distinct horizon and row times; reason: the capacity rows and (7.6) bind the intended variables without changing any instance
- encoding: rates during continuous growth in (7.9)–(7.10) → classical derivatives at smooth live clocks excluding exactly activation and saturation events; reason: the source has jumps and event boundaries; the integrated conclusion still covers the whole execution and every endpoint
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators
theorem continuous_growth
{P : Type} [Fintype P] [DecidableEq P]
(k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
(H : List P) :
(∀ (h : List P) (p : P) (τ : ℝ), smoothLive k c h p τ →
let F := fun u => clock false k c h p (run k c h) u
let h' := h ++ [p]
let G := growing k h' (F τ)
let B' := saturated h' (F τ)
HasDerivAt (fun u => continuousCost k c h' (F u))
(∑ q ∈ G, c q * deriv (fun u => (F u).x q (h'.count q)) τ *
deriv (fun u => (F u).y h'.length) τ) τ ∧
(∑ q ∈ G, c q * deriv (fun u => (F u).x q (h'.count q)) τ *
deriv (fun u => (F u).y h'.length) τ) =
∑ q ∈ G, (F τ).x q (h'.count q) ∧
(∑ q ∈ G, (F τ).x q (h'.count q)) ≤
required k h' - ∑ q ∈ B', (1 : ℝ) ∧
required k h' - (∑ q ∈ B', (1 : ℝ)) =
required k h' * deriv (fun u => (F u).y h'.length) τ -
∑ q ∈ B', deriv (fun u => (F u).z q (h'.count q)) τ ∧
HasDerivAt (fun u => (F u).y h'.length) 1 τ ∧
(∀ q ∈ G, HasDerivAt (fun u => (F u).x q (h'.count q))
((F τ).x q (h'.count q) / c q) τ) ∧
(∀ q ∈ B', HasDerivAt (fun u => (F u).z q (h'.count q)) 1 τ) ∧
HasDerivAt (fun u => dualValue k h' (F u))
(required k h' * deriv (fun u => (F u).y h'.length) τ -
∑ q ∈ B', deriv (fun u => (F u).z q (h'.count q)) τ) τ) ∧
(let s := run k c H
continuousCost k c H s ≤ dualValue k H s ∧
thresholdCost k c H s + continuousCost k c H s = cost c H s.x) := by sorry
end CompetitiveOnlinePD.WeightedCaching