Cycle lemma (${\sum }_i{b}_i=1$)

The cycle lemma turns a constraint at every prefix into a choice of where to start reading a circular sequence. Think of a lattice path whose vertical increments record votes for two candidates: $+1$ for one candidate and $-1$ for the other. Its partial sums are the running lead. Rotating the increments preserves the final lead, but changes whether that lead stays strictly positive throughout. This makes rotation useful for counting lattice paths subject to prefix constraints; the sum-one cycle lemma also supplies the cyclic prefix condition in the cyclic Turán covering construction.

The sum-one form. Let $b=(b_1,\dots ,b_n)$ be any nonempty sequence of integers with ${\sum }_{i=1}^n{b}_i=1$. A starting position $r\in \{0,\dots ,n-1\}$ means reading the rotated sequenceCall $r$ good when every nonempty partial sum of $b^{(r)}$ is strictly positive, including the full sum:The cycle lemma says there is exactly one good starting position. Negative entries, zero entries and positive entries larger than one are all allowed in this sum-one form. The empty partial sum is zero and is excluded from the positivity requirement. Douglas West's exercise 1.3.46(a) states a stronger result for arbitrary integer entries: take its case with all $n$ partial sums positive. ^[ref]

A worked sum-one example. For $b=(2,-2,0,1)$, the partial sums starting at zero are $S_0,S_1,S_2,S_3,S_4=0,2,0,0,1$. Starts $0,1,2$ fail: they have, respectively, a zero second partial sum, a negative first partial sum, and a zero first partial sum. Start $3$ reads $(1,2,-2,0)$ and has nonempty partial sums $1,3,1,1$, all positive. This example both allows an increment larger than one and shows why touching zero fails.

Why the last minimum works. Put $S_0=0$ and $S_j={\sum }_{i=1}^j{b}_i$. Choose the last index $r$ attaining the minimum of the proper partial sums $S_0,\dots ,S_{n-1}$: include $S_0$ and exclude $S_n$. After that index, later proper partial sums are strictly larger than $S_r$; also $S_n=1>S_r$, since $S_r\le 0$. Before wrapping, the new partial sums are therefore positive differences $S_j-S_r$. After wrapping, they are $1+S_j-S_r\ge 1$. In the worked example the last minimum is at $r=3$; choosing the first minimum at $r=0$ would fail. Uniqueness takes one further observation: two good starts would split the circle into two nonempty arcs, each having a positive integer sum, yet their sum would be one.

A standard positive-total form of the Dvoretzky-Motzkin cycle lemma uses a nonempty sequence $a=(a_1,\dots ,a_n)$ of integers satisfyingExactly $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. ^[ref]

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.

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.

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.

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 givesFor 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 $\frac{2}{4}\left(\genfrac{}{}{0ex}{}{4}{3}\right)=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.