pmf_uniform_group_convolution_eq_uniform
Let G be a finite nonempty additive commutative group. For any probability mass function p on G, the convolution of p with the uniform distribution PMF.uniformOfFintype G, defined as p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)), is equal to PMF.uniformOfFintype G.
Statement
theorem pmf_uniform_group_convolution_eq_uniform {G : Type*} [AddCommGroup G] [Fintype G] [Nonempty G] (p : PMF G) : p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)) = PMF.uniformOfFintype G
- Formalizes
- Shannon (1949), 'Communication Theory of Secrecy Systems', Theorem 6
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Cslib.Probability.PMF.uniformOfFintype_map_equivA uniform distribution on a finite type is invariant under any equivalence.
Read back from the Lean
For any finite, nonempty additive commutative group $G$, and for every probability mass function $p$ on $G$, the monadic bind of $p$ with the family of distributions given by shifting the uniform distribution on $G$ by $m$ (that is, $(PMF.uniformOfFintype\ G).map\ (k \mapsto m + k)$) equals the uniform distribution on $G$ ($PMF.uniformOfFintype\ G$). In other words, the convolution of any probability mass function $p$ on $G$ with the uniform distribution on $G$ is the uniform distribution on $G$.
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 convolution of p with the uniform distribution is defined monadically by drawing m from p and shifting the uniform distribution by m. Because translation by any element of a finite group is a bijection, shifting the uniform distribution leaves it invariant. Replacing each shift by the uniform distribution turns the convolution into a mixture of a constant distribution, which evaluates to the uniform distribution since the total probability mass of p is 1.
Translation by any element of G preserves the uniform distribution on G.
For any m ∈ G, left-addition k ↦ m + k is an equivalence of G (Equiv.addLeft m). Pushing forward the uniform distribution on G along this equivalence leaves the uniform distribution invariant (Cslib.Probability.PMF.uniformOfFintype_map_equiv).
uses
Cslib.Probability.PMF.uniformOfFintype_map_equiv,Equiv.addLefthave h (m : G) : (PMF.uniformOfFintype G).map (fun k => m + k) = PMF.uniformOfFintype G := Cslib.Probability.PMF.uniformOfFintype_map_equiv (Equiv.addLeft m)
The convolution simplifies to the uniform distribution.
Rewriting the integrand using the translation invariance established in the previous step replaces each translated distribution with the uniform distribution. The convolution expression then reduces to binding p to the constant uniform distribution, which equals the uniform distribution by PMF.bind_const because the total probability mass of p is 1.
uses
PMF.bind_constsimp_rw [h] exact PMF.bind_const p (PMF.uniformOfFintype G)
Cslib.Probability.PMF.uniformOfFintype_map_equiv- Pushing forward the uniform distribution on a finite nonempty type along an equivalence yields the uniform distribution on the target type.
Equiv.addLeft- Left-addition by an element of an additive group is an equivalence (permutation) of that group.
PMF.bind_const- Binding any probability mass function with a constant probability distribution yields that constant distribution.
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.
/-- The convolution of any probability distribution with the uniform distribution on a finite additive group is the uniform distribution. -/theorem pmf_uniform_group_convolution_eq_uniform {G : Type*} [AddCommGroup G] [Fintype G] [Nonempty G] (p : PMF G) : p.bind (fun m => (PMF.uniformOfFintype G).map (fun k => m + k)) = PMF.uniformOfFintype G := by have h (m : G) : (PMF.uniformOfFintype G).map (fun k => m + k) = PMF.uniformOfFintype G := Cslib.Probability.PMF.uniformOfFintype_map_equiv (Equiv.addLeft m) simp_rw [h] exact PMF.bind_const p (PMF.uniformOfFintype G)