cycle_greedy_mean
def
The rational expected assignment cost cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1 under greedy online assignment on a cycle of circumference n.
Statement
def cycle_greedy_mean (n : ℕ) : ℚ- Defined in
- arXiv:2610.15776, Section 3 and Theorem 9
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Built on 1
- cycle_greedy_momentsThe function
cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚdefined ascycle_greedy_moments_fuel g.length n g.
- cycle_greedy_momentsThe function
Read back from the Lean
The definition cycle_greedy_mean takes a natural number n and returns the first component (the mean) of cycle_greedy_moments n (List.replicate n 1), representing the first moment of a greedy process on a cycle initialized with n gaps of size 1.
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
/-- Expected total assignment cost of the greedy online algorithm on a cycle of circumference n. -/ def cycle_greedy_mean (n : ℕ) : ℚ := (cycle_greedy_moments n (List.replicate n 1)).1