= Cycle lemma with increments at most one
{title2=$\#\{\text{good starting positions}\}=k$}
A standard positive-total form of the <Dvoretzky-Motzkin cycle lemma> uses a nonempty <sequence> $a=(a_1,\ldots,a_n)$ of <integers> satisfying
$$
a_i\leq1\quad(1\leq i\leq n),\qquad \sum_{i=1}^{n}a_i=k>0.
$$
Exactly $k$ starting positions have every nonempty <partial sum> strictly positive, using the same rotation convention as the sum-one <cycle lemma>. Negative entries can be arbitrarily large in magnitude, and zero entries are allowed. Addario-Berry's proposition 2.2.1 gives an equivalent form with increments at least $-1$ and negative total; reversing the <sequence> and changing all signs gives the form here. https://problab.ca/louigi/notes/ssprob2021.pdf#page=39[Addario-Berry, Lecture notes: 2021 CRM-PIMS Probability Summer School, proposition 2.2.1, p. 39]{ref}
\b[Four starts, two successes.] For $a=(1,1,1,-1)$, the <sum> is $k=2$. Starts $0$ and $1$ give <partial sums> $(1,2,3,2)$ and $(1,2,1,2)$, respectively. Start $2$ gives $(1,0,1,2)$ and touches zero; start $3$ gives $(-1,0,1,2)$ and begins below zero. Thus exactly two starts are good. The rotated <sequence> $(-1,1,1,1)$ has the same positive total, but its first start is bad: a positive final lead alone does not control earlier <partial sums>.
\Image[/cycle-lemma-good-rotations.png]
{title=All four starts of $(1,1,1,-1)$: the <cycle lemma with increments at most one> counts precisely the two paths whose nonempty <partial sums> stay strictly above zero}
\b[Positions can give identical words.] The <sequence> $(1,1,-1,1,1,-1)$ repeats a block of length three and has <sum> two. Its good starts are $0$ and $3$, both giving the same <word> $(1,1,-1,1,1,-1)$ with <partial sums> $(1,2,1,2,3,2)$. Starts $1$ and $4$ touch zero; starts $2$ and $5$ begin negatively. The <cycle lemma with increments at most one> counts two starting positions even though there is only one distinct good rotated <word>. Counting distinct <words> would lose the multiplicity that makes the statement true.
\Image[/cycle-lemma-periodic-start-positions.png]
{title=Six starting positions of the repeating <sequence> $(1,1,-1,1,1,-1)$: starts $0$ and $3$ produce identical good <words> and count twice}
\b[The upper bound matters.] The one-entry <sequence> $(2)$ has positive <integer> <sum> two, but only one starting position. Thus the sum-$k$ conclusion fails for arbitrary positive increments when $k>1$. The sum-one <cycle lemma> above needs no such upper bound. Strict positivity also matters: counting paths that merely stay at or above zero would include additional starts in both diagrams.
\b[From rotation to enumeration.] For a fixed admissible <sequence>, a start chosen from a <uniform distribution on a finite set> of its $n$ positions is good with <probability> $k/n$. More generally, let $\mathcal F$ be any <finite set> of length-$n$ <sequences> satisfying the increment bound and total $k$, closed under rotation. <Double counting> pairs consisting of a <sequence> and a good starting position gives
$$
\#\{a\in\mathcal F:\text{all nonempty partial sums of }a\text{ are positive}\}
=\frac{k}{n}|\mathcal F|.
$$
For each good output <sequence> and each of the $n$ positions, inverse rotation gives one such pair, even when several rotated <words> coincide. For example, the four <sequences> containing three $+1$ votes and one $-1$ vote have exactly $\frac24\binom43=2$ vote orders with a strictly positive running lead: $(1,1,1,-1)$ and $(1,1,-1,1)$. This is how the <cycle lemma with increments at most one> converts many prefix inequalities into a simple counting factor.
Back to article page
