comparison_algorithm_success_prob
def
The probability that a comparison algorithm A on n objects selects the minimum element under linear order L.
Statement
def comparison_algorithm_success_prob {n : ℕ} {c : ℕ} (hn : 0 < n)
(A : ComparisonAlgorithm n c) (L : LinearOrder (Fin n)) : ℝ- Defined in
- arXiv:2610.34762 Section 2 (equation 2)
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Built on 2
- ComparisonAlgorithmA comparison algorithm on n objects with comparison budget c specifies, for each linear order on Fin n, an output probability distribution…
- linearOrderMinThe minimum element of Fin n with respect to a linear order L, for n > 0.
- Used by 1
- 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…
Read back from the Lean
Given natural numbers n and c, a proof hn : 0 < n, a ComparisonAlgorithm n c object A, and a linear order L on Fin n, comparison_algorithm_success_prob defines the real number obtained by evaluating A.prob L at the minimum element of Fin n under L (as computed by linearOrderMin hn L).
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 probability that comparison algorithm `A` selects the minimum element under linear order `L`. -/ def comparison_algorithm_success_prob {n : ℕ} {c : ℕ} (hn : 0 < n) (A : ComparisonAlgorithm n c) (L : LinearOrder (Fin n)) : ℝ := A.prob L (linearOrderMin hn L)