Finite-population tail probability conditioned on passing parameter estimation
OpenQAlgorithms.Papers.Independent.Intakethird100.P01.samplingTailS14Let be positive integers and . Let have any normalized joint probability distribution on two -bit strings. Independently of these strings, draw a uniformly random -element subset of the positions. Let be the relative Hamming distance on and let be the relative Hamming distance on its complement. Fix , define the event , and assume . For any , put
Then
This is a sampling-without-replacement estimate for arbitrary correlated strings. Applying it to an interactive QKD execution requires separately deriving the stated independent uniform sampling experiment.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P01
namespace QAlgorithms.Papers.Independent.Intakethird100.P01
open scoped BigOperators ComplexConjugate ComplexOrder
-- Accepted extended entropy: the finite-real smoothing helper excludes radius >= 1.
open QAlgorithms.Papers.Independent.Information100.P67
(IsSubnormalized purifiedDistance conditionalMaxEntropy smoothConditionalMaxEntropyExtended)
noncomputable section
/-- PDF p.13, Eqs.(S11)--(S14): the pass-conditioned finite-population tail bound.
The sample is drawn independently of an arbitrary normalized joint law of the total strings. -/
theorem samplingTailS14 (n k : ℕ) (hn : 0 < n) (hk : 0 < k)
(P : StringPair (n + k) → ℝ) (hP : ∀ z, 0 ≤ P z) (hPsum : ∑ z, P z = 1)
(Q : ℝ) (hQ0 : 0 ≤ Q) (hQ1 : Q ≤ 1) (hpass : 0 < passProbability P Q)
(mu : ℝ) (hmu : 0 ≤ mu) :
probabilityGivenPass P Q (fun w => complementErrorFraction w ≥ sampleError w + mu) ≤
(samplingFailureParameter n k mu) ^ 2 / passProbability P Q := by sorry
end
end QAlgorithms.Papers.Independent.Intakethird100.P01
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For all positive natural numbers , let be a nonnegative real function on ordered pairs of Boolean strings of length , with . Consider outcomes , where has cardinality , assigning each outcome weight . Define
For every real with , assume that the total weight of outcomes satisfying is strictly positive. Then, for every real , the total weight of outcomes satisfying both and , divided by , satisfies
The deviation event uses a non-strict inequality and includes .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.