Uniform exact-type channels and Bayes transpose
ProvedQAlgorithms.Papers.Independent.Support50.P38.lemma6Let be finite nonempty alphabets, a probability law on , and a stochastic channel. All logarithms and entropies are in bits. Write for the memoryless product laws, , and . Let and let be a joint exact -type with marginals . Write for its type classes, and for its forward and reverse fibers, and for the uniform type laws. Define and . Then
For compatible ,
On positive conditioning events, , with , and are the respective restrictions and normalizations of , where is the Bayes transpose of under . These identities establish the uniform-output and transpose structure used by the sampling construction.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P38
noncomputable section
namespace QAlgorithms.Papers.Independent.Support50.P38
open scoped BigOperators Matrix ComplexConjugate
open Filter
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
open QAlgorithms.Papers.Independent.Frontier30.P12 (IsStochastic)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)
attribute [local instance] Classical.propDecidable
/-- Lemma 6, PDF p.4: uniform type identities, forward and reverse cardinality ratios,
Bayes balance, and the conditional product-law identities on positive-mass events.
No full-support assumption is imposed. R and S are constructed as marginals of T. -/
theorem lemma6 {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
[Nonempty A] [Nonempty B] {n : ℕ} (hn : 0 < n)
(p : A → ℝ) (w : A → B → ℝ) (hp : IsLaw p) (hw : IsStochastic w)
(t : ExactType (A × B) n) :
(∀ y, (∑ x, typeUniform t.left x * typeForward t x y) = typeUniform t.right y) ∧
(∀ x y, typeUniform t.left x * typeForward t x y =
typeUniform t.right y * typeReverse t y x) ∧
(∀ x, x ∈ typeWords t.left →
0 < ∑ z ∈ typeWords t.left, wordMass p z →
typeUniform t.left x = wordMass p x / (∑ z ∈ typeWords t.left, wordMass p z)) ∧
(∀ y, y ∈ typeWords t.right →
0 < ∑ z ∈ typeWords t.right, wordMass (sourceOutputMarginal p w) z →
typeUniform t.right y = wordMass (sourceOutputMarginal p w) y /
(∑ z ∈ typeWords t.right, wordMass (sourceOutputMarginal p w) z)) ∧
(∀ x y, JointTypeWordsCompatible t x y →
typeForward t x y = ((typeWords t.left).card : ℝ) / (typeWords t).card ∧
typeReverse t y x = ((typeWords t.right).card : ℝ) / (typeWords t).card) ∧
(∀ x y, JointTypeWordsCompatible t x y →
0 < ∑ z ∈ forwardFiber t x, wordChannel w x z →
typeForward t x y = wordChannel w x y /
(∑ z ∈ forwardFiber t x, wordChannel w x z)) ∧
(∀ x y, JointTypeWordsCompatible t x y →
0 < ∑ z ∈ reverseFiber t y, wordChannel (sourceBayesReverse p w) y z →
typeReverse t y x = wordChannel (sourceBayesReverse p w) y x /
(∑ z ∈ reverseFiber t y, wordChannel (sourceBayesReverse p w) y z)) := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be finite nonempty types with decidable equality, let , let be a nonnegative distribution of total mass , and let have nonnegative rows of total mass . Let assign a natural-number count to every , with ; put and . Let be, respectively, the sets of length- words over having these exact counts. Say are compatible when their coordinatewise pairing belongs to ; set and . Define on and elsewhere, analogously, for compatible and otherwise, and for compatible and otherwise. Write , , , and . Then, for every and every , respectively,
For every , if , then ; for every , if , then . For every compatible ,
if additionally , then . Finally, define when , and otherwise, and put . For every compatible , if , then
No positive-probability assumption is imposed on ; each assertion with a positive-mass premise is conditional and imposes nothing when that mass is zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.