forest_carpool_tail_envelope
def
The proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
Statement
noncomputable def forest_carpool_tail_envelope (k : ℕ) : ℝ
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Used by 11
- 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_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_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_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.
- 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…
- forest_carpool_envelope_expAt every positive integer level, the Fibonacci tail envelope is at most exp(-(log 2 / 4) times 2 to the power of half the level).
- forest_carpool_fibonacci_envelope_decayAt every level at least four the proposed tail envelope is at least the next-level envelope plus the square of the previous-level envelope.
- 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…
- op_1106_forest_carpooling_random_greedy_double_exponential_tailThere exist absolute positive real constants c, C, and a such that for every natural number n, every forest edge sequence of length T ≥ 2…
- forest_carpool_maximum_fibonacci_tailFor a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the…
Lean source view module on GitHub
noncomputable def forest_carpool_tail_envelope (k : ℕ) : ℝ := if k = 2 then 3 / 8 else (1 / 2 : ℝ) ^ Nat.fib k