forest_greedy_enveloped_tie_bias_one
An enveloped fixed-parity law and a fair coin permit an increase from discrepancy 1 with probability at most 3/8.
Statement
theorem forest_greedy_enveloped_tie_bias_one (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) : (((Finset.univ.filter (fun p : β × Bool => (1 : ℤ) < Y p.1 ∨ ((1 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ 3 / 8
- 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 proof specializes the general enveloped tie-bias bound `forest_greedy_enveloped_tie_bias_bound` to initial discrepancy j = 1. Evaluating the tail envelope at arguments 1, 2, and 3 yields E(1) = 1/2, E(2) = 3/8, and E(3) = 1/4, so max(E(2), (E(1) + E(3)) / 2) simplifies directly to 3/8. Rewriting the cardinality of the product sample space β × Bool matches the goal to this simplified bound.
The general tie-bias bound applies at discrepancy j = 1, giving an upper bound of max(E(2), (E(1) + E(3)) / 2).
Specialising `forest_greedy_enveloped_tie_bias_bound` to j = 1 (where the prerequisite 1 ≤ 1 is proved by linear integer arithmetic) yields an inequality bounding the probability of discrepancy strictly greater than 1, or equal to 1 with coin flip true, by the envelope combination max(E(1+1), (E(1) + E(1+2)) / 2).
uses
forest_greedy_enveloped_tie_bias_boundhave h := forest_greedy_enveloped_tie_bias_bound β Y hY 1 (by omega)
The envelope upper bound evaluates numerically to 3/8.
By definition of `forest_carpool_tail_envelope` and `Nat.fib`, we have E(1) = (1/2)^1 = 1/2, E(2) = 3/8, and E(3) = (1/2)^2 = 1/4. The average (E(1) + E(3)) / 2 is (1/2 + 1/4) / 2 = 3/8, and the maximum max(3/8, 3/8) is 3/8. Evaluating these definitions reduces the upper bound in hypothesis h to 3/8.
uses
forest_carpool_tail_envelope,Nat.fibnorm_num [forest_carpool_tail_envelope, Nat.fib] at h
The goal follows from the evaluated bound by expanding the cardinality of the product space.
The denominator in the goal is the size of the product space β × Bool. Rewriting this cardinality via `Fintype.card_prod` and `Fintype.card_bool` as |β| * 2, and distributing casts using `Nat.cast_mul` and `Nat.cast_ofNat`, matches the left-hand side of the simplified bound h, completing the proof.
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 law Y on β and any integer j ≥ 1, the probability that Y > j or that Y = j with coin flip true 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 E(k), equal to 3/8 if k = 2 and (1/2)^(fib(k)) otherwise.
Nat.fib- The n-th Fibonacci number.
Fintype.card_prod- The cardinality of the Cartesian product α × β is the product of the cardinalities of α and β.
Fintype.card_bool- The type Bool has exactly 2 elements.
Nat.cast_mul- Casting a product of natural numbers to a semiring distributes over multiplication: ↑(m * n) = ↑m * ↑n.
Nat.cast_ofNat- Casting a numeral from ℕ to another type with numeral notation preserves the numeral.
- During the evaluation in line 7, `norm_num` also partially simplifies the denominator `Fintype.card (β × Bool)` in the hypothesis into `Fintype.card β * 2`. Step 3 then performs the matching rewrite on the denominator of the main goal.
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_one (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) : (((Finset.univ.filter (fun p : β × Bool => (1 : ℤ) < Y p.1 ∨ ((1 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ 3 / 8 := by have h := forest_greedy_enveloped_tie_bias_bound β Y hY 1 (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