forest_greedy_enveloped_tie_bias_two
An enveloped fixed-parity law and a fair coin permit an increase from discrepancy 2 with probability at most 1/4.
Statement
theorem forest_greedy_enveloped_tie_bias_two (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) : (((Finset.univ.filter (fun p : β × Bool => (2 : ℤ) < Y p.1 ∨ ((2 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ 1 / 4
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- forest_greedy_law_envelopedA finite uniform integer law has one fixed parity, is symmetric, and its positive tail at each positive integer is bounded by the forest…
- forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
- forest_greedy_enveloped_tie_bias_boundFor an enveloped fixed-parity law and a fair coin, the probability of a greedy increase from a positive discrepancy j is bounded by the…
- Used by 1
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
The proof, explained
The theorem establishes that for an enveloped law and an independent fair coin, the probability of exceeding 2 (or equaling 2 with a true coin toss) is at most 1/4. The proof specializes the general envelope tie-bias bound at threshold j = 2, yielding an upper bound of max(E(3), (E(2) + E(4)) / 2). Evaluating the envelope definition and Fibonacci values simplifies this bound numerically to 1/4, and rewriting the cardinality of β × Bool completes the argument.
The probability of exceeding discrepancy 2 (or equaling 2 with a true coin) is bounded by max(E(3), (E(2) + E(4)) / 2), where E is the carpool tail envelope.
We apply the general tie-bias bound lemma `forest_greedy_enveloped_tie_bias_bound` with discrepancy threshold j = 2. The required precondition 1 ≤ 2 is discharged by integer linear arithmetic (`omega`).
uses
forest_greedy_enveloped_tie_bias_boundhave h := forest_greedy_enveloped_tie_bias_bound β Y hY 2 (by omega)
The upper bound max(E(3), (E(2) + E(4)) / 2) simplifies numerically to 1/4.
By definition of the envelope function E and the Fibonacci sequence, E(2) = 3/8, E(3) = (1/2)^(fib 3) = (1/2)^2 = 1/4, and E(4) = (1/2)^(fib 4) = (1/2)^3 = 1/8. The average (E(2) + E(4)) / 2 is (3/8 + 1/8) / 2 = 1/4, making the maximum max(1/4, 1/4) = 1/4. Numerical evaluation (`norm_num`) computes this directly and simplifies the bound in hypothesis h.
uses
forest_carpool_tail_envelope,Nat.fibnorm_num [forest_carpool_tail_envelope, Nat.fib] at h
The probability of increasing from discrepancy 2 is at most 1/4, completing the proof.
The denominator |β × Bool| equals |β| × |Bool| = 2|β| using the product cardinality lemma and the fact that Bool has two elements. Rewriting these cardinalities reconciles the denominator in the goal with the hypothesis h, closing the goal.
uses
Fintype.card_prod,Fintype.card_bool,Nat.cast_mul,Nat.cast_ofNatsimpa only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] using h
forest_greedy_enveloped_tie_bias_bound- For an enveloped greedy law and an independent fair coin, the probability of exceeding a threshold j ≥ 1 (or tying at j with a true coin toss) is at most max(E(j+1), (E(j) + E(j+2))/2), where E is the carpool tail envelope.
forest_carpool_tail_envelope- The tail envelope function, defined as 3/8 when k = 2 and (1/2)^(fib(k)) otherwise.
Nat.fib- The Fibonacci sequence on natural numbers, defined by fib(0) = 0, fib(1) = 1, and fib(n+2) = fib(n+1) + fib(n).
Fintype.card_prod- The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Fintype.card_bool- The finite type of boolean values has cardinality 2.
Nat.cast_mul- The coercion of a product of natural numbers into a ring equals the product of the coerced factors.
Nat.cast_ofNat- The coercion of a natural numeral literal into a target type equals the numeral in that type.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem forest_greedy_enveloped_tie_bias_two (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) : (((Finset.univ.filter (fun p : β × Bool => (2 : ℤ) < Y p.1 ∨ ((2 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ 1 / 4 := by have h := forest_greedy_enveloped_tie_bias_bound β Y hY 2 (by omega) norm_num [forest_carpool_tail_envelope, Nat.fib] at h simpa only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] using h