App. B, pp. 18–19 — exchange step: evicting a token of strictly smaller ranking score is no worse for the optimal cost-to-go
DisprovedTailOptCaching.ETLRU.exchange_inequalityLet be a natural number and let be a post-decision state with arrived conversations. Let be two conversations with at least one cached token each, and write , for the states obtained from by evicting one token of , respectively of ; assume both are well formed, and that the cache of exceeds the capacity by exactly one token, , so that one token must be evicted. If the ranking scores satisfy
then for every number of remaining arrivals the Bellman optimum satisfies
This is the exchange argument of the proof of Theorem 2: in the paper's notation, , where evicts from the conversation of lowest score.
Formalization Note. The inequality between the scores is strict: with equal scores the two evictions can have different future costs (exact dynamic-programming checks found such pairs), and the paper's "ascending order" does not address ties. The hypothesis is added as for Lemma 1. Well-formedness of the two post-eviction states carries the invariant that every reachable state satisfies. The capacity hypothesis is the page's setting (the exchange is made among the tokens that must be evicted to restore the capacity constraint); it cannot be dropped: with slack capacity the deficit of the evicted token is never pushed out, its future cost is (probability that its conversation returns within the horizon) × (its tail probability), which is not linear in the rate, and an exact computation (C = 5, ξ = 1, λ_conv = 1, rates 1 and 2 with λ̄ = λ, L = X = 1, Q_0 ≡ 1, P(Q_1 = 1) = 11/20, A ≡ 0, decay factor 1, two arrivals) gives although the score of 0 is 1 < 11/10.
import Mathlib import Definitions.Def_TailOptCaching_ETLRU_Model open scoped ENNReal
namespace TailOptCaching.ETLRU
theorem exchange_inequality (P : Params) (hξ : ∃ m : ℕ, P.ξ = m) (r : ℕ) (z : State)
(i j : ℕ) (hi : i < z.n) (hj : j < z.n) (hXi : 1 ≤ z.X i) (hXj : 1 ≤ z.X j)
(hwi : WellFormed P (evict z i)) (hwj : WellFormed P (evict z j))
(hcap : ∑ l ∈ Finset.range z.n, z.X l = P.C + 1)
(hscore : score P z i < score P z j) :
optValue P r (evict z i) ≤ optValue P r (evict z j) := by sorry
end TailOptCaching.ETLRU
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.