(26), p. 59 — the joint no-click/click term is at most the marginal benefit of π∗'s r-th product placed after [π̃]ᵣ₋₁
ProvedRankAssort.SimpleLearn.eq_26Let types be drawn from with a measurable type map, let and be rankings of the products, fix a rank and let . Then
where is the prefix of the first products of followed by at rank . When already appears among the first products of , both sides are (footnote 17).
This is the argument of Lemma 1 applied to the learned ranking ; combined with (23) it bounds each term of (25) by the corresponding term of (6) plus .
Formalization Note Ranks are 0-based in Lean: the paper's rank is index , a ranking is a duplicate-free list of the products (Fin n), and is the list entry at index . The left side is jointTerm D τ piT piStar r, the right side firstClickTerm D τ (piT.take r ++ [iStar]) r with 0-based ; both are computed under the coupled first-click law. The statement holds for every ranking , not only for the output of Algorithm 2.
Differences from the source:
- generalization: π̃ the ranking returned by Algorithm 2 satisfying (24), π∗ the optimal ranking → π̃ and π∗ any two rankings; reason: the argument uses neither property; the paper's pair is one instance
- encoding: i∗ = π∗⁻¹(r) → iStar with piStar[r]? = some iStar (0-based r); reason: the same product
- encoding: the C̄(r − 1, ·) C(·) expectations of the paper, on the customer's click realisation → computed under the coupled first-click law (one Bernoulli(pᵢ) like-coin per product, p. 53); reason: the paper evaluates these terms through this coupling (proof of Lemma 1, p. 53); milestone first_click_identity ties the coupled law to the sequential click law with bias
- encoding: expectation over the type (p, f, k) ∼ D, a random variable → integral over θ ∼ D of a function of τ θ, with TypeMeasurable τ (every coordinate of the type map measurable); reason: the expectations are undefined otherwise (Lean would return the junk value 0); the integrands lie in [0, 1], so measurability is all that is needed
- encoding: ranks 1..n, a ranking is a permutation π of [n], π⁻¹(j) the product at rank j → 0-based indices, a ranking is a duplicate-free List (Fin n) of length n, π⁻¹(j) is the entry at index j − 1; reason: Lean convention; the same rankings
import Mathlib import Definitions.Def_RankAssort_SimpleLearn_Model
namespace RankAssort.SimpleLearn
open MeasureTheory
theorem eq_26 {n : ℕ} {Θ : Type*} [MeasurableSpace Θ] (D : Measure Θ) [IsProbabilityMeasure D]
(τ : Θ → CustomerType n) (hτ : TypeMeasurable τ)
(piT piStar : List (Fin n)) (hT : piT.Nodup) (hTlen : piT.length = n)
(hs : piStar.Nodup) (hslen : piStar.length = n)
(r : ℕ) (hr : r < n) (iStar : Fin n) (hiStar : piStar[r]? = some iStar) :
jointTerm D τ piT piStar r ≤ firstClickTerm D τ (piT.take r ++ [iStar]) r := by sorry
end RankAssort.SimpleLearn
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.