forest_greedy_refined_tail_step
For two independent uniform finite integer laws and a fair tie coin, the probability that a greedy update reaches threshold k is bounded by the first-law tail at k+1 plus the mass between k-1 and k times the chance that the partner-coin pair permits an increase from k-1.
Statement
theorem forest_greedy_refined_tail_step (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (k : ℤ) : (((Finset.univ.filter (fun p : α × β × Bool => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α) + ((((Finset.univ.filter (fun a => k - 1 ≤ X a)).card : ℝ) / Fintype.card α) - (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α)) * (((Finset.univ.filter (fun p : β × Bool => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ))
- 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_signed_stepThe new discrepancy of the first endpoint of a greedy edge is x+1 when x<y, x-1 when x>y, and uses the fair coin to choose between these…
- forest_greedy_threshold_event_countFor two finite uniform endpoint populations and a fair tie coin, the number of greedy updates reaching an integer threshold is bounded by…
- 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 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 probability that a greedy step reaches threshold k is bounded by decomposing the space of the first random variable X into an upper tail (X ≥ k + 1) and a middle interval (k - 1 ≤ X ≤ k). By the combinatorial bound `forest_greedy_threshold_event_count`, any outcome in the upper tail guarantees an update of at least k, whereas outcomes in the middle interval reach k only if the partner variable and coin permit an increase. Expressing the middle interval's probability as the difference of upper tails ℙ(X ≥ k - 1) - ℙ(X ≥ k + 1) and dividing by the total number of outcomes yields the desired inequality.
Introduce notation for the upper tail, middle interval, lower tail, partner-coin condition, and the step event.
Under classical logic, we define the relevant subsets: `hi` for outcomes where X ≥ k + 1, `mid` for k - 1 ≤ X ≤ k, `lo` for X ≥ k - 1, `allow` for partner pairs (Y, coin) that allow an increase from k - 1, and `ev` for the triples where the greedy step reaches at least k.
classical let hi : Finset α := Finset.univ.filter (fun a => k + 1 ≤ X a) let mid : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k) let lo : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a) let allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let ev : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)
The lower tail `lo` is the union of `hi` and `mid`.
By unfolding definitions, an element satisfies X ≥ k - 1 if and only if either X ≥ k + 1 or k - 1 ≤ X ≤ k. Integer linear arithmetic (`omega`) confirms this logical equivalence.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_unionhave heq : lo = hi ∪ mid := by ext a simp only [lo, hi, mid, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union] omega
The sets `hi` and `mid` are disjoint.
Using `Finset.disjoint_left.mpr`, we assume an element belongs to both `hi` and `mid`. This would require X ≥ k + 1 and X ≤ k simultaneously, which integer linear arithmetic (`omega`) recognizes as impossible.
uses
Finset.disjoint_left.mpr,Finset.mem_filter.mphave hd : Disjoint hi mid := by apply Finset.disjoint_left.mpr intro a ha hb have hh : k + 1 ≤ X a := (Finset.mem_filter.mp ha).2 have hm : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp hb).2 omega
The cardinality of `lo` is the sum of the cardinalities of `hi` and `mid`.
Since `lo` is the disjoint union of `hi` and `mid`, `Finset.card_union_of_disjoint` asserts that |lo| = |hi| + |mid|.
uses
Finset.card_union_of_disjointhave hpart : lo.card = hi.card + mid.card := by rw [heq, Finset.card_union_of_disjoint hd]
The number of event outcomes |ev| is bounded by |hi| · |β × Bool| + |mid| · |allow|.
This counting bound is provided by `forest_greedy_threshold_event_count`: outcomes with X ≥ k + 1 always produce an update at least k regardless of the partner pair, while outcomes with k - 1 ≤ X ≤ k only reach k if the partner pair belongs to `allow`.
uses
forest_greedy_threshold_event_counthave hc : ev.card ≤ hi.card * Fintype.card (β × Bool) + mid.card * allow.card := by simpa [ev, hi, mid, allow] using forest_greedy_threshold_event_count α β X Y k
The counting bound, the partition formula, and the sample space sizes are transferred to positive real numbers.
We cast the counting inequality and the partition identity |lo| = |hi| + |mid| from ℕ to ℝ using `exact_mod_cast`. Because α and β × Bool are nonempty finite types, their sizes are strictly positive real numbers by `Fintype.card_pos`.
uses
Fintype.card_poshave hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) + (mid.card : ℝ) * (allow.card : ℝ) := by exact_mod_cast hc have hpartR : (lo.card : ℝ) = (hi.card : ℝ) + (mid.card : ℝ) := by exact_mod_cast hpart have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α)) have hq : (0 : ℝ) < Fintype.card (β × Bool) := by exact_mod_cast (Fintype.card_pos (α := β × Bool))
Dividing by the total number of outcomes yields the tail bound with normalized probabilities.
Dividing both sides of the counting bound by |α| · |β × Bool| preserves inequality via `div_le_div_of_nonneg_right`, since the denominator is strictly positive by `mul_pos` and `le_of_lt`. Rewriting |mid| as |lo| - |hi| using |lo| = |hi| + |mid| (`hpartR`) and clearing denominators (`field_simp`, `ring` using `ne_of_gt`) simplifies the right-hand side to the desired sum of probabilities.
uses
div_le_div_of_nonneg_right,le_of_lt,mul_pos,ne_of_gthave hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) ≤ (hi.card : ℝ) / Fintype.card α + ((lo.card : ℝ) / Fintype.card α - (hi.card : ℝ) / Fintype.card α) * ((allow.card : ℝ) / Fintype.card (β × Bool)) := by calc _ ≤ ((hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) + (mid.card : ℝ) * (allow.card : ℝ)) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) := div_le_div_of_nonneg_right hr (le_of_lt (mul_pos hp hq)) _ = _ := by rw [hpartR]; field_simp [ne_of_gt hp, ne_of_gt hq] <;> ring
The main probability inequality holds.
We express the product size |α| · |β × Bool| as |α × β × Bool| using `Fintype.card_prod` and `Nat.cast_mul`, which simplifies the normalized counts to the probabilities stated in the theorem.
uses
Fintype.card_prod,Nat.cast_mulsimpa [ev, hi, lo, allow, Fintype.card_prod, Nat.cast_mul] using hreal
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mp- If an element belongs to a filtered finset, then it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The proposition True ∧ p is equivalent to p.
Finset.mem_union- An element belongs to the union of two finsets if and only if it belongs to at least one of them.
Finset.disjoint_left.mpr- Two finsets are disjoint if every element of the first does not belong to the second.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
forest_greedy_threshold_event_count- The count of outcomes where the greedy step is at least k is bounded by the upper tail count times all partner pairs plus the middle count times the partner pairs permitting an increase.
Fintype.card_pos- A nonempty finite type has strictly positive cardinality.
div_le_div_of_nonneg_right- Dividing both sides of an inequality by a non-negative quantity preserves the inequality.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
mul_pos- The product of two strictly positive numbers is strictly positive.
ne_of_gt- If a number is strictly greater than another, they are not equal.
Fintype.card_prod- The cardinality of a Cartesian product of two finite types is the product of their cardinalities.
Nat.cast_mul- The cast of a product of natural numbers into a ring or field equals the product of their casts.
- The proof operates with counts of finite sets cast to real numbers (via `exact_mod_cast` and `Nat.cast_mul`), which corresponds on paper to working directly with uniform probability distributions on finite spaces.
- The algebraic simplification in line 49 that replaces the middle probability with the difference of tails is automated via `field_simp` and `ring`.
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_refined_tail_step (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (k : ℤ) : (((Finset.univ.filter (fun p : α × β × Bool => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α) + ((((Finset.univ.filter (fun a => k - 1 ≤ X a)).card : ℝ) / Fintype.card α) - (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α)) * (((Finset.univ.filter (fun p : β × Bool => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).card : ℝ) / (Fintype.card (β × Bool) : ℝ)) := by classical let hi : Finset α := Finset.univ.filter (fun a => k + 1 ≤ X a) let mid : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k) let lo : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a) let allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let ev : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2) have heq : lo = hi ∪ mid := by ext a simp only [lo, hi, mid, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union] omega have hd : Disjoint hi mid := by apply Finset.disjoint_left.mpr intro a ha hb have hh : k + 1 ≤ X a := (Finset.mem_filter.mp ha).2 have hm : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp hb).2 omega have hpart : lo.card = hi.card + mid.card := by rw [heq, Finset.card_union_of_disjoint hd] have hc : ev.card ≤ hi.card * Fintype.card (β × Bool) + mid.card * allow.card := by simpa [ev, hi, mid, allow] using forest_greedy_threshold_event_count α β X Y k have hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) + (mid.card : ℝ) * (allow.card : ℝ) := by exact_mod_cast hc have hpartR : (lo.card : ℝ) = (hi.card : ℝ) + (mid.card : ℝ) := by exact_mod_cast hpart have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α)) have hq : (0 : ℝ) < Fintype.card (β × Bool) := by exact_mod_cast (Fintype.card_pos (α := β × Bool)) have hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) ≤ (hi.card : ℝ) / Fintype.card α + ((lo.card : ℝ) / Fintype.card α - (hi.card : ℝ) / Fintype.card α) * ((allow.card : ℝ) / Fintype.card (β × Bool)) := by calc _ ≤ ((hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) + (mid.card : ℝ) * (allow.card : ℝ)) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) := div_le_div_of_nonneg_right hr (le_of_lt (mul_pos hp hq)) _ = _ := by rw [hpartR]; field_simp [ne_of_gt hp, ne_of_gt hq] <;> ring simpa [ev, hi, lo, allow, Fintype.card_prod, Nat.cast_mul] using hreal