forest_greedy_signed_step
def
The 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 values on a tie.
Statement
def forest_greedy_signed_step (x y : ℤ) (coin : Bool) : ℤ- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Used by 9
- 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…
- forest_greedy_step_negNegating both input discrepancies and flipping the tie coin negates the output of one greedy step.
- forest_greedy_merge_large_levelsTwo independent enveloped laws remain within the Fibonacci tail envelope after a greedy step at every integer level at least four.
- forest_greedy_symmetric_mergeThe greedy update of two independent finite uniform symmetric integer laws with a fair tie coin has symmetric value counts.
- forest_greedy_merge_fixed_parityIf the first endpoint has fixed discrepancy parity, one greedy step has fixed output parity for all partner values and tie coins.
- 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…
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
- forest_greedy_high_tail_stepFor two independent nonempty finite uniform integer laws and a fair tie coin, the updated tail at k is at most the first tail at k+1 plus…
- forest_greedy_refined_tail_stepFor two independent uniform finite integer laws and a fair tie coin, the probability that a greedy update reaches threshold k is bounded…
Lean source view module on GitHub
def forest_greedy_signed_step (x y : ℤ) (coin : Bool) : ℤ := if x < y then x + 1 else if y < x then x - 1 else if coin then x + 1 else x - 1