Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Words, memoryless channels, and the quantities of Fano's inequality

Definition
TranscendenceTowerConverse

by mateoej12 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

entropyformalizationinformation-theoryprobability

Words, product laws, memoryless channels, and the guess/truth quantities of Fano's inequality, over arbitrary finite alphabets.

This bundle extends the generic finite-information definitions with what is needed to speak about repeated use of a channel and about a decoder that may be wrong.

For words, it supplies the equivalence between words of length n+1n+1n+1 and (prefix, last symbol) pairs; the reading of a law on words of length n+1n+1n+1 as a two-variable joint law on that pair; the iii-th coordinate marginal of a law on words; and the product law ∏irowsi(wi)\prod_i \mathrm{rows}_i(w_i)∏i​rowsi​(wi​) induced by a family of per-coordinate laws.

For channels, the channel joint of an input prior pr\mathrm{pr}pr and a channel KKK is

J(x,y)=pr(x)∏iK(xi,yi),J(x,y) = \mathrm{pr}(x)\prod_{i} K(x_i, y_i),J(x,y)=pr(x)i∏​K(xi​,yi​),

an input word drawn from the prior and pushed through the channel coordinatewise and independently. The prior is arbitrary and need not be a product, so correlation across uses is permitted.

For decoding, given a joint law JJJ on (guess, truth) it defines the correct and erroneous mass,

Pc=∑gJ(g,g),Pe=∑g∑w≠gJ(g,w),P_c=\sum_g J(g,g),\qquad P_e=\sum_{g}\sum_{w\ne g}J(g,w),Pc​=g∑​J(g,g),Pe​=g∑​w=g∑​J(g,w),

together with the comparison law used to prove Fano's inequality: mass PcP_cPc​ on the guess itself and Pe/MP_e/MPe​/M on every answer, scaled by the guess marginal.

Formalization note. That comparison law is a sub-probability: its rows sum to at most one, not to one. This is deliberate, and it is what removes all counting of the off-diagonal from the proof, at the cost of the constant log⁡M\log MlogM in place of the textbook log⁡(M−1)\log(M-1)log(M−1).

Definition code
/-
Definitions for the weak converse: words, product laws, memoryless channels,
and the guess/truth quantities Fano's inequality is stated in.

This imports the generic finite-information bundle and adds only the
constructions needed to talk about repeated use of a channel and about a
decoder that may be wrong.

Definitions only; every claim about these objects is proved in the theorem
that imports this bundle.
-/

import Definitions.Def_TranscendenceTowerFiniteInformation

set_option autoImplicit false

open scoped BigOperators
open TranscendenceTower.FiniteInformation

namespace TranscendenceTower.ConversePlatform

noncomputable section

variable {α β γ : Type} [Fintype α] [DecidableEq α] [Fintype β] [DecidableEq β]

/-! ## Words -/

/-- Words of length `n+1` are prefixes of length `n` paired with a last
symbol. -/
def snocEquiv (n : ℕ) : ((Fin n → β) × β) ≃ (Fin (n + 1) → β) where
  toFun p := Fin.snoc p.1 p.2
  invFun w := (Fin.init w, w (Fin.last n))
  left_inv p := by simp
  right_inv w := by simp

/-- A law on words of length `n+1`, read as a joint law on
(prefix, last symbol). -/
def splitLast {n : ℕ} (law : (Fin (n + 1) → β) → ℝ) : (Fin n → β) → β → ℝ :=
  fun w b => law (Fin.snoc w b)

/-- The `i`-th coordinate marginal of a law on words. -/
def coordMarginal {n : ℕ} (law : (Fin n → β) → ℝ) (i : Fin n) : β → ℝ :=
  fun b => ∑ w : Fin n → β, if w i = b then law w else 0

/-- The product law on words induced by a family of per-coordinate laws. -/
def productLaw {n : ℕ} (rows : Fin n → β → ℝ) : (Fin n → β) → ℝ :=
  fun w => ∏ i, rows i (w i)

/-- The word-level joint law of an input prior and a memoryless channel:
draw an input word from the prior, then pass it through the channel
coordinatewise and independently. -/
def channelJoint {n : ℕ} (prior : (Fin n → α) → ℝ) (K : α → β → ℝ) :
    (Fin n → α) → (Fin n → β) → ℝ :=
  fun x y => prior x * productLaw (fun i => K (x i)) y

/-! ## Guess and truth -/

variable [Fintype γ] [DecidableEq γ]

/-- Probability that the guess equals the truth. -/
def correctProb (J : γ → γ → ℝ) : ℝ := ∑ g, J g g

/-- Probability that the guess differs from the truth. -/
def errorProb (J : γ → γ → ℝ) : ℝ := ∑ g, ∑ w, if w = g then 0 else J g w

/-- Weight the comparison law used in Fano's inequality puts on answer `w`
when the guess is `g`: the correct-answer mass on the guess itself, and
`Pe / M` on every answer.  Its rows sum to at most one. -/
def fanoWeight (J : γ → γ → ℝ) (g w : γ) : ℝ :=
  if w = g then correctProb J else errorProb J / (Fintype.card γ : ℝ)

/-- The comparison law: the guess marginal times the weight. -/
def fanoComparison (J : γ → γ → ℝ) (g w : γ) : ℝ :=
  fstMarginal J g * fanoWeight J g w

end

end TranscendenceTower.ConversePlatform
Source
Mateo Estrada, Harmless and Pointless: Consistency, rigidity, and the indeterminacy of context transfer in McCarthy's formalization of context, 7 September 2026, Section 8.3 (What repeated observation cannot buy), Theorems 17 and 18.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me