Cslib.Probability.PMF.posteriorDist_apply
theoremverifiedformalizationimported Lean
Cslib.Probability.PMF.posteriorDist_apply
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open ENNReal in universe u v in variable {α : Type u} {β : Type v} in @[simp] theorem Cslib.Probability.PMF.posteriorDist_apply (p : PMF α) (f : α → PMF β) (b : β) (hb : b ∈ (p.bind f).support) (a : α) : posteriorDist p f b hb a = (p.bind fun a' => (f a').bind fun b' => PMF.pure (a', b')) (a, b) / (p.bind f) b
- Formalizes
- CSLib, `Cslib.Probability.PMF.posteriorDist_apply`
- Lean proof
- By Samuel Schlesinger, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Samuel Schlesinger. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.Probability.PMF.posteriorDist_apply← Cslib.Probability.PMF.posteriorDist_apply (Cslib/Probability/PMF.lean:107): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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.posteriorDistThe posterior distribution
- Used by 15
- Cslib.Crypto.Protocols.PerfectSecrecy.ciphertextIndist_of_perfectlySecretPerfect secrecy implies ciphertext indistinguishability.
- pmf_output_indist_of_posterior_eq_priorLet α and β be types, p a PMF on α, and f : α → PMF β a channel. Suppose that for every output b in the support of the marginal…
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_iff_ciphertextIndistA scheme is perfectly secret iff the ciphertext distribution is independent of the plaintext ([KatzLindell2020], Lemma 2.5).
- Cslib.Probability.PMF.posteriorDist_eq_prior_of_outputIndistIf the output distribution of a channel does not depend on the input, then conditioning on any output with positive probability leaves the…
- Cslib.Crypto.Protocols.PerfectSecrecy.otp_perfectlySecretThe one-time pad is perfectly secret ([KatzLindell2020], Theorem 2.10).
- Cslib.Crypto.Protocols.SecretSharing.Scheme.PerfectlyPrivatePerfect privacy for unauthorized coalitions: conditioning on a view does not change the prior on secrets.
- Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_of_ciphertextIndistCiphertext indistinguishability implies perfect secrecy.
- Cslib.Crypto.Protocols.PerfectSecrecy.shannonKeySpacePerfect secrecy requires
|K| ≥ |M|(Shannon's theorem). - Cslib.Crypto.Protocols.PerfectSecrecy.perfectlySecret_iff_indepPerfect secrecy is equivalent to message-ciphertext independence. The two formulations are related by multiplying/dividing by
marginal(c). - Cslib.Crypto.Protocols.SecretSharing.Scheme.posteriorSecretDist_applyCslib.Crypto.Protocols.SecretSharing.Scheme.posteriorSecretDist_apply
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDist_applyCslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDist_apply
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.PerfectlySecretAn encryption scheme is perfectly secret if the posterior message distribution equals the prior for every ciphertext with positive…
- Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.posteriorMsgDistThe posterior message distribution
Pr[M | C = c]as a probability distribution, given a message prior and a ciphertext in the support of… - Cslib.Crypto.Protocols.PerfectSecrecy.EncScheme.perfectlySecret_keySpace_gePerfect secrecy requires
|K| ≥ |M|([KatzLindell2020], Theorem 2.12). - Cslib.Crypto.Protocols.SecretSharing.Scheme.posteriorSecretDistThe posterior distribution on secrets after observing the coalition view
v.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open ENNReal in universe u v in variable {α : Type u} {β : Type v} in @[simp] theorem Cslib.Probability.PMF.posteriorDist_apply (p : PMF α) (f : α → PMF β) (b : β) (hb : b ∈ (p.bind f).support) (a : α) : posteriorDist p f b hb a = (p.bind fun a' => (f a').bind fun b' => PMF.pure (a', b')) (a, b) / (p.bind f) b := rfl