bpe_deviation_prob_nonneg
For any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability bpe_deviation_prob p hp k N c ε is ≥ 0.
Statement
theorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε- Source
- step towards op_1533_iid_binary_greedy_bpe_universal_rate
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- bpe_deviation_probGiven parameters (p : ℝ), hypothesis (hp : 0 < p ∧ p < 1), (k N : ℕ), and (c ε : ℝ), bpe_deviation_prob p hp k N c ε is the real number…
- boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval
unitInterval(the closed interval $[0, 1]$),… - bpe_greedy_runThe relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there…
- binaryEntropyThe binary entropy function \[ H(x) \;=\; -x\log_2 x - (1-x)\log_2(1-x), \] using the base-$2$ logarithm, with the convention…
- weighted_max_cut_linear_combinationFor all real numbers W and M, the convex combination of (3/4)W + (3/16)M and W - M with weights 16/19 and 3/19 equals (15/19)W.
The proof, explained
The deviation probability `bpe_deviation_prob` is defined as the real value (`toReal`) of an extended non-negative real measure (`ENNReal`). Unfolding its definition reduces the goal to showing that the real cast of a measure is non-negative, which holds identically for all `ENNReal` values and is solved by simplification.
0 ≤ bpe_deviation_prob p hp k N c ε automation
Unfolding the definition of `bpe_deviation_prob`, the deviation probability is defined as `(μ s).toReal`, the conversion to `ℝ` of the measure of an event under the Bernoulli product measure. Because extended non-negative reals (`ENNReal`) always have non-negative real parts (`0 ≤ x.toReal`), the simplifier simplifies the inequality to `True`, closing the goal.
uses
bpe_deviation_prob,weighted_max_cut_linear_combinationtheorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε := by first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination | (simp only [bpe_deviation_prob] at *; first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination)
bpe_deviation_prob- The definition of the deviation probability, given as the real value (`.toReal`) of the Bernoulli product measure of the set of bit strings where greedy BPE compression deviates by more than ε from c.
weighted_max_cut_linear_combination- An algebraic identity relating weighted linear combinations of cut values: (16 / 19) * ((3 / 4) * W + (3 / 16) * M) + (3 / 19) * (W - M) = (15 / 19) * W (an unused artifact here).
- The proof is written as an automated trial-and-error tactic script (`first | ...`). The lemma `weighted_max_cut_linear_combination` comes from an unrelated theorem about Max-Cut and is entirely unused; `simpa` discharges the goal by simplifying `0 ≤ x.toReal` to `True` via `ENNReal.toReal_nonneg`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- The greedy BPE deviation probability is non-negative. -/theorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε := by first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination | (simp only [bpe_deviation_prob] at *; first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination)