Typicality on a horizon holds with probability at least 1 − L² e^(−rate(λ+1))
ProvedBitcoinBackboneProb.typicalOn_prob_geThe complement of typicalOn_failure_le.
import Definitions.Def_BitcoinBackboneProb open BitcoinBackboneProb BitcoinBackbone open MeasureTheory ProbabilityTheory
theorem BitcoinBackboneProb.typicalOn_prob_ge (n t : ℕ) (p : unitInterval) (lam L : ℕ)
(hlam : 1 ≤ lam) (hm : 0 < margin n t p)
(hk : 4 * t * (p : ℝ) ≤ ((lam : ℝ) - 3) * margin n t p) :
1 - (L : ℝ) ^ 2 * Real.exp (-rate n t p * ((lam : ℝ) + 1)) ≤
(P n t p).real {ω | TypicalOn ω lam L} := 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.typicalOn_prob_ge
Statement. Let , and . Assume
- ;
- ;
- (real arithmetic; may be negative).
Then
with cast to . The left side may be negative, in which case the inequality holds trivially. For the left side is (and then holds vacuously for every ).
Consequences of the hypotheses and (stated because they restrict which parameter values the statement actually covers). Since , the hypothesis forces , and ; for this means (any ), for it requires in particular . Since and , the second hypothesis forces , and when it forces , i.e. . Thus values of below that the stated lower bound on admits make the hypotheses jointly unsatisfiable.
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.
Typicality on a horizon (unfolded)
For a trace and , holds iff for all with and :
(strict inequality; adversarial blocks counted over the closed window including both endpoints, uniquely successful rounds over the open window excluding both endpoints; , i.e. round of the trace, is included).
Edge cases: if there is no admissible window and holds vacuously (for every ). Any admissible window with has an empty open window, so its right side is and the strict inequality fails; hence for , is false for every and every , and for it is false for every as soon as .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.