First-step decomposition of upward count
ProvedCountingLLL.ContractedWalk.upward_count_first_stepalgorithmsprobability
For a contracted-walk path starting above zero whose shifted tail reaches zero, the number of upward moves before absorption equals the indicator that the first step is upward plus the corresponding upward count of the shifted path from its new level. This pathwise identity is a first-step ingredient for the generating-function recursion.
Preamble
import Definitions.Def_CountingLLL_ContractedGF open CountingLLL.ContractedWalk
Formal statement
theorem CountingLLL.ContractedWalk.upward_count_first_step (ω : Tape) (i : ℕ) (hi : 0 < i) (h : ∃ t, level (fun n => ω (n+1)) (if ω 0 then i+2 else i-1) t = 0) : upwardCount ω i = (if ω 0 then 1 else 0) + upwardCount (fun n => ω (n+1)) (if ω 0 then i+2 else i-1) := by sorry
Source
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC 2027 #442, proof of Lemma 6.5, PDF p. 27, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf