AFTD Auto-Formalizing Theoretical Domains

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)
See it in the graphDiscuss this resultChallenge it