ComparisonAlgorithm
structure
A comparison algorithm on n objects with comparison budget c specifies, for each linear order on Fin n, an output probability distribution on Fin n.
Statement
structure ComparisonAlgorithm (n : ℕ) (budget : ℕ)- Defined in
- arXiv:2610.34762 Section 2
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 2
- subset_transfer_two_comparisonsSuppose an algorithm on k objects succeeds in minimum selection with probability at least p on every strict order and uses at most two…
- comparison_algorithm_success_probThe probability that a comparison algorithm A on n objects selects the minimum element under linear order L.
Read back from the Lean
A structure parameterized by natural numbers n and budget, consisting of:
1. A function prob : LinearOrder (Fin n) → Fin n → ℝ assigning a real number to each linear order L on Fin n and each index i : Fin n;
2. A proof nonneg that for every linear order L on Fin n and every i : Fin n, 0 ≤ prob L i;
3. A proof total that for every linear order L on Fin n, the sum over all i : Fin n of prob L i is equal to 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
/-- A comparison algorithm on `n` objects with comparison budget `budget`. -/ structure ComparisonAlgorithm (n : ℕ) (budget : ℕ) where prob : LinearOrder (Fin n) → Fin n → ℝ nonneg : ∀ L i, 0 ≤ prob L i total : ∀ L, ∑ i : Fin n, prob L i = 1