AFTD Auto-Formalizing Theoretical Domains

pmf_output_indist_of_posterior_eq_prior

theoremverifiedformalization

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

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.

  1. 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$.

    lines 6–7

      have h_eq : ∀ (a : α), a ∈ p.support → ∀ (b : β), f a b = (p.bind f) b := by
        intro a ha b
  2. 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)$.

    lines 8–18

    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_inj

        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
  3. 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`.

    lines 19–28

    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
  4. 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.

    lines 29–30

      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$.

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

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