sum_rankings_of_nonempty
lemmaverified
For nonempty S, a sum over rankings of S splits as a sum over the top alternative a and the rankings of S minus a.
Statement
lemma sum_rankings_of_nonempty (S : Finset ℕ) (hS : S.Nonempty) (f : List ℕ → ℝ) :
∑ l ∈ rankings_of S, f l = ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), f (a :: t)- Source
- step towards plackett_luce_geometric_entropy_linear (Preference Elicitation as Average-Case Sorting, AAAI 2021, Sec. 5 conjecture (entropy O(m) for every phi in (0,1)))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
- rankings_of_eq_biUnionFor nonempty S, the rankings of S are obtained by choosing a top alternative a in S and then a ranking of S minus a.
- Used by 2
- sum_plackett_luce_probWith positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
- plackett_luce_entropy_eqChain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma sum_rankings_of_nonempty (S : Finset ℕ) (hS : S.Nonempty) (f : List ℕ → ℝ) : ∑ l ∈ rankings_of S, f l = ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), f (a :: t) := by rw [rankings_of_eq_biUnion S hS, Finset.sum_biUnion] · refine Finset.sum_congr rfl fun a _ => ?_ rw [Finset.sum_image] intro x _ y _ h; exact List.cons_injective h · intro a _ b _ hab simp only [Function.onFun] rw [Finset.disjoint_left] intro l h1 h2 simp only [Finset.mem_image] at h1 h2 obtain ⟨t1, -, rfl⟩ := h1 obtain ⟨t2, -, h⟩ := h2 exact hab (List.cons.inj h).1.symm