two_deletion_posterior_sum_two
For every received binary word w of length 2, the posterior distribution two_deletion_posterior 2 w over words of length 4 sums to 1.
Statement
theorem two_deletion_posterior_sum_two (w : Fin 2 → Bool) : ∑ y : Fin 4 → Bool, two_deletion_posterior 2 w y = 1- Source
- arXiv:2611.01064, Lemma 2.1
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- two_deletion_posteriorFor a received binary word w of length n, two_deletion_posterior n w y is the posterior probability of transmitting y of length n + 2…
- two_deletion_num_embeddingsFor a binary word w of length n and y of length n + 2, two_deletion_num_embeddings n w y is the number of strictly increasing index…
Read back from the Lean
For every boolean sequence $w : \mathrm{Fin}\ 2 \to \mathrm{Bool}$, the sum over all boolean sequences $y : \mathrm{Fin}\ 4 \to \mathrm{Bool}$ of $\mathrm{two\_deletion\_posterior}(2, w, y)$ is equal to $1$ (in $\mathbb{R}$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof evaluates the posterior sum directly using finite verification and algebraic simplification. By definition, the two-deletion posterior probability of a transmitted word y given a received word w is the number of subsequence embeddings of w into y divided by 4 * Nat.choose 4 2 = 24. Exhaustive finite computation shows that the total number of embeddings of w across all 16 possible 4-bit words y is 24, so factoring the denominator out of the sum yields 24 / 24 = 1.
For the given 2-bit word w, the total number of embeddings across all 16 candidate 4-bit words y is 24: ∑ y, two_deletion_num_embeddings 2 w y = 24. automation
Because the types Fin 2 → Bool and Fin 4 → Bool are finite, Lean can verify by exhaustive evaluation (via `decide`) that for every 2-bit word, the sum of embedding counts over all 16 possible 4-bit transmitted words is exactly 24. Specializing this universal statement to the given word w yields the equation hw.
have h : ∀ w : Fin 2 → Bool, ∑ y : Fin 4 → Bool, two_deletion_num_embeddings 2 w y = 24 := by decide have hw := h w
The posterior sum is rewritten as ∑ y, (two_deletion_num_embeddings 2 w y : ℝ) / 24 = 1.
Unfolding the definition of two_deletion_posterior, the posterior probability of y given w is its embedding count divided by 4 * Nat.choose 4 2. Since Nat.choose 4 2 = 6, the denominator 4 * 6 simplifies to 24 by numerical normalization.
uses
two_deletion_posteriorsimp only [two_deletion_posterior] rw [show Nat.choose 4 2 = 6 from by decide] norm_num
The sum of the posterior probabilities evaluates to 1.
Factoring the division by 24 out of the finite sum using Finset.sum_div and moving the real coercion outside the sum using Nat.cast_sum, the left-hand side becomes (↑∑ y, two_deletion_num_embeddings 2 w y) / 24. Rewriting with hw replaces the sum with 24, leaving 24 / 24 = 1, which holds by arithmetic.
uses
Finset.sum_div,Nat.cast_sumrw [← Finset.sum_div] rw [← Nat.cast_sum] rw [hw] norm_num
two_deletion_posterior- the posterior probability of transmitted word y given received word w after two deletions, defined as the number of embeddings divided by 4 * Nat.choose (n + 2) 2
Finset.sum_div- a constant divisor can be factored out of a finite sum: (∑ i ∈ s, f i) / a = ∑ i ∈ s, (f i / a)
Nat.cast_sum- coercing a sum of natural numbers to a semiring equals the sum of the coerced terms: ↑(∑ x ∈ s, f x) = ∑ x ∈ s, ↑(f x)
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.
/-- For any received binary word of length 2, the two-deletion posterior distribution sums to 1. -/theorem two_deletion_posterior_sum_two (w : Fin 2 → Bool) : ∑ y : Fin 4 → Bool, two_deletion_posterior 2 w y = 1 := by -- Double counting / direct evaluation: for every w the total number of -- embeddings over all transmitted words y is 4 * (4 choose 2) = 24. have h : ∀ w : Fin 2 → Bool, ∑ y : Fin 4 → Bool, two_deletion_num_embeddings 2 w y = 24 := by decide have hw := h w simp only [two_deletion_posterior] rw [show Nat.choose 4 2 = 6 from by decide] norm_num rw [← Finset.sum_div] rw [← Nat.cast_sum] rw [hw] norm_num