forest_greedy_enveloped_tie_bias_bound
For an enveloped fixed-parity law and a fair coin, the probability of a greedy increase from a positive discrepancy j is bounded by the larger of the envelope at j+1 and the average of its values at j and j+2.
Statement
theorem forest_greedy_enveloped_tie_bias_bound (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) (j : ℕ) (hj : 1 ≤ j) : (((Finset.univ.filter (fun p : β × Bool => (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ max (forest_carpool_tail_envelope (j + 1)) ((forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2)
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- forest_greedy_enveloped_tie_bias_oneAn enveloped fixed-parity law and a fair coin permit an increase from discrepancy 1 with probability at most 3/8.
- forest_greedy_enveloped_tie_bias_twoAn enveloped fixed-parity law and a fair coin permit an increase from discrepancy 2 with probability at most 1/4.
The proof, explained
The proof decomposes the favorable event for a greedy increase—either Y b > j, or Y b = j with a fair coin landing true—into disjoint components and analyses its probability based on whether ties can occur. If no ties occur (|equal| = 0), the probability simplifies to the single tail probability at j + 1, bounded by the envelope at j + 1. If ties can occur (|equal| > 0), the constant parity of Y forces all values strictly greater than j to be at least j + 2; the probability then equals the arithmetic mean of the tail probabilities at j and j + 2, which is bounded by the average of the envelopes at j and j + 2. In either case, the probability is bounded by the maximum of the two quantities.
Define the subsets of outcomes according to how Y compares to j.
We partition outcomes of β into those strictly greater than j (above), equal to j (equal), at least j (lo), and at least j + 2 (hi). We also define fav ⊆ β × Bool as the favorable event where either Y b > j, or Y b = j and the coin toss lands true.
classical let above : Finset β := Finset.univ.filter (fun b => (j : ℤ) < Y b) let equal : Finset β := Finset.univ.filter (fun b => (j : ℤ) = Y b) let lo : Finset β := Finset.univ.filter (fun b => (j : ℤ) ≤ Y b) let hi : Finset β := Finset.univ.filter (fun b => ((j + 2 : ℕ) : ℤ) ≤ Y b) let fav : Finset (β × Bool) := Finset.univ.filter (fun p => (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))
The sets above and equal are disjoint, and the favorable event has size |fav| = 2|above| + |equal|.
No outcome can satisfy both j < Y a and j = Y a, so above and equal are disjoint. Consequently, the Cartesian products above × Bool and equal × {true} are disjoint, and their union is exactly fav. Since Bool has 2 elements and {true} has 1, the size of fav is 2|above| + |equal|.
uses
Finset.disjoint_left.mpr,Finset.mem_filter.mp,Finset.mem_product,Finset.mem_product.mp,Finset.disjoint_left.mp,Finset.card_union_of_disjoint,Finset.card_product,Nat.mul_commhave hdis : Disjoint above equal := by apply Finset.disjoint_left.mpr intro a ha hb have ha' : (j : ℤ) < Y a := (Finset.mem_filter.mp ha).2 have hb' : (j : ℤ) = Y a := (Finset.mem_filter.mp hb).2 omega have hevent : fav = (above ×ˢ (Finset.univ : Finset Bool)) ∪ (equal ×ˢ {true}) := by ext p rcases p with ⟨b, c⟩ simp [fav, above, equal, Finset.mem_product] have hprod_dis : Disjoint (above ×ˢ (Finset.univ : Finset Bool)) (equal ×ˢ {true}) := by apply Finset.disjoint_left.mpr intro p hp hq have ha : p.1 ∈ above := (Finset.mem_product.mp hp).1 have hb : p.1 ∈ equal := (Finset.mem_product.mp hq).1 exact (Finset.disjoint_left.mp hdis) ha hb have hfav : fav.card = 2 * above.card + equal.card := by rw [hevent, Finset.card_union_of_disjoint hprod_dis] simp [Finset.card_product, Nat.mul_comm]
The set lo is the disjoint union of above and equal, so |lo| = |above| + |equal|.
An integer satisfies j ≤ Y b if and only if j < Y b or j = Y b. Thus lo = above ∪ equal, and because above and equal are disjoint, the size of lo is the sum of their sizes.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_union,Finset.card_union_of_disjointhave hlo : lo = above ∪ equal := by ext b simp only [lo, above, equal, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union] omega have hlo_card : lo.card = above.card + equal.card := by rw [hlo, Finset.card_union_of_disjoint hdis]
The state spaces have positive cardinality, and we extract the constant parity and tail bound hypotheses from the enveloped law.
Because β and β × Bool are nonempty finite types, their cardinalities are strictly positive. From the assumption that Y is an enveloped greedy law, we extract that all values Y a share a constant parity modulo 2 and that the upper tail probabilities at any threshold k ≥ 1 are bounded by forest_carpool_tail_envelope(k).
uses
Fintype.card_poshave hp : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β)) have hpc : (0 : ℝ) < Fintype.card (β × Bool) := by exact_mod_cast (Fintype.card_pos (α := β × Bool)) obtain ⟨parity, hparity⟩ := hY.1 have htail := hY.2.2
When no element has value j, the favorable count is 2|above| and above coincides with the tail at j + 1.
We split into cases on whether |equal| = 0. When |equal| = 0, no ties can occur, so |fav| = 2|above|. Over the integers, j < Y b is equivalent to j + 1 ≤ Y b, which identifies above with the tail event at threshold j + 1. Since j ≥ 1, the tail bound hypothesis applies at threshold j + 1.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Nat.cast_add,Nat.cast_oneby_cases hzero : equal.card = 0 · have hzeroR : (equal.card : ℝ) = 0 := by exact_mod_cast hzero have hfavR : (fav.card : ℝ) = 2 * (above.card : ℝ) := by exact_mod_cast (show fav.card = 2 * above.card by omega) have habove : above = Finset.univ.filter (fun b => ((j + 1 : ℕ) : ℤ) ≤ Y b) := by ext b simp only [above, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_one] omega have htail1 := htail (j + 1) (by omega)
When |equal| = 0, the probability is at most the envelope at j + 1, which is at most the maximum.
The total number of states is |β × Bool| = 2|β|. The probability |fav| / (2|β|) = 2|above| / (2|β|) simplifies to |above| / |β|. By the tail bound at j + 1, this is bounded by forest_carpool_tail_envelope(j + 1), which is at most the maximum of the envelope at j + 1 and the average via le_max_left.
uses
Fintype.card_prod,Fintype.card_bool,Nat.cast_mul,Nat.cast_ofNat,ne_of_gt,le_max_lefthave hprob : (fav.card : ℝ) / Fintype.card (β × Bool) = (above.card : ℝ) / Fintype.card β := by rw [hfavR] simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] field_simp [ne_of_gt hp] calc _ = (above.card : ℝ) / Fintype.card β := hprob _ ≤ forest_carpool_tail_envelope (j + 1) := by simpa [habove] using htail1 _ ≤ _ := le_max_left _ _
When some element has value j, all outcomes share the parity of j, which implies above = hi.
When |equal| ≠ 0, there is a witness b₀ with Y b₀ = j. By the constant parity property, every Y b has the same parity modulo 2 as j. Therefore, Y b > j implies Y b ≥ j + 2, meaning above is identical to the tail set hi = {b | j + 2 ≤ Y b}.
uses
Finset.card_pos.mp,Nat.pos_of_ne_zero,Finset.mem_filter.mp,Finset.mem_filter,Finset.mem_univ,true_and,Nat.cast_add,Nat.cast_ofNat· have hex : ∃ b, b ∈ equal := Finset.card_pos.mp (Nat.pos_of_ne_zero hzero) obtain ⟨b0, hb0⟩ := hex have hb0' : (j : ℤ) = Y b0 := (Finset.mem_filter.mp hb0).2 have habove : above = hi := by ext b have hpar : Y b % 2 = (j : ℤ) % 2 := by rw [hparity b, ← hparity b0, ← hb0'] simp only [above, hi, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_ofNat] omega
When |equal| ≠ 0, |fav| = |lo| + |hi|, and we obtain the tail envelope bounds at j and j + 2.
Using |lo| = |above| + |equal| and above = hi, we rewrite |fav| = 2|above| + |equal| as |lo| + |hi|. Since j ≥ 1 and j + 2 ≥ 1, the enveloped law tail bounds apply at thresholds j and j + 2.
have hfav2 : fav.card = lo.card + hi.card := by rw [hlo_card, ← habove, hfav]; omega have hfavR : (fav.card : ℝ) = (lo.card : ℝ) + (hi.card : ℝ) := by exact_mod_cast hfav2 have htail0 := htail j hj have htail2 := htail (j + 2) (by omega)
When |equal| ≠ 0, the probability is bounded by the average of the envelopes at j and j + 2, which is at most the maximum.
Dividing |fav| = |lo| + |hi| by |β × Bool| = 2|β| expresses the probability as the arithmetic mean of the tail probabilities at j and j + 2. Applying the tail bounds at j and j + 2 bounds this mean by (forest_carpool_tail_envelope(j) + forest_carpool_tail_envelope(j + 2)) / 2, which by le_max_right is at most the maximum.
uses
Fintype.card_prod,Fintype.card_bool,Nat.cast_mul,Nat.cast_ofNat,ne_of_gt,le_max_righthave hprob : (fav.card : ℝ) / Fintype.card (β × Bool) = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := by rw [hfavR] simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] field_simp [ne_of_gt hp] <;> ring calc _ = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := hprob _ ≤ (forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2 := by have h0 : (lo.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope j := by simpa [lo] using htail0 have h2 : (hi.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope (j + 2) := by simpa [hi] using htail2 linarith _ ≤ _ := le_max_right _ _
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp- If an element belongs to a filtered finite set, then it belongs to the base set and satisfies the predicate.
Finset.mem_product- An element belongs to the Cartesian product of two finite sets if and only if its first component belongs to the first set and its second component belongs to the second set.
Finset.mem_product.mp- If an element belongs to the Cartesian product of two finite sets, its components belong to the respective sets.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element in the first set does not belong to the second set.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_product- The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Nat.mul_comm- Multiplication of natural numbers is commutative.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set of that type.
true_and- The logical conjunction of True and a proposition p is equivalent to p.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Fintype.card_pos- A nonempty finite type has strictly positive cardinality.
Nat.cast_add- The coercion of a sum of natural numbers to an additive monoid with one equals the sum of their coercions.
Nat.cast_one- The coercion of 1 to an additive monoid with one equals 1.
Fintype.card_prod- The cardinality of the product of two finite types is the product of their cardinalities.
Fintype.card_bool- The type of Booleans has cardinality 2.
Nat.cast_mul- The coercion of a product of natural numbers equals the product of their coercions.
Nat.cast_ofNat- Numeric numerals coerce to their corresponding values in a numerical type.
ne_of_gt- If b < a in a preorder, then a ≠ b.
le_max_left- Any value a is less than or equal to the maximum of a and b.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
le_max_right- Any value b is less than or equal to the maximum of a and b.
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_bound (β : Type) [Fintype β] [Nonempty β] (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) (j : ℕ) (hj : 1 ≤ j) : (((Finset.univ.filter (fun p : β × Bool => (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) ≤ max (forest_carpool_tail_envelope (j + 1)) ((forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2) := by classical let above : Finset β := Finset.univ.filter (fun b => (j : ℤ) < Y b) let equal : Finset β := Finset.univ.filter (fun b => (j : ℤ) = Y b) let lo : Finset β := Finset.univ.filter (fun b => (j : ℤ) ≤ Y b) let hi : Finset β := Finset.univ.filter (fun b => ((j + 2 : ℕ) : ℤ) ≤ Y b) let fav : Finset (β × Bool) := Finset.univ.filter (fun p => (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true)) have hdis : Disjoint above equal := by apply Finset.disjoint_left.mpr intro a ha hb have ha' : (j : ℤ) < Y a := (Finset.mem_filter.mp ha).2 have hb' : (j : ℤ) = Y a := (Finset.mem_filter.mp hb).2 omega have hevent : fav = (above ×ˢ (Finset.univ : Finset Bool)) ∪ (equal ×ˢ {true}) := by ext p rcases p with ⟨b, c⟩ simp [fav, above, equal, Finset.mem_product] have hprod_dis : Disjoint (above ×ˢ (Finset.univ : Finset Bool)) (equal ×ˢ {true}) := by apply Finset.disjoint_left.mpr intro p hp hq have ha : p.1 ∈ above := (Finset.mem_product.mp hp).1 have hb : p.1 ∈ equal := (Finset.mem_product.mp hq).1 exact (Finset.disjoint_left.mp hdis) ha hb have hfav : fav.card = 2 * above.card + equal.card := by rw [hevent, Finset.card_union_of_disjoint hprod_dis] simp [Finset.card_product, Nat.mul_comm] have hlo : lo = above ∪ equal := by ext b simp only [lo, above, equal, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union] omega have hlo_card : lo.card = above.card + equal.card := by rw [hlo, Finset.card_union_of_disjoint hdis] have hp : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β)) have hpc : (0 : ℝ) < Fintype.card (β × Bool) := by exact_mod_cast (Fintype.card_pos (α := β × Bool)) obtain ⟨parity, hparity⟩ := hY.1 have htail := hY.2.2 by_cases hzero : equal.card = 0 · have hzeroR : (equal.card : ℝ) = 0 := by exact_mod_cast hzero have hfavR : (fav.card : ℝ) = 2 * (above.card : ℝ) := by exact_mod_cast (show fav.card = 2 * above.card by omega) have habove : above = Finset.univ.filter (fun b => ((j + 1 : ℕ) : ℤ) ≤ Y b) := by ext b simp only [above, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_one] omega have htail1 := htail (j + 1) (by omega) have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) = (above.card : ℝ) / Fintype.card β := by rw [hfavR] simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] field_simp [ne_of_gt hp] calc _ = (above.card : ℝ) / Fintype.card β := hprob _ ≤ forest_carpool_tail_envelope (j + 1) := by simpa [habove] using htail1 _ ≤ _ := le_max_left _ _ · have hex : ∃ b, b ∈ equal := Finset.card_pos.mp (Nat.pos_of_ne_zero hzero) obtain ⟨b0, hb0⟩ := hex have hb0' : (j : ℤ) = Y b0 := (Finset.mem_filter.mp hb0).2 have habove : above = hi := by ext b have hpar : Y b % 2 = (j : ℤ) % 2 := by rw [hparity b, ← hparity b0, ← hb0'] simp only [above, hi, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_ofNat] omega have hfav2 : fav.card = lo.card + hi.card := by rw [hlo_card, ← habove, hfav]; omega have hfavR : (fav.card : ℝ) = (lo.card : ℝ) + (hi.card : ℝ) := by exact_mod_cast hfav2 have htail0 := htail j hj have htail2 := htail (j + 2) (by omega) have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := by rw [hfavR] simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] field_simp [ne_of_gt hp] <;> ring calc _ = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := hprob _ ≤ (forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2 := by have h0 : (lo.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope j := by simpa [lo] using htail0 have h2 : (hi.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope (j + 2) := by simpa [hi] using htail2 linarith _ ≤ _ := le_max_right _ _