AFTD Auto-Formalizing Theoretical Domains

bpe_deviation_prob

deforiginal

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
See it in the graphDiscuss this resultChallenge it