bpe_deviation_prob
Given parameters (p : ℝ), hypothesis (hp : 0 < p ∧ p < 1), (k N : ℕ), and (c ε : ℝ), bpe_deviation_prob p hp k N c ε is the real number defined as the value in ℝ obtained by taking .toReal of the measure under boolean_product_bernoulli (Fin N) ⟨p, ⟨le_of_lt hp.1, le_of_lt hp.2⟩⟩ of the set of words w : Fin N → Bool for which there exists a list t : List ℕ such that bpe_greedy_run k (List.ofFn (fun i => if w i then 1 else 0)) t and ε < |binaryEntropy p * (N : ℝ) / ((t.length : ℝ) * Real.logb 2 (k + 2)) - c|.
Statement
noncomputable def bpe_deviation_prob (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : ℝ
- Related work
- knowledgebase, OP-1533: iid binary greedy bpe universal log dictionary rate
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 3
- 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…
- boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval
unitInterval(the closed interval $[0, 1]$),…
- Used by 1
- bpe_deviation_prob_nonnegFor any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability…
Read back from the Lean
The declaration bpe_deviation_prob defines a function taking:
- a real number p,
- a proof hp : 0 < p ∧ p < 1,
- natural numbers k (the number of BPE merge steps) and N (the sequence length),
- real numbers c (a target constant) and ε (a tolerance parameter),
and returns the probability (as a real number) under the product Bernoulli measure on Fin N → Bool (where each coordinate is independently true with probability p and false with probability 1 - p) that:
there exists a list of natural numbers t reachable from the initial sequence (List.ofFn (fun i => if w i then 1 else 0)) via k steps of greedy Byte Pair Encoding (BPE), such that
ε < |(binaryEntropy p * N) / (t.length * Real.logb 2 (k + 2)) - c|,
where binaryEntropy p = -p * Real.logb 2 p - (1 - p) * Real.logb 2 (1 - p).
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 a random binary string of length N has a k-step greedy BPE run deviating from rate c by more than ε. -/ noncomputable def bpe_deviation_prob (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : ℝ := let p_unit : unitInterval := ⟨p, ⟨le_of_lt hp.1, le_of_lt hp.2⟩⟩ ((boolean_product_bernoulli (Fin N) p_unit) {w : Fin N → Bool | ∃ t : List ℕ, bpe_greedy_run k (List.ofFn (fun i => if w i then 1 else 0)) t ∧ ε < |binaryEntropy p * (N : ℝ) / ((t.length : ℝ) * Real.logb 2 (k + 2)) - c|}).toReal