A Discrete Model of Collective Marching on Rings

The paper proves, for k=1, E[Tstable] ≤ m^2 + 2(n−m) with a matching Ω(m^2 + n−m) lower bound using a persistent “winning segment” SW(t), a coupling-to-random-walk bound on the number of size changes (Lemma 4), and a 2(n−m) bound on waiting steps due to empties (Lemma 5), exactly as stated in Theorem 1 and its proof sketch . For k>1, the paper establishes E[Tstable] = O(min(mn+m^2, n^2 log k)) via (i) deadlock-and-elimination cascades giving O(mn+m^2) (Theorem 19) and (ii) a maximal-deadlock argument plus a k-walk absorption-time bound O(n^2 log k) (Lemma 20, Theorem 21), then takes the minimum (Theorem 10) . With erratic vertical switching 0<p<1 and m<nk, the paper proves finite expected time to global consensus by ensuring a bounded-below probability q>0 of increasing the number of clockwise agents within O(log k·n^2 + nk) steps (Theorem 22) . The candidate’s solution mirrors these constructions: the same segment decomposition and “winner” coupling for k=1; the same deadlock mechanism, gambler’s-ruin times, and sum-of-squares for O(mn+m^2); the same spectral-gap tail/maximum-of-k-walks idea for O(n^2 log k); and the same positive-probability progress argument for erratic switching. Minor differences are expository (e.g., phrasing of independence among deadlocked pairs; track-by-track vs global Mt), not substantive. The paper’s simplifying note that each track has ≥2 locusts (not essential) is explicit . Overall, both are correct and essentially the same proof structure.