pmf_output_indist_of_posterior_eq_prior
Let α and β be types, p a PMF on α, and f : α → PMF β a channel. Suppose that for every output b in the support of the marginal distribution (p.bind f), the posterior distribution Cslib.Probability.PMF.posteriorDist p f b hb equals p. Then for all inputs a₀ and a₁ in the support of p, the output distributions f a₀ and f a₁ are equal.
Statement
theorem pmf_output_indist_of_posterior_eq_prior {α β : Type*} (p : PMF α) (f : α → PMF β) (h : ∀ (b : β) (hb : b ∈ (p.bind f).support), Cslib.Probability.PMF.posteriorDist p f b hb = p) (a₀ a₁ : α) (h₀ : a₀ ∈ p.support) (h₁ : a₁ ∈ p.support) : f a₀ = f a₁
- Formalizes
- Shannon (1949), 'Communication Theory of Secrecy Systems', Theorem 1
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- Cslib.Probability.PMF.posteriorDistThe posterior distribution
Pr[A = a | B = b]as aPMF, givena ← p,b ← f a, and thatbhas positive marginal probability. - Cslib.Probability.PMF.posteriorDist_applyCslib.Probability.PMF.posteriorDist_apply
- Cslib.Probability.PMF.bind_pair_applyEvaluating the "pairing" bind
(do let a ← p; return (a, ← f a))at(a, b)gives the productp a * f a b.
- Cslib.Probability.PMF.posteriorDistThe posterior distribution
Read back from the Lean
For any types α and β, given a prior probability mass function p : PMF α and a channel/transition kernel f : α → PMF β:
if for every b : β in the support of the marginal distribution p.bind f (with witness hb), the posterior distribution Cslib.Probability.PMF.posteriorDist p f b hb is equal to the prior p,
then for all a₀, a₁ : α that belong to the support of p, the output distributions f a₀ and f a₁ are equal.
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
To prove that any two inputs in the prior's support induce identical output distributions when the posterior always equals the prior, the argument establishes that every such input $a$ induces the marginal distribution: $f(a)(b) = (p.\mathrm{bind}\ f)(b)$ for all $b$. For outputs $b$ in the marginal support, Bayes' formula and the assumption that the posterior equals the prior yield $(p(a) f(a)(b)) / (p.\mathrm{bind}\ f)(b) = p(a)$, from which canceling the non-zero probabilities gives $f(a)(b) = (p.\mathrm{bind}\ f)(b)$. For outputs $b$ outside the marginal support, the total probability $(p.\mathrm{bind}\ f)(b) = \sum_{a'} p(a') f(a')(b)$ is zero, forcing each individual term $p(a) f(a)(b)$ and hence $f(a)(b)$ to be zero. Since $f(a_0)$ and $f(a_1)$ both coincide with the marginal distribution on all outputs, they are equal.
To show $f(a_0) = f(a_1)$, it suffices to establish that $f(a)(b) = (p.\mathrm{bind}\ f)(b)$ for every $a \in \mathrm{supp}(p)$ and every output $b$.
We formulate an intermediate claim `h_eq` asserting that any input $a$ in the prior's support yields the marginal probability $(p.\mathrm{bind}\ f)(b)$ on every output $b$. We fix an arbitrary $a \in \mathrm{supp}(p)$ and $b \in \beta$.
have h_eq : ∀ (a : α), a ∈ p.support → ∀ (b : β), f a b = (p.bind f) b := by intro a ha b
If $b$ is in the support of the marginal distribution $p.\mathrm{bind}\ f$, then $f(a)(b) = (p.\mathrm{bind}\ f)(b)$.
We split into cases on whether $b \in \mathrm{supp}(p.\mathrm{bind}\ f)$. When $b$ is in the support, hypothesis $h$ ensures that the posterior distribution conditioned on $b$ equals the prior $p$, so its evaluation at $a$ is $p(a)$. Unfolding the posterior distribution via `Cslib.Probability.PMF.posteriorDist_apply` and `Cslib.Probability.PMF.bind_pair_apply` gives $(p(a) \cdot f(a)(b)) / (p.\mathrm{bind}\ f)(b) = p(a)$. Since $b \in \mathrm{supp}(p.\mathrm{bind}\ f)$, the marginal $(p.\mathrm{bind}\ f)(b)$ is non-zero (by `PMF.mem_support_iff`) and finite (by `PMF.apply_ne_top`), so multiplying both sides by $(p.\mathrm{bind}\ f)(b)$ cancels the denominator via `ENNReal.div_mul_cancel`. Finally, since $a \in \mathrm{supp}(p)$, $p(a)$ is non-zero and finite, allowing us to cancel $p(a)$ via `ENNReal.mul_right_inj` to conclude $f(a)(b) = (p.\mathrm{bind}\ f)(b)$.
uses
Cslib.Probability.PMF.posteriorDist_apply,Cslib.Probability.PMF.bind_pair_apply,PMF.mem_support_iff,PMF.apply_ne_top,ENNReal.div_mul_cancel,ENNReal.mul_right_injby_cases hb : b ∈ (p.bind f).support · have h1 : Cslib.Probability.PMF.posteriorDist p f b hb a = p a := by rw [h b hb] rw [Cslib.Probability.PMF.posteriorDist_apply, Cslib.Probability.PMF.bind_pair_apply] at h1 have hb_ne_zero : (p.bind f) b ≠ 0 := by rwa [PMF.mem_support_iff] at hb have hb_ne_top := PMF.apply_ne_top (p.bind f) b have ha_ne_zero : p a ≠ 0 := by rwa [PMF.mem_support_iff] at ha have ha_ne_top := PMF.apply_ne_top p a have h2 : (p a * f a b) / (p.bind f) b * (p.bind f) b = p a * (p.bind f) b := by rw [h1] rw [ENNReal.div_mul_cancel hb_ne_zero hb_ne_top] at h2 exact (ENNReal.mul_right_inj ha_ne_zero ha_ne_top).mp h2
If $b$ is not in the support of the marginal distribution $p.\mathrm{bind}\ f$, then $f(a)(b) = (p.\mathrm{bind}\ f)(b) = 0$.
In the complementary case where $b \notin \mathrm{supp}(p.\mathrm{bind}\ f)$, the marginal probability is $(p.\mathrm{bind}\ f)(b) = 0$ by `PMF.mem_support_iff` and `Classical.not_not`. By `PMF.bind_apply`, this marginal probability is the sum $\sum_{a'} p(a') f(a')(b) = 0$. Because a series of non-negative reals sums to zero if and only if each term is zero (`ENNReal.tsum_eq_zero`), every term $p(a') f(a')(b)$ vanishes; in particular, $p(a) f(a)(b) = 0$. Since $a \in \mathrm{supp}(p)$, $p(a) \ne 0$, so `mul_eq_zero_iff_left` gives $f(a)(b) = 0 = (p.\mathrm{bind}\ f)(b)$, completing the proof of `h_eq`.
uses
PMF.mem_support_iff,Classical.not_not,PMF.bind_apply,ENNReal.tsum_eq_zero,mul_eq_zero_iff_left· have hb_zero : (p.bind f) b = 0 := by rwa [PMF.mem_support_iff, Classical.not_not] at hb rw [hb_zero] have h_bind : (p.bind f) b = ∑' a', p a' * f a' b := PMF.bind_apply p f b rw [hb_zero] at h_bind have h_all : ∀ a', p a' * f a' b = 0 := by rwa [← ENNReal.tsum_eq_zero] have ha_prod := h_all a have ha_ne_zero : p a ≠ 0 := by rwa [PMF.mem_support_iff] at ha exact (mul_eq_zero_iff_left ha_ne_zero).mp ha_prod
The channel output distributions $f(a_0)$ and $f(a_1)$ are equal.
By function extensionality (`ext b`), it suffices to show that $f(a_0)(b) = f(a_1)(b)$ for every $b$. Since both $a_0$ and $a_1$ belong to the support of $p$ by hypotheses $h_0$ and $h_1$, the intermediate lemma `h_eq` shows that both $f(a_0)(b)$ and $f(a_1)(b)$ are equal to $(p.\mathrm{bind}\ f)(b)$, completing the proof.
ext b rw [h_eq a₀ h₀ b, h_eq a₁ h₁ b]
Cslib.Probability.PMF.posteriorDist_apply- The posterior probability of $a$ given observation $b$ is the joint probability of $(a, b)$ divided by the marginal probability of $b$.
Cslib.Probability.PMF.bind_pair_apply- The joint probability of the pair $(a, b)$ under prior $p$ and channel $f$ is given by $p(a) \cdot f(a)(b)$.
PMF.mem_support_iff- An element belongs to the support of a probability mass function if and only if its probability is non-zero.
PMF.apply_ne_top- The probability assigned by a PMF to any point is finite (strictly less than $\infty$).
ENNReal.div_mul_cancel- For extended non-negative reals, division by $a$ followed by multiplication by $a$ cancels, provided $a \ne 0$ and $a \ne \infty$.
ENNReal.mul_right_inj- In extended non-negative reals, a non-zero, finite factor $a$ can be canceled from both sides: $a \cdot b = a \cdot c \leftrightarrow b = c$.
Classical.not_not- Double negation elimination: $\neg\neg P \leftrightarrow P$.
PMF.bind_apply- The marginal probability of an output $b$ under $p.\mathrm{bind}\ f$ is the sum $\sum_{a'} p(a') \cdot f(a')(b)$ over all inputs $a'$.
ENNReal.tsum_eq_zero- A sum of extended non-negative reals is zero if and only if every term in the sum is zero.
mul_eq_zero_iff_left- In an algebraic structure without zero divisors, if $a \ne 0$, then $a \cdot b = 0 \leftrightarrow b = 0$.
- Because Lean represents probabilities in `ENNReal` (extended non-negative reals $[0, \infty]$), standard algebraic simplifications like canceling denominators or common factors require explicitly verifying that values are non-zero and finite ($\ne \top$).
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.
/-- If conditioning on every output in the marginal support leaves the posterior equal to the prior, then the output distributions are identical across all inputs in the support. -/theorem pmf_output_indist_of_posterior_eq_prior {α β : Type*} (p : PMF α) (f : α → PMF β) (h : ∀ (b : β) (hb : b ∈ (p.bind f).support), Cslib.Probability.PMF.posteriorDist p f b hb = p) (a₀ a₁ : α) (h₀ : a₀ ∈ p.support) (h₁ : a₁ ∈ p.support) : f a₀ = f a₁ := by have h_eq : ∀ (a : α), a ∈ p.support → ∀ (b : β), f a b = (p.bind f) b := by intro a ha b by_cases hb : b ∈ (p.bind f).support · have h1 : Cslib.Probability.PMF.posteriorDist p f b hb a = p a := by rw [h b hb] rw [Cslib.Probability.PMF.posteriorDist_apply, Cslib.Probability.PMF.bind_pair_apply] at h1 have hb_ne_zero : (p.bind f) b ≠ 0 := by rwa [PMF.mem_support_iff] at hb have hb_ne_top := PMF.apply_ne_top (p.bind f) b have ha_ne_zero : p a ≠ 0 := by rwa [PMF.mem_support_iff] at ha have ha_ne_top := PMF.apply_ne_top p a have h2 : (p a * f a b) / (p.bind f) b * (p.bind f) b = p a * (p.bind f) b := by rw [h1] rw [ENNReal.div_mul_cancel hb_ne_zero hb_ne_top] at h2 exact (ENNReal.mul_right_inj ha_ne_zero ha_ne_top).mp h2 · have hb_zero : (p.bind f) b = 0 := by rwa [PMF.mem_support_iff, Classical.not_not] at hb rw [hb_zero] have h_bind : (p.bind f) b = ∑' a', p a' * f a' b := PMF.bind_apply p f b rw [hb_zero] at h_bind have h_all : ∀ a', p a' * f a' b = 0 := by rwa [← ENNReal.tsum_eq_zero] have ha_prod := h_all a have ha_ne_zero : p a ≠ 0 := by rwa [PMF.mem_support_iff] at ha exact (mul_eq_zero_iff_left ha_ne_zero).mp ha_prod ext b rw [h_eq a₀ h₀ b, h_eq a₁ h₁ b]