Joint sampling deviation with boundary-inclusive information tail
OpenQAlgorithms.Papers.Independent.Intakenext100.P77.joint_sampling_deviationLet and fix an arbitrary normalized probability law on binary error strings , for a fixed basis. Independently choose a uniformly random -element subset as the information positions; its complement is the test set. Let be the restrictions of . For and ,
This is a joint event, averaged over the balanced partition and the full error law, without conditioning on passing. The boundary-inclusive information endpoint follows the weak-tail bound in Appendix M, Eq. (41).
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P77
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P77
open scoped BigOperators ComplexConjugate ComplexOrder
open QAlgorithms
-- The repair instruction authorizes imports of pinned accepted definitions.
-- These are definitions only; no imported paper theorem is used here.
open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)
open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon)
open QAlgorithms.Papers.Independent.Information100.P39 (pushLaw)
open QAlgorithms.Papers.Independent.Support50.P16 (trivialMeasurement)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- Lemma 4.4, PDF p.10; Appendices L--M, pp.27--28. SOURCE CORRECTION:
printed information event is strict '>'; changed to '>=' to retain Eq.(8)'s
boundary. Weak-tail Eq.(41) proves this boundary-inclusive bound with the same
constant. Test endpoint '<=' follows the protocol. Independent moderation needed. -/
theorem joint_sampling_deviation {n : ℕ} (hn : 1 ≤ n)
(p : Law (Qubits (n + n))) (allowed margin : ℝ)
(hp : 0 ≤ allowed) (hp1 : allowed ≤ 1) (he : 0 < margin) :
samplingDeviation p allowed margin ≤ 2 * Real.exp (-(n : ℝ) * margin ^ 2 / 2) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P77
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , every function satisfying for every and , and all real numbers satisfying and , let , and define and . Then
Thus the left side averages uniformly over all subsets of exactly coordinates and uses the same arbitrary law for each subset. The endpoints are included, and there is no upper bound on ; when , the summation event is empty and the left side is zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.