Conditional common-randomness generation without communication
ProvedQAlgorithms.Papers.Independent.Support50.P38.commonRandomness_reversalLet 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 . Assume the global assertion of Question 4: for every finite source and channel and each , ordinary minimum code rates converge to mutual information. For every , all sufficiently large positive admit a positive integer and normalized local stochastic kernels on and on with
where . A uniform shared seed selects ; the local outputs are independent conditional on it, with no communication. The result is an implication from an open assertion, not an unconditional reversibility theorem.
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
/-- PDF pp.8–9: CONDITIONAL reversal of common-randomness extraction. Question 4 is
an antecedent, never an available theorem. The two local randomizations are independent
given a single uniform shared seed, and no public discussion is allowed. -/
theorem commonRandomness_reversal (hquestion : QuestionFour)
{A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
(p : A → ℝ) (w : A → B → ℝ) (hp : IsLaw p) (hw : IsStochastic w)
(error slack : ℝ) (he : 0 < error) (hs : 0 < slack) :
∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∃ seeds : ℕ, 0 < seeds ∧ Real.logb 2 (seeds : ℝ) / n ≤ sourceInformationBits p w + slack ∧
∃ (a : Fin seeds → SourceWord A n → ℝ) (b : Fin seeds → SourceWord B n → ℝ),
IsStochastic a ∧ IsStochastic b ∧
tv (jointWordLaw p w) (generatedPairs a b) ≤ error := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Assume the following statement: for every pair of positive integers , every probability law on , every stochastic matrix from that set to , and every , the sequence converges to , where is the infimum in of positive message sizes admitting stochastic encoders and decoders such that
Here each encoder row and each decoder row is nonnegative and sums to , and
The natural-number infimum is defined to be if its defining set is empty, and the total logarithm used here has . Under this assumption, let be any finite nonempty types, let be nonnegative with , and let satisfy and for every . For every pair of positive real numbers , there is a natural-number threshold such that, for every at least that threshold with , there exist a positive integer and probability laws on and on , one of each for every , satisfying
Zero probabilities are permitted throughout, and the conclusion imposes no upper bound on .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.