iid_greedy_bpe_approx_prob
Given alphabet size q, weights p : Fin q → ℝ, merge budget k, length N, and tolerance ε : ℝ, iid_greedy_bpe_approx_prob q p k N ε is the real probability under iid_word_measure q N p of the event that a word w : Fin N → Fin q has bpe_min_greedy_utility (List.ofFn (fun i => (w i : ℕ))) k ≥ (iid_bpe_sharp_factor - ε) * bpe_optimal_full_utility (List.ofFn (fun i => (w i : ℕ))) k.
Statement
noncomputable def iid_greedy_bpe_approx_prob (q : ℕ) (p : Fin q → ℝ) (k N : ℕ) (ε : ℝ) : ℝ
- Related work
- folklore
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 4
- iid_word_measureGiven natural numbers q and N, and real weights p : Fin q → ℝ, iid_word_measure q N p is the product measure on words Fin N → Fin q…
- bpe_min_greedy_utilityThe minimum total reduction in string length achieved by any k-step greedy Byte-Pair Encoding merge run on s under arbitrary tie-breaking.
- bpe_optimal_full_utilityThe maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.
- iid_bpe_sharp_factorThe conjectured sharp uniform i.i.d. greedy Byte-Pair Encoding merge factor c = (2 + √2) / 4.
- Used by 1
- op_1604_iid_greedy_bpe_budget_oneOpen Problem OP-1604 (budget k = 1 case): For a merge budget of k = 1, every alphabet size q ≥ 2, every strictly positive probability…
Read back from the Lean
iid_greedy_bpe_approx_prob q p k N ε is a definition (not a theorem) that evaluates to a real number. Given an alphabet size q : ℕ, a symbol weight function p : Fin q → ℝ, a step count k : ℕ, a word length N : ℕ, and a tolerance ε : ℝ, it defines the measure (cast to ℝ) of the set of length-N words w : Fin N → Fin q satisfying:
(bpe_min_greedy_utility w k : ℝ) ≥ (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility w k : ℝ)
under the product measure on Fin N → Fin q where each coordinate is independently drawn from the discrete measure $\sum_{i : \text{Fin } q} \operatorname{ofReal}(p(i)) \cdot \delta_i$.
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
/-- Probability that length-N i.i.d. string achieves greedy k-merge utility at least (c - ε) times optimal full-merge utility. -/ noncomputable def iid_greedy_bpe_approx_prob (q : ℕ) (p : Fin q → ℝ) (k N : ℕ) (ε : ℝ) : ℝ := ((iid_word_measure q N p) {w : Fin N → Fin q | (bpe_min_greedy_utility (List.ofFn fun i => (w i : ℕ)) k : ℝ) ≥ (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) k : ℝ)}).toReal