Lemma I.8: Pr(TV,P,alpha)≥1−a/alpha² and |TV,P,alpha|≤2^(nH(P)+K a alpha sqrt(n)), K=2log2(e)/e.
ProvedQAlgorithms.Papers.Independent.Renew46.P43.classicalTypicalLet be a finite nonempty alphabet of size , a normalized law, and . A word is variance typical if each count differs from by at most . Put .
This is the source result with its stated operational or information-theoretic domain.
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P43
noncomputable section
namespace QAlgorithms.Papers.Independent.Renew46.P43
open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal Matrix.Norms.L2Operator
open Filter MeasureTheory
open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)
open QAlgorithms.Papers.Independent.Information100.P06 (Below)
open QAlgorithms.Papers.Independent.Information100.P60 (copies relativeBits)
open QAlgorithms.Papers.Independent.Dependency50.P19 (count both)
open QAlgorithms.Papers.Independent.Information100.P22 (coherentInformation)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- Lemma I.8, PDF pp.11-12. Printed d in the cardinality bound is corrected to
alphabet size a: the proof is the eigenvalue-list counting argument, and there is no
quantum dimension in this classical statement. See MODERATION_NOTES.md. -/
theorem classicalTypical {I : Type} [Fintype I] [DecidableEq I] [Nonempty I]
(P : PMF I) (n : ℕ) (hn : 0 < n) (alpha : ℝ) (halpha : 0 < alpha) :
(∑ w ∈ varianceSet P n alpha, ∏ k, (P (w k)).toReal) ≥
1 - Fintype.card I / alpha^2 ∧
((varianceSet P n alpha).card : ℝ) ≤
exp2 (n * pmfEntropy P + varianceConstant * Fintype.card I * alpha * Real.sqrt n) := by sorry
end QAlgorithms.Papers.Independent.Renew46.P43
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite, nonempty set with decidable equality, let be a probability mass function on , and write as a real number. For every positive integer and every real , define and
Writing , with zero terms contributing zero, and , the declaration asserts both
Zero probabilities are allowed: the defining condition then requires the corresponding symbol to occur zero times; a symbol of probability one must occur times. The first lower bound is permitted to be negative.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.