uniform_kserver_step_dist
For a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, a normalized finitely supported configuration distribution μ : (∀ i, M i) →₀ ℝ, and a current configuration x, uniform_kserver_step_dist k r μ x is the finitely supported transition distribution of type (∀ i, M i) →₀ ℝ: if x serves r it returns Finsupp.single x 1; otherwise it returns the sum over all i : Fin k of Finsupp.single (Function.update x i (r i)) (1 / (2 * k)), plus (1 / 2 : ℝ) • μ.
Statement
noncomputable def uniform_kserver_step_dist (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (r : ∀ i, M i) (μ : (∀ i, M i) →₀ ℝ) (x : ∀ i, M i) : (∀ i, M i) →₀ ℝ
- Defined in
- arXiv:2610.37192 Section 3.2
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- uniform_kserver_servesFor a natural number k, a family of uniform metric spaces M indexed by Fin k, and configurations x, r in the product space over Fin k, x…
- Used by 1
- uniform_kserver_step_expected_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, a previous finitely supported…
Read back from the Lean
A definition of a finitely supported real-valued function (transition distribution) on the product type ∏ i : Fin k, M i. Given a natural number k, a family of types M indexed by Fin k with decidable equality, a target/request vector r : ∀ i, M i, a background distribution μ : (∀ i, M i) →₀ ℝ, and a current configuration x : ∀ i, M i: if uniform_kserver_serves x r holds (i.e., some coordinate of x matches the corresponding coordinate of r), the result is the Dirac mass Finsupp.single x 1; otherwise, it is the sum over i : Fin k of Finsupp.single (Function.update x i (r i)) (1 / (2 * k)) plus (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
/-- Step transition distribution of the randomized online algorithm. -/ noncomputable def uniform_kserver_step_dist (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (r : ∀ i, M i) (μ : (∀ i, M i) →₀ ℝ) (x : ∀ i, M i) : (∀ i, M i) →₀ ℝ := by classical exact if uniform_kserver_serves x r then Finsupp.single x 1 else (∑ i : Fin k, Finsupp.single (Function.update x i (r i)) (1 / (2 * (k : ℝ)))) + (1 / 2 : ℝ) • μ