Hoeffding's inequality for the adversary's lead on finite sets of rounds
ProvedBitcoinBackboneProb.sets_hoeffdingFor finite and with : .
import Definitions.Def_BitcoinBackboneProb open BitcoinBackboneProb BitcoinBackbone open MeasureTheory ProbabilityTheory
theorem BitcoinBackboneProb.sets_hoeffding (n t : ℕ) (p : unitInterval) (S T : Finset ℕ)
(hTS : T ⊆ S) (j : ℕ)
(hε : 0 ≤ (j : ℝ) + T.card * (n * p * (1 - (p : ℝ)) ^ (n - 1)) - S.card * (t * p)) :
(P n t p).real {ω | ∑ i ∈ T, Y ω i + j ≤ ∑ i ∈ S, Z ω i} ≤
Real.exp (-2 * ((j : ℝ) + T.card * (n * p * (1 - (p : ℝ)) ^ (n - 1)) - S.card * (t * p)) ^ 2
/ (S.card * ((t : ℝ) + 1) ^ 2)) := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinBackboneProb.sets_hoeffding
Statement. Let , , let be arbitrary finite sets of natural numbers (round indices; round allowed, not necessarily contiguous) with , and let . Write
Assume . Then
The event compares natural numbers: the number of uniquely successful rounds among the rounds in , plus , is at most the total number of adversarial blocks over the rounds in (non-strict ).
Edge case: if (hence ) the denominator is ; division by zero is defined to give , so the right side is . No hypothesis on the sign of the margin or on is made beyond .
Probabilistic round model (unfolded)
- Parameters. are arbitrary natural numbers (either may be ): is the number of honest parties, the number of adversarial queries per round. is an element of the closed unit interval (so and are allowed); wherever it appears in arithmetic it is the real number . All casts of and other naturals into formulas are casts into (so , etc. below are real subtractions and may be negative), except where a natural-number subtraction is explicitly flagged.
- Bernoulli law . The two-point Bernoulli measure on built by Mathlib's
bernoulliMeasure true false p: mass on and mass on . It is a probability measure. - Round outcomes . A round outcome is a pair with (which honest parties succeeded) and (which adversarial queries succeeded). If (resp. ) the corresponding component is the unique empty function.
- Round law . The product measure
on (product -algebra): all coordinates are independent, each with probability . It is a probability measure.
- Traces . A trace is an infinite sequence of round outcomes, indexed by all starting at ; with the product -algebra.
- Trace law . The infinite product probability measure on (Mathlib's
Measure.infinitePi): the coordinates are i.i.d. with law . It is a probability measure. For any set (measurable or not; non-measurable sets get their outer measure), below denotes the real number obtained by converting the (extended-nonnegative) measure of to ; it lies in . - Counts in one round. For :
- Round indicators. if and otherwise; if and otherwise (both natural numbers); computed in .
- Trace variables. For and (including ): , , (natural numbers), . So and .
- Margin.
where is natural-number subtraction (truncated at ): for the exponent is and ; for , ; the convention applies, so for , the factor equals .
- Rate.
(the denominator is at least , never zero).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.