is_dominating_distribution
A probability distribution μ on Fin n supported on cache C is dominating with respect to pairwise hitting probabilities α if for every resident page q in C, the expected probability that a page drawn from μ is requested before q is at most 1/2.
Statement
def is_dominating_distribution {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (μ : Fin n → ℝ) : Prop
- Defined in
- arXiv:2610.40824 Definition 6, eq. (2)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 4
- 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…
- 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
Given a natural number $n$, a subset $C \subseteq \mathrm{Fin}(n)$, a function $\alpha : \mathrm{Fin}(n) \to \mathrm{Fin}(n) \to \mathbb{R}$, and a function $\mu : \mathrm{Fin}(n) \to \mathbb{R}$, is_dominating_distribution C α μ asserts that:
1. For every $p \in \mathrm{Fin}(n)$, $\mu(p) \ge 0$;
2. The sum of $\mu(p)$ over all $p \in \mathrm{Fin}(n)$ is equal to $1$;
3. For every $p \in \mathrm{Fin}(n)$, if $p \notin C$, then $\mu(p) = 0$ (so $\mu$ is supported on $C$);
4. For every $q \in C$, the sum $\sum_{p \in C} \mu(p) \cdot \alpha(p, q) \le \frac{1}{2}$.
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 distribution μ supported on C is dominating if ∑_{p ∈ C} μ(p) α(p, q) ≤ 1/2 for all q ∈ C. -/ def is_dominating_distribution {n : ℕ} (C : Finset (Fin n)) (α : Fin n → Fin n → ℝ) (μ : Fin n → ℝ) : Prop := (∀ p, 0 ≤ μ p) ∧ (∑ p, μ p = 1) ∧ (∀ p, p ∉ C → μ p = 0) ∧ (∀ q ∈ C, ∑ p ∈ C, μ p * α p q ≤ 1 / 2)