A window fails typicality with exponentially small probability
ProvedBitcoinBackboneProb.window_boundFor a window with and : .
import Definitions.Def_BitcoinBackboneProb open BitcoinBackboneProb BitcoinBackbone open MeasureTheory ProbabilityTheory
theorem BitcoinBackboneProb.window_bound (n t : ℕ) (p : unitInterval) (a k : ℕ) (hk1 : 1 ≤ k)
(hk : 2 * t * (p : ℝ) ≤ ((k : ℝ) - 1) * margin n t p) :
(P n t p).real {ω | ∑ i ∈ Finset.Ioo a (a + k), Y ω i ≤ ∑ i ∈ Finset.Icc a (a + k), Z ω i} ≤
Real.exp (-2 * (((k : ℝ) - 1) * margin n t p - 2 * t * p) ^ 2 /
(((k : ℝ) + 1) * ((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.window_bound
Statement. Let , and . Assume
- ;
- (real arithmetic).
Then
Here ( rounds; empty when ) and ( rounds); the event is that the number of uniquely successful rounds strictly inside the window is at most (non-strict) the number of adversarial blocks in the closed window. The start is arbitrary (including ). The denominator is positive.
No positivity of the margin is assumed explicitly. Implied by the hypotheses: if then and the right side equals ; if then .
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).
Window conventions
For natural numbers : (closed window; empty if , a single point if ) and (open window; empty whenever ). A sum over an empty index set is . Sums of the natural-number variables are computed in and compared there.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.