Simultaneous row and aggregate sampling on a type class
OpenQAlgorithms.Papers.Independent.Support50.P38.lemma8Let be finite nonempty alphabets, , and a joint exact -type with marginal types . Let be the uniform type-class laws and the uniform reverse conditional-type channel. Fix and positive integers satisfying
There is one array , , for which, pointwise as functions,
Repeated samples are allowed. The simultaneous array is the combinatorial interface for channel compression.
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 8, PDF p.4: one sampling array simultaneously satisfies every row bound and
the aggregate empirical-law bound. Sampling is with replacement. The small relative-error
range 0 < epsilon < 1/2 is inherited from Lemma 5, used in the proof. -/
theorem lemma8 {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
[Nonempty A] [Nonempty B] {n : ℕ} (hn : 0 < n) (t : ExactType (A × B) n)
(epsilon : ℝ) (he : 0 < epsilon) (he1 : epsilon < 1 / 2)
(m seeds : ℕ) (hm : 0 < m) (hs : 0 < seeds)
(hrow : (2 * Real.log 2 / epsilon ^ 2) *
(((typeWords t.left).card : ℝ) * (typeWords t.right).card / (typeWords t).card) *
Real.logb 2 (4 * seeds * (typeWords t.left).card : ℝ) < m)
(hall : (2 * Real.log 2 / epsilon ^ 2) * (typeWords t.right).card *
Real.logb 2 (4 * (typeWords t.right).card : ℝ) < (seeds : ℝ) * m) :
∃ ys : Fin seeds → Fin m → SourceWord B n,
(∀ s j, ys s j ∈ typeWords t.right) ∧
(∀ s x,
(1 - epsilon) * typeUniform t.left x ≤ (∑ j, typeReverse t (ys s j) x) / m ∧
(∑ j, typeReverse t (ys s j) x) / m ≤ (1 + epsilon) * typeUniform t.left x) ∧
(∀ y,
(1 - epsilon) * typeUniform t.right y ≤
(∑ s, ∑ j, if ys s j = y then (1 : ℝ) else 0) / ((seeds : ℝ) * m) ∧
(∑ s, ∑ j, if ys s j = y then (1 : ℝ) else 0) / ((seeds : ℝ) * m) ≤
(1 + epsilon) * typeUniform t.right y) := 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 , and let have total count . Let be the length- words over with counts , and let have the marginal counts and . Write , , , and define to be on their respective type classes and zero elsewhere. For , let be the set of whose pairing with has counts , and define when , and otherwise. Given a real and positive integers satisfying
there exists an array , indexed by , , such that every belongs to , and for every and every ,
while for every ,
The array entries need not be distinct. Both bounds quantify over all words, including words outside the respective type classes, where the uniform type-class functions are zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.