is_forward_biased_optimal
A distribution μ is an optimal solution to the forward-biased linear program if μ is a dominating distribution supported on cache C and maximizes the mass μ e on the target page e among all dominating distributions on C.
Statement
def is_forward_biased_optimal {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop
- Defined in
- arXiv:2610.40824 Definition 6, eq. (5)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- is_dominating_distributionA probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every…
- Used by 4
- forward_biased_selector_output_uniqueFor any cache C, hitting probabilities α, and target page e, if μ₁ and μ₂ both satisfy is_forward_biased_selector_output C α e, then μ₁ =…
- is_forward_biased_selector_outputA distribution μ is the forward-biased selector output for cache C, hitting probabilities α, and target page e if μ is an optimal solution…
- forward_biased_selector_output_is_dominatingThe forward-biased selector output μ is always a dominating distribution.
- forward_biased_selector_dominating_and_computableOn every Markov paging instance with n pages, cache C, fault on page s, and hitting probabilities α, assuming the dominating distribution…
Read back from the Lean
For a fixed natural number $n$, a subset $C \subseteq \text{Fin } n$, a function $\alpha : \text{Fin } n \to \text{Fin } n \to \mathbb{R}$, a designated element $e \in \text{Fin } n$, and a function $\mu : \text{Fin } n \to \mathbb{R}$, is_forward_biased_optimal C α e μ asserts that:
1. $\mu$ is a dominating distribution with respect to $C$ and $\alpha$ (is_dominating_distribution C α μ); and
2. For every $\nu : \text{Fin } n \to \mathbb{R}$, if $\nu$ is also a dominating distribution with respect to $C$ and $\alpha$, then $\nu(e) \le \mu(e)$ (that is, $\mu$ maximizes the value at $e$ among all dominating distributions).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A dominating distribution μ maximizing μ(e). -/ def is_forward_biased_optimal {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop := is_dominating_distribution C α μ ∧ ∀ ν, is_dominating_distribution C α ν → ν e ≤ μ e