is_forward_biased_selector_output
A distribution μ is the forward-biased selector output for cache C, hitting probabilities α, and target page e if μ is an optimal solution to the forward-biased linear program and every other optimal solution ν is strictly smaller than μ in lexicographical order Pi.Lex (· < ·) (· < ·).
Statement
def is_forward_biased_selector_output {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop
- Defined in
- arXiv:2610.40824 Definition 6
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 2
- is_dominating_distributionA probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every…
- is_forward_biased_optimalA distribution μ is an optimal solution to the forward-biased linear program if μ is a dominating distribution supported on cache C and…
- Used by 3
- 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 μ₁ =…
- 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 given natural number $n$, a subset $C \subseteq \mathrm{Fin}\ n$, a payoff/weight function $\alpha : \mathrm{Fin}\ n \to \mathrm{Fin}\ n \to \mathbb{R}$, an element $e \in \mathrm{Fin}\ n$, and a distribution $\mu : \mathrm{Fin}\ n \to \mathbb{R}$, is_forward_biased_selector_output C α e μ asserts that:
1. $\mu$ is forward-biased optimal with respect to $C, \alpha, e$.
2. For every $\nu : \mathrm{Fin}\ n \to \mathbb{R}$, if $\nu$ is forward-biased optimal with respect to $C, \alpha, e$, then either $\nu = \mu$ or $\nu$ is strictly lexicographically smaller than $\mu$ (under the standard strict ordering on indices $\mathrm{Fin}\ n$ and real numbers $\mathbb{R}$).
In other words, $\mu$ is the lexicographically maximal forward-biased optimal distribution.
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
/-- The lexicographically largest optimal solution to the forward-biased LP. -/ def is_forward_biased_selector_output {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (e : Fin n) (μ : Fin n → ℝ) : Prop := is_forward_biased_optimal C α e μ ∧ ∀ ν, is_forward_biased_optimal C α e ν → (ν = μ ∨ Pi.Lex (· < ·) (· < ·) ν μ)